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')

출처 :

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

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

ACAYKP
0000000
C0111111
A0112222
P0112223
C0122223
A0123333
K0123344

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
ABCDE
A0
B0
C0
D0
E0
  1. AB, BC와 같이 1칸 차이가 나는 행렬은 그냥 곱한 것이 결과이다. 그 결과를 대입한다.
ABCDE
A0105
B0189
C0297
D0198
E0

  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])

결과

ABCDE
A0105240567364
B0189528294
C0297252
D0198
E0

정답코드

 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 읽기