[알고리즘] 동적 계획법(Dynamic Programming)과 분할 정복(Divide and Conquer)

1. 정의

동적계획법 (DP)

• 입력 크기가 작은 부분 문제들을 해결한 후 ➡️ 해당 부분 문제의 해를 활용해서 ➡️ 보다 큰 크기의 부분 문제를 해결 ➡️ 최종적으로 전체 문제를 해결하는 알고리즘
• 상향식 접근법으로, 가장 최하위 해답을 구한 후 ➡️ 이를 저장하고 ➡️ 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
• 🌟 Memoization 기법을 사용함
  - Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, “다시 계산하지 않도록” 하여 전체 실행 속도를 빠르게 하는 기술
• 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨
  - 예: 피보나치 수열

분할 정복

• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 하양식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
  - 일반적으로 재귀함수로 구현
• 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
  - 예: 병합 정렬, 퀵 정렬 등

2. DP와 분할 정복의 공통점과 차이점

공통점

• 문제를 잘게 쪼개서, 가장 작은 단위로 분할

차이점

• 동적 계획법
  - 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
  - Memoization 기법 사용 (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)
• 분할 정복
  - 부분 문제는 서로 중복되지 않음
  - Memoization 기법 사용 안함

3. 동적 계획법 알고리즘 이해

프로그래밍 연습

# 피보나치 수열 (대표적인 DP 문제)

# recursive call 활용 -> 같은 계산을 여러번 하게 됨
def fibo(x):
    if x <= 1:
        return x
    return fibo(x-1) + fibo(x-2)

# DP 활용 -> Memoization 기법 -> 같은 계산을 여러번 하지 않음
def fiboDp(x):
    cache = [0 for _ in range(x+1)] # Memoization 기법을 활용하기 위해 저장공간을 만든다
    cache[0] = 0
    cache[1] = 1
    
    for i in range(2, x+1): # i는 2부터 x까지
        cache[i] = cache[i-1] + cache[i-2]
        
    return cache[x]

코드 이미지

테스트

분할 정복 알고리즘의 예는 이후에 배울 병합 정렬과 퀵 정렬을 통해 이해

4. 실전 코딩 테스트

동적계획법

1) 연습 문제 1

백준에서 이 문제를 풀어보자

풀이 전략

일반적인 동적 계획법 문제는 통상 코드 자체는 간결하므로,
가장 적은 경우의 수부터 계산을 해본 후 ➡️ 패턴을 찾아 ➡️ “점화식”을 세우는 것이 핵심!

점화식이란, 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식을 의미함
- 예: dp[n+2] = dp[n+1] + dp[n+2]

코드 작성 패턴

1. 빈 리스트 만들기 (입력 값에 따른)
2. 초기값을 설정
3. 점화식을 기반으로 계산값 적용하기
4. 특정 입력 값에 따른 계산 값을 리스트에서 추출하기

풀이

n = int(input())
dp = [0 for _ in range(n+1)]

if n <= 3 : print(n)
else : 
	dp[1] = 1
	dp[2] = 2
	for i in range(3, n+1):
		dp[i] = dp[i-1] + dp[i-2]
	print(dp[i]%10007)

2) 연습 문제 2

백준에서 이 문제를 풀어보자

풀이

dp = [0 for i in range(101)]
dp[1] = 1
dp[2] = 1
dp[3] = 1

for i in range(1, 98): # i는 97까지
    dp[i + 3] = dp[i] + dp[i + 1] # dp[97 + 3] -> dp[100]

t = int(input())
for i in range(t):
    n = int(input())
    print(dp[n])

3) 연습 문제 3

백준에서 이 문제를 풀어보자

풀이

n = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

for k in range(3,n+1):
    dp[k] = (dp[k-1]+ dp[k-2])%15746
print(dp[n])

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기