[이코테_코딩테스트] 다이나믹 프로그래밍 기초 문제 풀이 - 2

[문제] 효율적인 화폐 구성

• N가지 종류의 화폐가 있습니다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 합니다. 이때 각 종류의 화폐는 몇 개라도 사용할 수 있습니다.

• 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수입니다.

• M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하세요.

[문제] 효율적인 화폐 구성 - 문제 조건

[문제] 효율적인 화폐 구성 - 나의 답안 (Python)

n, m = map(int, input().split())
n_list = []

for i in range(n):
    n_list.append(int(input()))

d = [10001] * 10001
d[0] = 0

for i in n_list:
    for j in range(1, m + 1):
        if j % i == 0:
            d[j] = min(d[j], j // i)
        elif d[j] != 10001:
            d[j + i] = min(d[j] + 1, d[j + i])

if d[m] == 10001:
    print(-1)
else:
    print(d[m])

[문제] 효율적인 화폐 구성 - 문제 해결 아이디어

• = 금액 i를 만들 수 있는 최소한의 화폐 개수

• k = 각 화폐의 단위

• 점화식 : 각 화폐 단위인 k를 하나씩 확인하며
• 를 만드는 방법이 존재하는 경우,
• 를 만드는 방법이 존재하지 않는 경우,

• N = 3, M = 7이고, 각 화폐의 단위가 2, 3, 5인 경우 확인해 봅시다.

[문제] 효율적인 화폐 구성 - 답안 예시 (Python)

# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

[문제] 금광

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

• 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.

[문제] 금광 - 문제 조건

[문제] 금광 - 문제 해결 아이디어

• 금광의 모든 위치에 대하여 다음의 세 가지만 고려하면 됩니다.
1. 왼쪽 위에서 오는 경우
2. 왼쪽 아래에서 오는 경우
3. 왼쪽에서 오는 경우

• 세 가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 갱신해주어 문제를 해결한다.

• = i행 j열에 존재하는 금의 양

• = i행 j열까지의 최적의 해 (얻을 수 있는 금의 최댓값)

• 이때 테이블에 접근할 때마다 리스트의 범위를 벗어나지 않는지 체크해야 한다.

• 편의상 초기 데이터를 담는 변수 array를 사용하지 않아도 됩니다.
• 바로 DP 테이블에 초기 데이터를 담아서 다이나믹 프로그래밍을 적용할 수 있다.

[문제] 금광 - 답안 예시 (Python)

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

    # 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
    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)

[문제] 병사 배치하기

• N명의 병사가 무작위로 나열되어 있습니다. 각 병사는 특정한 값의 전투력을 보유하고 있습니다.

• 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 합니다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 합니다.

• 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용합니다. 그러면서도 남아 있는 병사의 수가 최대가 되도록 하고 싶습니다.

• 예를 들어, N = 7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하겠습니다.

• 이때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아 있는 병사의 수가 내림차순의 형태가 되며 5명이 됩니다. 이는 남아 있는 병사의 수가 최대가 되도록 하는 방법입니다.

• 병사에 대한 정보가 주어졌을 때, 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력하는 프로그램을 작성하세요.

[문제] 병사 배치하기 - 문제 해결 아이디어

• 이 문제의 기본 아이디어는 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어와 같다.

• 예를 들어 하나의 수열 array = {4, 2, 5, 8, 4, 11, 15}가 있다면,
• 이 수열의 가장 긴 증가하는 부분 수열은 {4, 5, 8, 11, 15}이다.

• 본 문제는 가장 긴 감소하는 부분 수열을 찾는 문제로 치환할 수 있다. LIS 알고리즘을 조금 수정하여 적용함으로써 정답을 도출할 수 있다.

가장 긴 증가하는 부분 수열(LIS) 알고리즘

• D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이

• 다시 원래 문제로 돌아와서 설명하자면, 가장 먼저 입력 받은 병사 정보의 순서를 뒤집는다.

• 가장 긴 증가하는 부분 수열 (LIS) 알고리즘을 수행하여 정답을 도출한다.

[문제] 병사 배치하기 - 답안 예시 (Python)

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

이 글은 유튜브 “동빈나” 채널의 “(이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍” 영상을 보고 작성하였습니다.