[DP] 문제 풀이 팁

다이나믹 프로그래밍 

큰 문제를 작게 나누고 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하려는 알고리즘 기법

다이나믹 프로그래밍을 사용할 수 있는 경우

1. 최적 부분 구조(큰 문제를 작은 문제로 나눌 수 있다)

2. 중복되는 부분 문제(동일한 작은 문제를 반복적으로 해결 (최적화))

 

두가지 조건을 만족하면 다이나믹 프로그래밍 방식을 사용할 수 있다 

 

하향식 (탑다운)

• 메모이제이션 기법사용 : 한번 계산한 결과를 메모리 공간에 메모하는 기법
• 재귀 사용
• 탑다운 방식
• 시간복잡도 O(N)

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현 (탑다운 DP)
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))

상향식 (보텀업)

• 반복문 사용
• 보텀업 방식
• 전형적인 형태 
• 결과 저장용 리스트를 DP테이블이라고 부름
• 시간복잡도 o(N)

# 보텀업 방식
# 앞서 계산된 결과 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫번째 피보나치 수와 두번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수 반복문으로 구현 (보텀업 DP)
for i in range(3, n+1):
	d[i] = d[i-1] + d[i-2]
 
 print(d[n])

 

문제 접근 방법

1. 주어진 문제가 다이나믹 프로그래밍 유형임을 파악한다
   • 최적 부분 구조 - 큰 문제를 작은 문제로 나눌 수 있는지
   • 중복되는 부분 문제 - 동일한 작은 문제를 반복적으로 해결할 수 있는지
2. 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제 해결할 수 있는지 검토
   • 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해본다
3. 일단 재귀함수로 베효율적인 완전탐색을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그래도 사용될 수 있으면 코드를 개선하는 방법 사용
4. 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많음