동적 계획법과 분할 정복

동적계획법

---

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

 

분할 정복

---

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

 

공통점과 차이점

---

[공통점]

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

[차이점]

• 동적 계획법
  • 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
  • 메모이제이션 기법 사용
• 분할 정복
  • 부분 문제는 서로 중복되지 않음
  • 메모이제이션 기법 사용x

 

recursive call 활용

---

def fibo(num):
    if num <= 1:
        return num
    return fibo(num - 1) + fibo(num - 2)
print(fibo(10))

 

동적 계획법 활용

---

def fibo(num):
    cache = [0 for index in range(num + 1)]  # 파이썬 comprehension
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num + 1):
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]

https://www.fun-coding.org/PL&OOP5-2.html

파이썬 특수 문법(데코레이터, 이터레이터등): 파이썬 Comprehension - 잔재미코딩

https://pythontutor.com/visualize.html#mode=display

Python Tutor - Visualize Python, Java, JavaScript, C, C++, Ruby code execution

 

분할 정복 활용

---

• 별도 챕터에서 다루는 병합 정렬과 퀵 정렬을 통해 이해

 

실전코딩테스트-동적계획법

---

[풀이 전략]

• 점화식을 찾아보자
  • 점화식이란, 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식을 의미함
  • 예) dp[n + 3] = dp[n + 1] + dp[n + 2]

[백준 11726번]

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

11726번: 2×n 타일링

"""
패턴
1. 빈 리스트 만들기(입력값에 따른)
2. 초기값을 설정
3. 점화식 기반으로 계산값 적용하기
4. 특정 입력값에 따른 계산값을 리스트에서 추출하기
"""
# 1
dp = [0] * 1001

#2
dp[1] = 1
dp[2] = 2

#3
for index in range(3, 1001):
    dp[index] = dp[index - 1] + dp[index - 2]

#4
print(dp[9])

[백준 9461번]

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

9461번: 파도반 수열

dp = [0] * 101
dp[1], dp[2], dp[3] = 1, 1, 1
for i in range(1, 98):
    dp[i + 3] = dp[i] + dp[i + 1]

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

[백준 1904번]

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

1904번: 01타일

n = int(input())

def fibo(n):
    cache = [0 for i in range(n + 1)]
    cache[1] = 1
    cache[2] = 2

    for i in range(3, n + 1):
        cache[i] = (cache[i - 2] + cache[i - 1]) % 15746
    return cache[n]
print(fibo(n))