SK네트웍스 Family AI 캠프 1기 3주차 알고리즘 스터디

Posted Jul 14, 2024

By J213h

8 min read

SK Networks AI Camp

알고리즘 스터디 - 3주차

알고리즘 스터디 3주차 주제는 다이나믹 프로그래밍(Dynamic Programming)입니다!
다이나믹 프로그래밍은 동적 계획법 또는 DP 라고도 얘기합니다.
“그래서 다이나믹 프로그래밍이 뭔데?” 라는 대답은 아래에서 해드리도록 하겠습니다.

다이나믹 프로그래밍이란?

다이나믹 프로그래밍은 복잡한 문제를 더 간단한 부분 문제로 나누어 해결하는 알고리즘입니다.
다시 말하자면 문제를 해결하는 과정에서 동일한 하위 문제가 여러 번 재계산되는 경우, 이를 방지하기 위해 하위 문제의 답을 저장해두고 재사용하는 것을 의미합니다.
다이나믹 프로그래밍의 구현 방식에는 크게 탑다운(top-down) 과 바텀업(bottom-up) 두 가지 방식이 있습니다.

탑다운 : 재귀적으로 문제를 풀면서 이미 계산한 하위 문제의 답을 저장하여 동일한 하위 문제가 나타나면 재사용합니다.
바텀업 : 작은 하위 문제부터 차례대로 해결하면서 결과를 배열에 저장하고, 이를 이용해 점차 더 큰 문제를 해결합니다.

아래에서 간단한 예제와 함께 탑다운 방식과 바텀업 방식의 차이점을 알아봅시다!

예 제

피보나치 수열

어떠한 숫자 N이 입력으로 주어졌을 때, N번째 피보나치 수를 구해보시오.

입력 예시 : 10
출력 예시 : 55

다이나믹 프로그래밍으로 문제를 해결하기 위해, 피보나치 수열을 정의해도록 합시다.
n번째 피보나치 수을 F(n)이라고 했을 때, 피보나치 수는 아래와 같이 정의됩니다.

F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) (if, n >= 2)

더 큰 F(n)이라는 값을 보다 작은 F(n - 2)와 F(n - 1)의 합으로 나타낼 수 있으므로, 피보나치 수열은 더 큰 문제를 풀기 위해 보다 작은 부분 문제를 이용할 수 있음을 알 수 있습니다.
따라서, 피보나치 수열은 다이나믹 프로그래밍으로 풀이할 수 있을 것입니다.

탑다운 방식(메모이제이션 이용)

  


def fibo(n, memo={}):
    if n in memo:
        return memo[n]
    
    if n == 0:
        return 0

    elif n == 1:
        return 1

    else:
        memo[n].= fibo(n - 1, memo) + fibo(n - 2, memo)
        return memo[n]

N = int(input())
print(fibo(N))

탑다운 방식에서는 memo라는 딕셔너리를 이용하여 계산된 결과를 저장하고, 이미 계산된 결과라면 다시 계산하지 않도록 구현하였습니다.

바텀업 방식

  


def fibo(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1

    dp = [0]* (n + 1)
    dp[0] = 0
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

N = int(input())
print(fibo(N))

바텀업 방식에서는 N번째 인덱스까지 저장할 수 있는 배열을 만들고, 계산된 결과를 해당하는 배열의 인덱스에 저장하여 반복되는 계산을 하지 않도록 구현하였습니다. —

연습 문제

거스름돈
14916번 문제 링크
그리디로 접근할 수도 있지만, 다이나믹 프로그래밍으로 처리하는 방법도 있습니다.

  


n = int(input())

INF = 1e18
# 매우 큰 값으로 테이블 초기화
dp = [INF] * 100001

# 초기값 설정
dp[2] = 1
dp[4] = 2
dp[5] = 1

# 6보다 큰 수에 대해서는 다이나믹 프로그래밍 적용
for i in range(6, n + 1):
    dp[i] = min(dp[i - 2], dp[i - 5]) + 1

# 거슬러 줄 수 없는 돈이라면 -1 출력하고
# 거슬러 줄 수 있다면 그 돈의 테이블 값을 출력
print(-1 if dp[n] == INF else dp[n])

1로 만들기
1463번 문제 링크
아래에 주석에 달아놓은 것처럼 하나의 큰 문제를 풀기 위해선 보다 작은 3가지 문제의 결과를 비교해보면 됩니다.

  


import sys

n = int(sys.stdin.readline())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * (int(1e6) + 1)

# 다이나믹 프로그래밍 진행(보텀업)
for i in range(2, n + 1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)

print(d[n])

삼각 그래프
4883번 문제 링크
각각의 노드에 접근하는 방식이 몇가지가 존재하는지 생각해보는 것이 중요합니다.
예를 들어 맨 왼쪽의 노드는 자기보다 한 칸위의 노드와 대각선 오른쪽 위의 노드에서만 접근이 가능하고, 맨 오른쪽의 노드는 자기보다 한 칸위의 노드와 대각선 왼쪽 위의 노드, 바로 왼쪽의 노드 이렇게 3가지 방향에서 접근이 가능합니다.

  


import sys


def solve(idx, n):
    graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    dp = [[0] * 3 for _ in range(n)]

    dp[0][0] = int(1e9)
    dp[0][1] = graph[0][1]
    dp[0][2] = min(graph[0][1], graph[0][1] + graph[0][2])

    for i in range(1, n):
        dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + graph[i][0]
        dp[i][1] = min(min(dp[i - 1]), dp[i][0]) + graph[i][1]
        dp[i][2] = min(dp[i - 1][1], dp[i - 1][2], dp[i][1]) + graph[i][2]

    print(f'{idx}. {dp[n - 1][1]}')


idx = 1
while True:
    n = int(sys.stdin.readline())

    if n == 0:
        break

    solve(idx, n)
    idx += 1