다이나믹 프로그래밍

다이나믹 프로그래밍의 개념

다이나믹 프로그래밍은 하나의 큰 문제를 작은 여러 개의 문제로 나누어 해결하는 알고리즘 기법이다.

중복되는 문제의 하위 해답을 저장하고 재사용하여 계산해서 재 사용성을 높이는 방법이다.

 

 

다이나믹 프로그래밍의 원리

1. 작은 문제로 분리 - 큰 문제를 작은 문제로 나눈다.

2. 하위 문제 해결 - 하위 문제를 해결하고 그 답을 저장한다.

3. 상위 문제 해결 - 하위 문제의 답을 가지고 재귀적으로 반복적으로 상위 문제를 해결해 나간다.

 

 

다이나믹 프로그래밍 문제 예시

백준 1463번 - 자세한 설명 및 문제는 링크를 통해 확인

 

풀이

n = int(input())
d = [0] * (n + 1)
for i in range(2, n + 1):
    d[i] = d[i - 1] + 1
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
print(d[n])

이해하기 위해 사용한 코드 ↓

n = int(input())
d = [0] * (n + 1)
print(d)
for i in range(2, n + 1):
    print(i)
    d[i] = d[i - 1] + 1
    print("before:")
    print(d)
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    print("after:")
    print(d)
print(d[n])

1. 1로 만들고자 하는 정수 n을 입력받는다.

2. d라는 리스트를 만들어서 n+1 개만큼의 인덱스를 생성한다.

 - 각 인덱스 i는 i를 1로 만들기 위한 최소한의 수, 예를 d [10]=3이라는 값이 저장되어 있으면 10을 1로 만들기 위한 최소한의 경우의 수는      3이라는 말이다. 

3. 2부터 n+1 만큼 for문을 돌립니다. / 1을 1로 만드는 최소한의 수는 0 이기 때문에 for문은 2부터 시작한다.

1. 1을 빼는 연산을 하기 위해서 d [i] = d[i - 1] + 1을 계산한다.
2. i가 3으로 나누어 떨어지면 d [ i // 3 ] 값에서 + 1을 계산하고 d [i] 값과 비교하여 작은 값을 d [i] 값으로 초기화해준다.
3. i가 2로 나누어 떨어지면 d [ i // 2 ] 값에서 + 1을 계산하고 d [i] 값과 비교하여 작은 값을 d [i] 값으로 초기화해준다.

4. d [n] 값을 출력한다.

 

 

이해하기 쉽게 설명하다면 3번의 1, 2, 3번의 연산이 순차적으로 진행되는 것이 아니라 각자 따로 진행된다고 생각하면 이해하기 쉽다.

예를 들어 i의 값이 12이고 d [11]까지의 값들은 전부 계산되어 있는 상태라고 생각해 보자. ( d [11]=4, d [4]=2, d [6]=2 )

1. d [12] = d[11] + 1 을 하면 d[12]는 5 라는 값이 나온다. ( 11에 1을 더하면 12니깐 횟수는 1이 추가됨 )

2. d[12] = d[ i // 3] + 1을 하면 d [4] 즉 4라는 값을 구하기 위한 최소한의 경우에 수에 1을 더한 3이 나온다. ( 4에 3을 곱하면 12 니깐 횟수는 1회가 추가됨)

3.  d[12] = d[ i // 2] + 1을 하면 d [6] 즉 6이라는 값을 구하기 위한 최소한의 경우에 수에 1을 더한 3이 나온다. ( 6에 2를 곱하면 12 니깐 횟수는 1회가 추가됨)

이후 1, 2, 3에서 계산한 결과 중 최솟값을 구하면 12를 구하기 위한 최소 값이 된다.

 

 

시간 복잡도

d의 리스트의 크기를 '(n+1)'로 초기화하는데 O(n)

반복문을 통해 2부터 n+1까지 계산하는데 O(n-2) -> O(n)

반복문안에 if문들은 i가 3, 2로 나누어 떨어지는지 계산 O(1)

따라서 전체 알고리즘의 시간 복잡도는 O(n)이다.