[이코테] 다이나믹 프로그래밍

[이코테] 다이나믹 프로그래밍

* [나동빈 - 이것이 취업을 위한 코딩테스트다.]를 공부하고 정리한 글 입니다.

다이나믹 프로그래밍

중복되는 연산을 줄이자

메모리 공간을 약간 더 사용해 연산 속도를 비약적으로 증가시킬 수 있는 방법

탑다운 방식과 보텀업 방식이 있음

피보나치 수열

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시

피보나치 수열은 위와 같은 형태로 끝없이 이어진다.

이러한 피보나치 수열은 점화식으로 간단히 표현이 가능하다.

앞의 피보나치 수열 예시 이미지를 보면 첫 번째 항과 두 번째 항이 모두 1이기 때문에 아래 수식으로 정의할 수 있다.

프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있고, 수학적 점화식은 재귀함수를 이용해 간단히 표현할 수 있다.

따라서 피보나치 수열은 다음 소스로 구현이 가능하다.

def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2) print(fibo(4))

하지만 위의 방식으로 피보나치 수열을 구현하면 n이 크면 클 수록 수행 시간이 기하급수적으로 증가한다.

시간복잡도가 O(2^n)인 것이다.

따라서 이러한 문제를 다이나믹 프로그래밍으로 해결할 수 있다.

다이나믹 프로그래밍은 다음 조건을 만족해야 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있음

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일

피보나치 수열은 위의 조건을 만족하는 대표 문제이며, 메모이제이션 기법을 사용해 해결한 코드는 다음과 같다.

# 메모이제이션 기법이란?

다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법; 캐싱이라고 하기도 함

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍) def fibo(x): # 종료 조건(1 혹은 2일 때 1을 반환) if x == 1 or x == 2: return 1 # 이미 계산한 적 있는 문제라면 그대로 반환 if d[x] != 0: return d[x] # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환 d[x] = fibo(x - 1) + fibo(x - 2) return d[x] print(fibo(99))

즉, 다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이라고 불 수 있다.

분할 정복과의 차이점은 무엇일까?

분할 정복은 한번 문제가 해결되면 다시 처리하는 부분이 없으나 다이나믹 프로그래밍은 문제들이 서로 영향을 미친다.

한번 해결했던 문제를 다시금 해결하는 것이 다이나믹 프로그래밍의 특징, 따라서 답을 저장해놓고 다시 해결할 필요가 없다고 반환함

예시로 6번째 피보나치 수를 호출할 때는 색칠된 노드만 방문하게 된다.

왜냐하면 실선으로 표시된 노드들은 이미 계산이 되었기 때문에 호출하더라도 따로 계산하지 않고 리스트에 저장된 값을 가져오거나 바로 1을 반환하기 때문이다.

재귀함수 대신 반복문을 사용하면 오버헤드를 줄여 성능을 더 좋게 할 수 있다.

다이나믹 프로그래밍을 적용했을 때 시간 복잡도는 O(N)으로 훨씬 좋아진 것을 알 수 있다.

탑다운 방식과 보텀업 방식

탑다운 방식(하향식; 메모이제이션): 큰 문제를 해결하기 위해 작은 문제를 호출

보텀업 방식(상향식): 작은 문제부터 차근차근 답을 도출

피보나치 수열을 보텀업 방식으로 구현하면 다음과 같다.

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 100 # 첫 번째 피보나치 수와 두 번째 피보나치 수는 1 d[1] = 1 d[2] = 1 n = 99 # 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍) for i in range(3, n + 1): d[i] = d[i - 1] + d[i - 2] print(d[n])

# 메모이제이션에 어떤 자료형을 사용하는 것이 효율적인가?

연속적이지 않은 경우, 일부의 작은 문제에 대한 해답만 필요한 경우 사전(dict) 자료형이 유용

# 코딩테스트에서의 다이나믹 프로그래밍

대체로 간단한 형태로 출제

먼저 DP유형임을 파악하는 것이 중요, 완전 탐색으로 접근했을 때 시간이 오래 걸린다면 중복 여부를 확인하자

가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식 구현을 권장

예제는 다음 글에서 이어집니다.

https://shotory.tistory.com/43

from http://shotory.tistory.com/42 by ccl(A) rewrite - 2021-12-21 00:26:41