[Algorithm] DP (다이나믹 프로그래밍) 정리

 

 

 

 

 

다이나믹 프로그래밍이란, 한마디로 똑같은 계산을 두번 다시 하지 않도록 하는 알고리즘이다.

DP는 메모리 공간을 조금 더 사용하는 대신, 연산 속도를 증가시키는 방법이다.

따라서 한번 구한 결과값을 별도의 메모리 공간에 저장하는 방식을 따른다. 

이러한 방식을 Memoization(메모이제이션)이라고 한다.

 

 

 

DP에도 두가지 방식이 있는데 하나는 Top-Down(하향식), 하나는 Bottom-Up(상향식)이다.

 

 

 

 

'이것이 코딩테스트다' 교재에도 나와있고 백준에도 나와있는 DP의 가장 베이직한 문제 "1로 만들기"를 다이나믹 프로그래밍으로 푼 코드이다. 이때 Bottom-Up(상향식)을 사용했다. Top-Down 방식으로도 구현해보려고 했는데 찾아보니 메모리 초과가 난다고...

 

 

https://www.acmicpc.net/problem/1463 

1463번: 1로 만들기

 

 

Bottom-Up 방식으로 구현

x = int(input())

d = [0] * 3001

for i in range(2, x+1):
	d[i] = d[i-1] + 1  // -1 한 경우
    
    if i % 2 == 0:  // 2로 나눠지는 경우
    	d[i] = min(d[i], d[i//2]+1)  
    if i % 2 == 0:  // 3으로 나눠지는 경우
    	d[i] = min(d[i], d[i//3]+1)
    if i % 2 == 0:  // 5로 나눠지는 경우
    	d[i] = min(d[i], d[i//5]+1)
        
print(d[x])

처음에 이 코드를 봤을 때는 입력받은 값이 아니라 입력받은 값만큼의 index를 돌면서 index에 대해 연산을 하는게 잘 이해되지 않았다. 그래서 한참 생각했다...

결국 원리는 간단했다. 입력받은 수가 6이라면, d = [0 ,0, 0, 0, 0, 0, 0, 0] 만큼의 저장공간을 생성해두고 인덱스 값 2부터 계산한다.

 

 

 

 

 

 

 

 

 

아래는 내가 이해한 내용

내가 이 코드를 이해할 때 생각보다 시간이 걸렸기 때문에 혹시나 나와 같이 어려움을 겪는 사람들을 위해 길게 적어봤다.. 물론 코드만 봐도 이해되는 사람이라면 패스해주길

먼저 2는 2로 나누어지기 때문에 d[2//2]+1 과 d[1] + 1 를 비교해 작은 값을 넣어준다.

그럼 배열은 [0, 0, 1, 0, 0, 0, 0]이 된다. 

그 다음, 인덱스 값 3을 계산한다. 3은 3으로 나누어떨어지기 때문에 d[3//3]+1과 d[2]+1을 비교해 작은 값을 넣어준다.

배열은 [0, 0, 1, 1, 0, 0, 0]이 된다.

다음 인덱스 값 4는 2로 나누어떨어진다. 따라서 d[4//2]+1과 d[3]+1을 비교해 작은 값을 넣어준다. 

배열은 [0, 0, 1, 1, 2, 0, 0]이 된다. 이때쯤 각 인덱스에 해당하는 배열의 값은 계산 횟수를 의미하는구나!를 알 수 있게 된다. 4는 2의 배수이므로 2를 1로 만들기 위해 필요한 1회의 연산에 +1(2로 한번 더 나눠줌)을 하여 총 2회의 연산을 통해 1이 될 수 있다. 이런식으로 입력받은 값에 해당하는 인덱스 값까지 모두 계산을 하여 최종적으로 d[입력받은 값]을 출력하면 원하는 결과를 얻을 수 있다.