2023년 9월 9일 알고리즘 문제풀이

문제 1 백준 12865

문제 링크

1차 시도

나의 생각

입력값을 받을 때 무게 제한보다 무거운 물건은 아예 받지 않도록 조건을 추가한다. 큐를 이용한 최소힙을 통해 물건의 무게와 가치를 원소로 하는 배열에서 무게가 낮은 순서로 하나씩 pop한다. 배낭을 나타내는 배열에 [0,0]을 추가하여 아무것도 없는 상태를 만든다. pop할 때마다 기존 가방에 있는 것에 현재 물건을 더한 것을 추가해준다. 이 방식이면 원소갯수가 2배씩 늘어난다.

비어있는것 1개 => 첫번째 물건 더한것과 안더한것 2개 => 앞의 2개에 각각 두번째 물건을 더한것과 안더한 것 해서 총 4개 => 8개 => …

모든 경우의 가치를 음수로 바꾸어 또다른 큐에 넣는다. 최대 힙을 이용하여 가장 가치가 높을때를 출력하였다.

시간초과가 떴다.. 일부러 최소힙까지 썼는데 ..;

결과

오답(시간초과)

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
from heapq import heappush, heappop

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

arr = []
for _ in range(n):
    w,v = map(int,sys.stdin.readline().split())
    if w <= k:
        heappush(arr,[w,v])

n = len(arr)
dp = []
ans = []
dp.append([0,0])
while arr:
    w,v = heappop(arr)
    for i in range(len(dp)):
        p,q = dp[i]
        if p+w <= k:
            dp.append([p+w,q+v])
            heappush(ans,-1*(q+v))
print(-1*heappop(ans))

2차 시도

나의 생각

출처

이러한 유형의 문제를 풀때 냅색 알고리즘을 사용한다고 한다. 물건을 나눌 수 있을 때와 나눌 수 없을 때가 나뉘는데 여기선 물건을 쪼갤수 없으니 후자이다. 결론부터 말하자면 LCS와 비슷하게 2차원 배열을 만들고 이전 case를 통해 업데이트 하는 방식을 취한다.

2차원 배열에서 한 쪽은 물건의 번호를, 다른 쪽은 현재 가방의 무게를 index로 한다. dp[i][j] 는 i번째 물건 고민하고 있으며 현재 배낭 무게가 j인 상황에서 가장 높은 가치를 나타낼 것이다.

현재 배낭 무게 j보다 물건이 무거울 때(12행)는 배낭에 물건을 넣을수 없으므로 이전 물건을 결정할때와 동일한 가치를 가진다.

배낭 무게 j보다 물건이 가벼울 떄는 물건을 넣었을 떄와 넣지 않았을때를 파악해야 한다. 당연히 넣으면 가치가 올라가니 넣어야 한다고 생각하면 안된다. 이 물건을 넣기로 한다면 이전에 넣었던 물건이 들어가지 못할 수도 있기 떄문이다.

예를 들어, 물건 A는 무게가 8kg, 가치가 8이고 물건 B는 무게가 2kg, 가치가 3, 물건 C는 무게가 6kg, 가치가 10이라고 생각해보자. dp[1][4]이 의미하는 것은 현재 배낭의 무게가 4kg일 때 1번 물건까지 순회하여 계산한 가질 수 있는 가장 높은 가치이다. 따라서 0일 것이다. 물건 B는 넣지 못한다. 1번 물건까지 순회한다고 했기 때문이다.

현재 배낭의 무게를 8kg라고 한다면, dp는 어떤 값을 가져야할까? dp[1][8]부터 생각해보면, 물건 A를 고민하고 있는 상황이다. 순서대로 물건을 보기 때문에 물건 B,C는 고려하지 않는다. 이 물건을 보기 전은? 아무것도 없는 상황이다. 무게도, 가치도. 따라서 현재 배낭 무게(8)보다 물건의 무게(8)가 작거나 같으므로 넣어도 된다. dp[1][8] = 8이다.

dp[2][9] 차례다. 현재 물건 B는 무게 2kg, 가치 3이다. 그럼 dp[1][7] 에서 현재 물건의 가치와 무게를 더한 것과 같다고 볼 수 있다. 현재 배낭 무게인 9kg에 현재 물건을 포함시키려면 배낭에서 현재 물건의 무게를 뺏을 떄의 가치를 확인해야한다. dp[1][7] 에 물건 A는 들어갈 수없다. A의 무게가 8kg기 때문이다. 따라서 dp[1][7] 는 0이다. 여기서 갈람길이 나뉜다. 물건 A와 B 모두 들어갈 수는 없고 선택해야 한다.dp[1][7] 이자 배낭에 아무것도 없는 상황에서 물건 B를 넣어 만든 가치가 첫번째이다. 두번째는 dp[1][9], 물건 A만 들어가고 B는 고려조차 안한 상황이다. 둘 중 더 큰 가치를 지니는 것이 dp[2][9]값이 된다. 여기선 A의 가치가 더 크므로 dp[1][9] 의 값을 그대로 가져오면 된다.

가정을 바꾸어 물건 A의 무게를 4kg로 바꾸면 어떨까? 첫번째 dp[1][7]이 A와 B 둘다 포함되는 경우를 뜻하게 된다. 정리하면

i번째 물건까지 고려하는 상황에서 현재 배낭의 무게가 j일 때 가질 수 있는 가장 큰 가치

• 현재 고려하는 물건의 무게가 배낭무게보다 무겁다 : 이전 물건을 고려할때 값을 가져온다.
• 현재 고려하는 물건의 무게가 배낭무게보다 가볍다
  • 현재 물건을 넣는다 : 이전 물건까지 고려하는 상황에서 현재 배낭 무게에서 현재 물건의 무게를 뺏을때의 가치에서 현재 물건의 가치를 더한 값
  • 현재 물건을 넣지 않는다 : 현재 배낭 무게에서 이전 물건까지만 고려했을 때의 가치 값
  • 이 둘을 비교하여 높은 값으로 한다.

좀 더 이해를 돕기 위해 표를 첨부한다. 내부의 값은 가치의 최댓값을 의미한다. LCS에서 바로 위,왼쪽, 대각선 중 하나의 값을 가져오는 것과 헷갈려선 안된다!

(가) : 현재 고려하는 물건(2번)의 무게(4)가 배낭 무게(4)보다 작거나 같다. 따라서

• 물건을 넣는 경우 : 이전 물건(1번)까지 고려하는 상황에서 현재 배낭 무게(4)에서 현재 물건의 무게(4)를 뺏을 때(4-4=0)의 가치(0)에서 현재 물건의 가치(8)를 더한 값
  • dp[1][0] + 8 = 8
• 물건을 안 넣는 경우 : 현재 배낭 무게(4)에서 이전 물건(1번)까지만 고려했을 떄의 가치 값 = dp[1][4] = 0

둘 중 높은 값 : 8 이 (가)에 들어갈 값이다.

(나) : 현재 고려하는 물건(3번)의 무게(3)이 배낭 무게(7)보다 작거나 같다. 따라서

• 물건을 넣는 경우 : 이전 물건(2번)까지 고려하는 상황에서 현재 배낭 무게(7)에서 현재 물건의 무게(3)를 뺏을 때(7-3=4)의 가치에서 현재 물건의 가치(6)를 더한 값
  • dp[2][4] + 6 = (가) + 6 = 8 + 6 = 14
• 물건을 안 넣는 경우 : 현재 배낭 무게(7)에서 이전 물건(2번)까지만 고려했을때의 가치 값 = dp[2][7] = 13

둘 중 높은 값 14가 (나)에 들어간다.

결과

이해

코드

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

n,k = map(int,sys.stdin.readline().split())
arr = [[0,0]]
for _ in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,k+1):
        weight, value = arr[i]
        if j < weight:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(value+dp[i-1][j-weight], dp[i-1][j])

print(dp[-1][-1])

문제 2 백준 11049

문제 링크

1차 시도

나의 생각

여러개의 행렬을 곱한다고 가정했을 때 먼저 계산하는 두 파트로 나뉘는 경우를 모두 구한 후 최솟값을 고르도록 했다. 예를 들어, 5개의 행렬 a,b,c,d,e를 곱한다고 하면

[a] 와 [b,c,d,e] , [a,b]와 [c,d,e], [a,b,c]와 [d,e], [a,b,c,d]와 [e] 의 case를 생각했다. 이들 중 최솟값을 찾아내려고 했다. 각 case에서 전자의 것은 우리가 이미 알고 있는 것이다.

[a,b,c]는 행렬이 3개일 때 이미 최솟값을 구했을 것이고, [a,b,c,d]도 4개일 떄 이미 구햇을 것이다. 따라서 뒷파트의 것만 계산한 후 앞파트로 완성된 행렬과 뒷파트로 완성된 행렬을 곱할 떄의 계산을 더해주고자 했다. 여러개의 행렬의 결과로 만들어진 행렬의 크기는 가장 앞의 행렬의 행과 가장 뒤의 행렬의 열로 결정된다. 따라서 앞파트의 결과물 행렬과 뒷파트의 결과물 행렬의 크기를 미리 알 수 있고 따라서 그 곱도 알 수 있다.

예제 문제는 정답이 나왔는데 python3로 제출하면 시간 초과고, pypy3로 제출하면 오답이 뜬다.. 예외가 있나?

결과

오답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import sys

n = int(sys.stdin.readline())
arr = [0]
for _ in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))

dp = [0 for _ in range(n+1)]
dp[1] = 0
def cal(p,q):
    return p[0]*p[1]*q[1]
def mix(p,q):
    return [p[0],q[1]]

idx = 2
while idx <= n :
    if idx == 2:
        dp[idx] = cal(arr[idx-1],arr[idx])
        idx += 1
        continue

    tmp = []
    for i in range(1,idx):
        cnt = 0
        cnt += dp[i]
        k = arr[i+1]
        j = i+2
        cnt += arr[1][0]*k[0]*arr[idx][1]
        while j <= idx:
            cnt += cal(k,arr[j])
            k = mix(k,arr[j])
            j += 1
        tmp.append(cnt)
    dp[idx] = min(tmp)
    idx += 1
print(dp[-1])

2차 시도

나의 생각

내 기존코드에 오류를 발견했다. 예를 들어 A,B,C,D,E 를 해결한다고 했을 때 A와 BCDE로 나눈 후 BCDE는 그냥 순서대로 계산하여 처리했다. 근데 BCDE도 CD를 먼저 계산했을 때 더 작을 수도 있다. 내 코드에선 그러한 예시에 대한 처리가 안되었다.

LCS도 그렇고 DP에서 계속되는 방식은 배열을 통해 이전 경우에서 약간의 수정 혹은 그대로 현재 값을 도출해 내는 것이였다. 여기서도 그래야 할 것같은데, 1차원 배열로만 끝날리가 없다고 생각해서 2차원 배열을 그려내는 방법에 대해 고민했지만 힘들었다. 결국 과거의 내 답을 보고 이해할 수 있었다.

기존의 내 논리는 그대로 가져갔다. A,B,C,D,E 행렬의 곱셈의 최솟값은

• A 최솟값 과 BCDE 계산 최솟값 + 마지막 두 파트간 계산값
• AB 계산 최솟값과 CDE 계산 최솟값 + 마지막 두 파트간 계산값
• ABC 계산 최솟값과 DE 계산 최솟값 + 마지막 두 파트간 계산값
• ABCD 계산 최솟값과 E 계산 최솟값 + 마지막 두 파트간 계산값

이 4개 중 최솟값을 의미한다. 기존의 나는 A가 포함되지 않는 뒷 파트 계산에 대해 소홀해서 정답을 찾지 못했다. 따라서 A를 우선적 기준으로 생각하지 않았다. LCS에서 그랬듯 표를 그려보자.

위 표에서 i행부터 j열까지의 계산의 최솟값을 의미한다. 즉 3행 5열은 CDE 행렬의 곱셉의 최솟값을 나타낸다. 행과 열의 차이는 곱해야 할 행렬의 갯수를 의미한다. 행과 열이 같으면 총 행렬 갯수가 1개니까 계산 횟수가 0이다. 행과 열이 1 차이나는건 곱해야할 행렬의 갯수가 1개 존재한다는 뜻이다. 행렬 두개의 최솟값은 그냥 곱하는 방법 뿐이다. 차라서 (앞 행렬의 행)x(앞 행렬의 열)x(뒷 행렬의 열) 을 표시하면 된다. 아래를 보자.

가운데 대각선을 기준으로 대칭이라 한쪽만 입력했다. (가)라고 적혀있는 위 행렬의 (1,3)은 A,B,C의 최솟값을 의미한다. 위에서도 말했지만 이는 A,B의 최솟값 + 합치는 값 , B,C의 최솟값 + 합치는 값 중 최솟값일 것이다. A,B의 최솟값은 (1,2)의 값인 56이다. B,C의 최솟값은 (2,3) 인 70이다. 합치는 값만 알면 된다. A,B와 C의 합치는 값은 (A의 행)x(B의 열)x(C의 열)이다. B,C와 A의 합치는 값은 (A의 행)x(A의 열)x(C의 열)이다. 결국 56 + (4x7x5) = 196, 70 + (4x2x5) = 110 이므로 최솟값은 110이다.

(나)의 값은? ABCDE의 최솟값을 의미한다. 그렇다면

• A 최솟값 과 BCDE 계산 최솟값 + 마지막 두 파트간 계산값
  • (1,1) + (2,5) + (A행 x A열 x E열)
• AB 계산 최솟값과 CDE 계산 최솟값 + 마지막 두 파트간 계산값
  • (1,2) + (3,5) + (A행 x B열 x E열)
• ABC 계산 최솟값과 DE 계산 최솟값 + 마지막 두 파트간 계산값
  • (1,3) + (4,5) + (A행 x C열 x E열)
• ABCD 계산 최솟값과 E 계산 최솟값 + 마지막 두 파트간 계산값
  • (1,4) + (5,5) + (A행 x D열 x E열)

이들을 모두 알아야 한다.

이를 일반화시켜보자. 위 표에서 a행 b열을 어떻게 찾아낼 수 있을까?

• (a,k) + (k+1,b) + (a번째 행렬의 행) x (k번째 행렬의 열) x (b번째 행렬의 열)

k를 a부터 b까지 반복하면 된다. 하지만 이대로 코드 작성하면 틀린다. 실제로 이 표는 대각선의 순서대로 작성되야 한다. 즉 일반적인 반복문으로 i와 j의 이중반복문을 이용하면 안된다. 왼쪽위부터 1행 1열, 1행 2열, 1행 3열로 작성하면 정확한 값을 계산할 수 없다. 대각선 순서로 1행 1열 ~ 5행 5열 후 1행 2열 , 2행 3열 ,… 순서로 가서 마지막에 1행 n열을 봐야 한다!

i행 j열로 생각하지 말고, i를 가운데부터 몇번째 대각선인지, j는 그 대각선에서 어떤 열에 있는지를 표시하였다. 코드는 아래와 같다.

결과

이해

코드

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

n = int(sys.stdin.readline())
arr = []
for _ in range(n):
    arr.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(n-i):
        if i == 1:
            dp[j][j+i] = arr[j][0] * arr[j][1] * arr[j+i][1]
            continue

        dp[j][j+i] = 2**32
        for x in range(j,j+i):
            dp[j][j+i] = min(dp[j][j+i], dp[j][x] + dp[x+1][j+i] + arr[j][0] * arr[x][1] * arr[j+i][1])

print(dp[0][n-1])

문제 3 백준 11053

문제 링크

1차 시도

나의 생각

그래도 이건 좀 쉬웠다… 갯수가 최대 1000개라 1001개짜리 dp 배열을 만들었다. 수열을 앞에서부터 순회하는데 이 수열을 i 라 하고, 처음부터 i 전까지 를 j라는 이름으로 순회하였다. 즉 j는 i 보다 이전에 있는 모든 수를 순회한다. 순회하면서 j가 i보다 작다고 생각해보자. 그렇다면 j 지점까지 발견하여 기록한 증가하는 부분수열 값인 dp[j]보다 dp[i] 가 커야한다. j가 i보다 크므로 j까지 있는 증가하는 부분수열보다 딱 1이 더 커질것이기 때문이다. 따라서 j를 순회하면서 i보다 이전에 있는 증가하는 부분수열의 길이중 가장 큰 것으로 dp[i]로 업데이트 해준 이후, i가 커졌으므로 1만 더해주면 된다.

결과

정답

코드

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

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
dp = [0 for _ in range(1001)]

for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
print(max(dp))

• Previous
  사용자 식별
• Next
  점진적인 개선(3)