[이것이 취업을 위한 코딩테스트이다 with 파이썬] Ch.16 다이나믹 프로그래밍 문제

 📌한 장으로 보는 알고리즘

다이나믹 프로그래밍
 - 정의 : 한 번 해결된 부분 문제의 정답을 메모리에 기록 → 한 번 계산한 답은 다시 계산하지 않도록 함
 - 구현 : 점화식을 코드로 구현

탑다운과 보텀업
 - 다이나믹 프로그래밍을 이용한 소스코드 작성 방법
 - 탑다운 : 재귀함수를 이용, 큰 문제를 해결 위해 작은 문제 호출
 - 보텀업 : 반복문을 이용, 작은 문제 해결 후 작은 문제를 모아 큰 문제 해결

---

📌Q.31) 금광

 

✔️문제

n*m 크기의 금광, 금광은 1*1 크기의 칸으로 나누어져 있으며 각 칸은 특정한 크기의 금이 들어 있습니다.

채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫번째 열의 어느 행에서든 출발할 수 있습니다.

이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다.

 

결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.

 

✔️ 입력 조건

• 첫째 줄에 테스트 케이스 T가 입력됩니다. (1 <= T <= 1000)
• 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력됩니다. (1 <= n,m <= 20) 
  둘째 줄에 n*m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다. (1 <= 각 위치에 매장된 금의 개수 <= 1000)

✔️ 출력 조건

• 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다. 각 테스트 케이스는 줄 바꿈을 이용해 구분합니다. 

 

✔️ 입출력 예시

✔️ 나의 문제풀이

 - DP 규칙

• DP 맨 아래 줄 :  dp[i] = max(dp[i-1], dp[i+(m-1)]) + li[i]
• DP 중간 줄 : dp[i] = max(dp[i-1], dp[i+(m-1)], dp[i-(m+1)]) + li[i]
• DP 맨 윗 줄 : dp[i] = max(dp[i-1], dp[i-(m+1)]) + li[i]

t = int(input())

for _ in range(t):
    n,m = map(int,input().split())

    li = list(map(int,input().split()))
    dp = [0] * len(li)

    for i in range(len(li)):
        if i % m == 0:
            dp[i] = li[i]


    k = 1  
    while True:
        if k == m:
            break

        for i in range(len(li)):
            if i % m == k and 1 <= i < m:
                dp[i] = max(dp[i-1], dp[i+(m-1)]) + li[i]
            elif i % m == k and (n-1)*m < i < n*m:
                dp[i] = max(dp[i-1], dp[i-(m+1)]) + li[i]
            elif i % m == k and m < i < (n-1)*m:
                dp[i] = max(dp[i-1], dp[i+(m-1)], dp[i-(m+1)]) + li[i]
        k += 1
    
    print(max(dp)

 

 

✔️ 책의 문제풀이

 - 아이디어 : 2차원 테이블 이용, ① 왼쪽 위 ②왼쪽 아래 ③ 왼쪽 경우 중 가장 많은 금을 가지고 있는 경우를 테이블에 저장

• DP 테이블 접근 시, 리스트 범위 벗어나지 않는지 확인하기

# 테스트 케이스 입력
for tc in range(int(input())):
    n,m = map(int,input().split())
    array = list(map(int,input().split()))

    # 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
    # DP 테이블은 m-1 열까지만 저장 
    dp = []
    index = 0
    for i in range(n):
        dp.append(array[index:index+m])
        index += m

    # 다이나믹 프로그래밍 진행
    for j in range(1,m):
        for i in range(n):
            # 왼쪽 위에서 오는 경우
            if i == 0:
                left_up = 0
            else:
                left_up = dp[i-1][j-1]

            # 왼쪽 아래에서 오는 경우
            if i == n-1:
                left_down = 0
            else:
                left_down = dp[i+1][j-1]
            # 왼쪽에서 오는 경우
            left = dp[i][j-1]
            dp[i][j] = dp[i][j] + max(left_up, left_down, left)
    
    result = 0
    for i in range(n):
        result = max(result, dp[i][m-1])
    print(result)

 

 

✔️ 리뷰 

- 책과 1,2차원 배열 차이 아이디어는 동일

 

---

📌Q.32) 정수 삼각형

 

✔️ 문제 유형

 다이나믹 프로그래밍

 

✔️ 문제

1932번: 정수 삼각형

 

 

✔️ 나의 문제풀이

 - 2차원 배열 이용하여 규칙 찾음

• 왼쪽 위는 left_up = dp[i-1][j-1]로 정의, 단 j가 0일때는 범위 벗어나므로 제한
• 오른쪽 위는 right_up = dp[i-1][j], 단 i==j일때 오른쪽 위가 없으므로 범위 제한

n = int(input())

array = []
dp = []
for i in range(n):
    a = list(map(int,input().split()))
    array.append(a)
    dp.append([0 for i in range(len(a))])

dp[0][0] = array[0][0]

for i in range(1,len(array)):
    for j in range(len(array[i])):
        if j == 0:
            left_up = 0
        else:
            left_up = dp[i-1][j-1]

        if i == j:
            right_up = 0
        else:
            right_up = dp[i-1][j]

        dp[i][j] = max(left_up, right_up) + array[i][j]

print(max(max(dp)))

 

✔️ 책의 문제풀이

- Q.31과 매우 유사한 문제

- 아이디어 : ① 왼쪽 위 ② 바로 위의 위치에서만 내려올 수 있음, 2개의 위치 최적의 합 중 큰 값을 가지는 경우 선택

n = int(input())
dp = []

for _ in range(n):
    dp.append(list(map(int,input().split())))

# 다이나믹 프로그래밍으로 두 번째 줄부터 내려가면서 확인
for i in range(1,n):
    for j in range(i+1):
        # 왼쪽 위에서 내려오는 경우
        if j == 0:
            up_left = 0
        else:
            up_left = dp[i-1][j-1]
        # 바로 위에서 내려오는 경우
        if j == i:
            up = 0
        else:
            up = dp[i-1][j]
        # 최대 합을 저장
        dp[i][j] = dp[i][j] + max(up_left, up)

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

 

✔️ 리뷰

- array에 따로 저장하지 말고, 바로 DP테이블에 저장 시킨 후 문제 풀어보기

 

---

📌Q.33) 퇴사

 

✔️문제 유형

다이나믹 프로그래밍, 브루트포스 알고리

 

✔️문제

 

14501번: 퇴사

 

✔️나의 문제풀이

- 정답X, 시도만 함

n = int(input())
array = []

for _ in range(n):
    array.append(list(map(int,input().split())))

dp = [[0] * len(array) for _ in range(len(array))]

for i in range(len(array)):
    days =  i + array[i][0]
    for j in range(i + array[i][0], len(array)):
        #days =  i + array[i][0]
        if j == i + array[i][0]:
            dp[i][j] = dp[i][j-1] + array[i][1]
        else: 
            dp[i][j] = dp[i][j-1] + array[j-day_up][1]

        day_up = array[j][0]
        days += day_up
        

        if days == len(array) - 1:
            break
    print(dp)
    print()

print(dp)
# print(max(*dp))

 

✔️책의 문제풀이

아이디어 : 뒤쪽 날짜부터 거꾸로 확인하는 방식으로 접근하는 다이나믹 프로그래밍

→ 현재 상담 일자의 이윤 + 현재 상담을 마친 일자부터의 최대 이윤

• dp[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익
• max_value : 뒤에서부터 계산할 때, 현재까지의 최대 상담 금액에 해당하는 변수 

dp[i] = max(p[i] + dp[t[i] + i], max_value)

n = int(input())
t = []  # 각 상담을 완료하는 데 걸리는 시간
p = []  # 각 상담을 완료했을 때 받을 수 있는 금액
dp = [0] * (n+1)
max_value = 0

for _ in range(n):
    x,y = map(int, input().split())
    t.append(x)
    p.append(y)

# 리스트를 뒤에서부터 거꾸로 확인
for i in range(n-1, -1, -1):
    time = t[i] + i     # i를 더한 것이 총 기간을 알 수 있음  
    # 상담이 기간 안에 끝나는 경우
    if time <= n:
        # 점화식에 맞게, 현재까지의 최고 이익 계산
        dp[i] = max(p[i] + dp[time], max_value)
        max_value = dp[i]
    # 상담이 기간을 벗어나는 경우
    else:
        dp[i] = max_value
    

print(max_value)

 

✔️리뷰

- time은 해당 기간 시간 + 앞으로 나아갈 시간

- DP문제는 뒤에서도 생각해보기 

---

📌Q.34) 병사 배치하기

 

✔️문제 유형

다이나믹 프로그래밍, 가장 긴 증가하는 부분 수열 : O(nlogn)

 

✔️문제

18353번: 병사 배치하기

 

✔️나의 문제풀이

- 틀림 

n = int(input())
dp = list(map(int,input().split()))
ans = 0

now = dp[-1]
for i in range(n-1, 0, -1):
    if dp[i-1] < now:
        ans += 1
    else:
        now = dp[i-1]

print(ans)

 

✔️책의 문제풀이

아이디어 : '가장 긴 증가하는 부분 수열' 문제 - 하나의 수열이 주어졌을 때, 값들이 증가하는 형태의 가장 긴 부분 수열 찾기

→ '가장 긴 감소하는 부분 수열'의 길이 계산 문제로 간주, 입력 원소 순서 뒤집은 후 '가장 긴 증가하는 부분 수열' 문제의 점화식 적용 

- 예시

array = {10, 20, 10, 30, 20, 50} → {10, 20, 30, 50} 

• D[i] = array[i] 를 마지막 원소로 가지는 부분 수열의 최대 길이 
• DP테이블의 값은 1로 초기화

n = int(input())
array = list(map(int,input().split()))
array.reverse()

# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n
# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1,n):
    for j in range(0,i):
        if array[j] < array[i]:
            dp[i] = max(dp[i], dp[j]+1)

# 열외시켜야 하는 병사의 최소 수를 출력
print(n - max(dp))

 

✔️리뷰

- array[i]로 값 정해두고, array[i] 앞의 값 array[j]로 하나씩 체크 → array[i]보다 작은 값 원소 개수를 DP에 저장 → DP의 저장된 값으로 다음 큰 수 나올 때 사용 

- 알고리즘 코드 외워두기!

---

📌Q.35) 못생긴 수

 

✔️문제

못생긴 수 = 오직 2,3,4만을 소인수로 가지는 수(2,3,5를 약수로 가지는 합성수)

못생긴 수 = {1,2,3,4,5,6,8,9,10,12,15...}

→ 11번째 못생긴 수 : 15

 

✔️입력 조건

• 첫째 줄에 n 입력 (1 <= n <= 1000)

 

✔️출력 조건

• n번째 못생긴 수를 출력

 

✔️입출력 예시

 

✔️나의 문제풀이

- DP에 못생긴 수 저장, n에 맞는 수 출력

n = int(input())
cnt = 1
dp = [1]
num = 1

while True:
    if cnt == n:
        break

    if num == 1:
        num += 1
        continue

    if num % 2 == 0 or num % 3 == 0 or num % 5 == 0:
        cnt += 1
        dp.append(num)
    num += 1

print(dp[-1])

 

✔️책의 문제풀이

아이디어 : 가능한 못생긴 수를 앞에서부터 하나씩 찾기 → 못생긴 수에 2,3,5를 곱한 수 또한 못생긴 수에 해당

n = int(input())

ugly = [0] * n      # 못생긴 수를 담기 위한 DP 테이블
ugly[0] = 1


# 2배,3배,5배를 위한 인덱스
i2 = i3 = i5 = 0
# 처음에 곱셈값을 초기화
next2, next3, next5 = 2, 3, 5

# 1부터 n까지의 못생긴 수를 찾기
for l in range(1,n):
    # 가능한 곱셈 결과 중에서 가장 작은 수를 선택
    ugly[l] = min(next2, next3, next5)
    # 인덱스에 따라서 곱셈 결과를 증가
    if ugly[l] == next2:
        i2 += 1
        next2 = ugly[i2] * 2
    if ugly[l] == next3:
        i3 += 1
        next3 = ugly[i3] * 3
    if ugly[l] == next5:
        i5 += 1
        next5 = ugly[i5] * 5

print(ugly[n-1])

 

✔️리뷰

- 다이나믹 프로그래밍 : DP테이블 안에 있는 정보 완전탐색

- 인덱스 증가, min 함수 이용하여 DP 정보 완탐 및 정렬 가능

---

📌Q.36) 편집 거리

 

✔️문제

두 개의 문자열 A, B → 문자열 A를 편집하여 문자열 B로 만든다.

 

문자열 A 편집은 세 연산 중 한 번에 하나씩 선택하여 이용할 수 있음

 1) 삽입(Insert) : 특정한 위치에 하나의 문자를 삽입

 2) 삭제(Remove) : 특정한 위치에 있는 하나의 문자를 삭제

 3) 교체(Replace) : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체

 

편집 거리 = 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수 

→ 문자열 A를 문자열 B로 만드는 최소 편집 거리 계산

 

✔️나의 문제풀이

X

 

✔️책의 문제풀이

아이디어 : 최소 편집거리를 담을 2차원 테이블 DP 생성 → 최소 편집 거리를 계산하여 테이블에 저장

• 2차원 테이블 : 왼쪽(열) 문자열 → 위쪽(행) 문자열로 바꾸는 비용을 직관적으로 보여줌
• 예시) dp[3][3] = 2, 'sun' → 'sat' 문자열로 바꾸기 위한 최소 편집거리가 2 

# 최소 편집 거리(Edit Distance) 계산을 위한 다이나믹 프로그래밍
def edit_dist(str1, str2):
    n = len(str1)
    m = len(str2)

    # 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화 
    dp = [[0] * (m+1) for _ in range(n+1)]

    # DP 테이블 초기 설정
    for i in range(1,n+1):
        dp[i][0] = i
    for j in range(1,m+1):
        dp[0][j] = j

    # 최소 편집 거리 계산
    for i in range(1,n+1):
        for j in range(1, m+1):
            # 문자가 같다면, 왼쪽 위에 해당하는 수를 그대로 대립
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            # 문자가 다르다면, 3가지 경우 중에서 최솟값 찾기
            else:   # 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
                dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
    return dp[n][m]

str1 = input()
str2 = input()

print(edit_dist(str1,str2))

 

✔️리뷰

 - A,B 모두 완탐, 효율적으로 완탐하기 위해서는? → DP 사용하기

 - 문제풀이 이해

• 삽입: A의 문자는 그대로, B의 문자는 이전 문자로 이동
• 삭제 : A의 문자 공백, B의 문자는 그대로
• 교체 : A의 문자 공백, B의 문자는 이전 문자로 이동