1. 개발 진행 및 완료 상황

• 3주차 python algorithm 난이도 중 이하 문제 풀이 완료
• CSAPP 3.3 까지 공부

1. 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용

백준 9084 동전(https://www.acmicpc.net/problem/9084)

풀이 과정 : j원을 만들 수 있는 경우의 수를 dp[j]라 한다면 동전의 한 종류인 i원을 더한 j+i원을 만드는 경우의 수도 dp[j+i]를 더함으로서 구할 수 있다.

정답코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
ans = []
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    coin = list(map(int,sys.stdin.readline().split()))
    m = int(sys.stdin.readline())

    dp = [0] * 10001
    dp[0] = 1
    for i in coin:
        for j in range(1,m+1):
            if j-i >= 0:
                dp[j] += dp[j-i]
    ans.append(dp[m])
print(*ans, sep='\n')

출처 :

• https://velog.io/@whddn0221/%EB%B0%B1%EC%A4%80-9084-%EB%8F%99%EC%A0%84-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-%ED%8C%8C%EC%9D%B4%EC%8D%AC

• https://fre2-dom.tistory.com/489

백준 9251 LCS(Longest Common Subsequence, 최장 공통 부분 수열) (https://www.acmicpc.net/problem/9251)

풀이 과정 : 2차원 배열의 캐시를 만들어 해결하였다.

2개의 문자열의 현재 시점에서 LCS 값을 구한다. 같은 알파벳인 경우 해당 위치에서는 굴자를 추가하기 전의 LCS 값보다 1을 더해서 저장. 이중 for문이므로 i,j를 사용했을 때 위치는 [i-1][j-1]이다.

알파벳이 다른 경우 이전까지 비교한 값중 최대값

ex. CAP 와 ACA비교 : CAP,AC = 1, CA,ACA =2중 최대값인 2

정답코드

1
2
3
4
5
6
7
8
9
10
11
12
13
import sys

word1, word2 = sys.stdin.readline().strip(), sys.stdin.readline().strip()
h, w = len(word1), len(word2)
cache = [[0] * (w+1) for _ in range(h+1)]

for i in range(1, h+1):
    for j in range(1, w+1):
        if word1[i-1] == word2[j-1]:
            cache[i][j] = cache[i-1][j-1] + 1
        else:
            cache[i][j] = max(cache[i][j-1], cache[i-1][j])
print(cache[-1][-1])

출처 : https://myjamong.tistory.com/317

백준 12865 평범한 배낭 (https://www.acmicpc.net/problem/12865)

풀이 과정 : knapsack 알고리즘으로 풀 수 있다. 2차원 배열을 사용하였다. 각 무게일때 배낭의 최대 가치를 저장할 것이다.

무게가 점차 증가하면서 우리가 선택해야할 것은 다음과 같다.

1. 현재 배낭의 허용 무게보다 넣을 물건의 무게가 더 크다면 넣지 않는다.

2. 아니라면, 더 나은 가치를 선택해야 한다.

   2-1. 현재 넣을 물건의 무게만큼 배낭에서 빼고 현재 물건을 넣는다.

   2-2. 현재 물건을 넣지 않고 그대로 간다.

들어간 물건을 빼더라도 우린 이전 무게에서의 최대 가치를 저장해 왔기 때문에 구할 수 있다.

정답코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys

n, k = map(int, sys.stdin.readline().split())

thing = [[0,0]]
d = [[0]*(k+1) for _ in range(n+1)]

for i in range(n):
    thing.append(list(map(int, sys.stdin.readline().split())))

for i in range(1, n+1):
    for j in range(1, k+1):
        w = thing[i][0]
        v = thing[i][1]

        if j < w:
            d[i][j] = d[i-1][j]
        else:
            d[i][j] = max(d[i-1][j], d[i-1][j-w]+v)

print(d[n][k])

출처 : https://hongcoding.tistory.com/50

백준 11049 행렬 곱셈 순서 (https://www.acmicpc.net/problem/11049)

풀이 과정 : pypy3로만 풀 수 있는 문제였다.

dp라는 새로운 행렬을 만든다. 절반만 쓸 예정이다. 각 칸의 의미는 i행렬부터 j행렬까지 행렬 곱의 최솟값이다.

1. 각 행렬이 같은 부분은 0

1. A~B, B~C와 같이 1칸 차이가 나는 행렬은 그냥 곱한 것이 결과이다. 그 결과를 대입한다.

1. 두 칸 이상 떨어진 행렬들의 곱의 최솟값은 다음과 같이 구할 수 있다.

   ABCDE의 최솟값 :

   min(ABCDE,

   min(A) + min(BCDE) + (A행 x A열 x E열),

   min(AB) + min(CDE) + (A행 x B열 x E열),

   min(ABC) + min(DE) + (A행 x C열 x E열),

   min(ABCD) + min(E) + (A행 x D열 x E열)

   )

k를 첫행렬부터 마지막 행렬-1 까지 순회한다.

dp[첫행렬 위치][k] + dp[k+1][마지막 행렬 위치] + (matrix[첫행렬 위치][0]*matrix[k][1]*matrix[마지막행렬 위치][1])

결과

정답코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import sys
N = int(sys.stdin.readline())
matrix = []
for _ in range(N):
    matrix.append(list(map(int, sys.stdin.readline().split())))
dp =[[0 for _ in range(N)] for _ in range(N)]


for i in range(1, N): #몇 번째 대각선?
    for j in range(0, N-i): #대각선에서 몇 번째 열?

        if i == 1: #차이가 1밖에 나지 않는 칸
            dp[j][j+i] = matrix[j][0] * matrix[j][1] * matrix[j+i][1]
            continue

        dp[j][j+i] = 2**32 #최댓값을 미리 넣어줌
        for k in range(j, j+i):
            dp[j][j+i] = min(dp[j][j+i],
                             dp[j][k] + dp[k+1][j+i] + matrix[j][0] * matrix[k][1] * matrix[j+i][1])
print(dp[0][N-1]) #맨 오른쪽 위

출처 : https://claude-u.tistory.com/271

1. 새로 배운 내용

2. 참고할 만한 레퍼런스들
   • 각 백준 문제 정답코드 밑 참고
3. 특이사항
   • leetcode 공부 필요
4. 회고
   • 블로그 옮기는 동안 많이 밀렸다. 열심히 해야겠다.
5. TO-DO-LIST
   • 난이도 상 문제 풀어보기
   • 추가문제 풀어보기
   • CSAPP 읽기

• Previous
  습관