동적 계획법(DP), 분할 정복(Divide and Conquer)

동적 계획법(Dynamic Programming, DP)

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

분할 정복(Divide and Conquer)

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

공통점

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

 

차이점

동적 계획법

• 부분 문제는 중복되어 상위 문제 해결 시 재활용
• Memoization 기법 사용 - 부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용
•  

분할 정복

• 부분 문제는 서로 중복되지 않음
• Memoization 기법 사용 안함

 

동적 계획법 알고리즘 이해

피보나치 수열

첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열

공식으로 나타내면 다음과 같다.

F(n) = F(n-1) + F(n-2)

토끼 번식과 관련된 문제로 나올수도

 

코드로 나타내면 다음과 같다.

def fibo(n):
  if n <= 1:
    return n
  return fibo(n-1) + fibo(n-2)

근데 여기서 문제는

만약 fibo(4)에 대해 진행될 때

fibo(3) + fibo(2)
fibo(3) = fibo(2) + fibo(1)
fibo(2) = fibo(1) + fibo(0)

이런 코드 흐름이 생기는데 fibo(2), fibo(1)의 계산이 반복되는 것을 볼 수 있다.

여기서 DP가 들어가 한번 계산한 부분 문제를 저장해놓고 재활용 할 수 있는 것이다.

 

코드로 나타내면 다음과 같다.

def fibo_dp(n):
  cache = [0 for i in range(n + 1)]  # 자기 스스로 저장해야 리턴할 때 cache[n]으로 내보낼 수 있으니
  cache[0] = 0
  cache[1] = 1
  
  for i in range(2, n + 1):
    cache[i] = cache[i - 1] + cache[i - 2]
  return cache[n]

0, 1은 미리 저장해놓고 2부터 (자기 자신)까지 cache에 담아 사용하며

마지막으로 cache[n]을 리턴함으로 재활용을 통해 피보나치 수열을 구현했다.

 

점화식 사용

문제 1

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

11726번: 2×n 타일링

 

점화식이란?

이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식

ex) dp[n + 3] = dp[n + 1] + dp[n + 2]

 

문제에 대해 그림을 그려 규칙을 찾아낸 모습

이에 따라 코드로 구현해봤다.

 

풀이

input_data = int(input())
print(test(input_data))

def test(n):
    cache = list([0 for _ in range(n+1)])
    cache[1] = 1
    cache[2] = 2
    
    if n >= 3:
        for i in range(3, n+1):
            cache[i] = cache[i-1] + cache[i-2]
    return cache[n] % 10007

음.. 잘못된 부분은 없는 것 같은데 계속 런타임 오류를 반환한다.

백준 처음 써봐서 프로그래머스 보다 구형의 형태라 뭔가 답답한 것도 있고 좀 스트레스

 

강의에서 정답이라고 준 풀이로 제출해보니

n = int(input())

cache = [0] * 1001
cache[1] = 1
cache[2] = 2

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

정답으로 뜨는데

1. 함수 선언 및 사용

2. cache 선언 방법

3. range가 1001까지가 아닌 n + 1이라?

 

근데 애초에 n이 1 이상 1000 이하로 들어올텐데

고정된 1000의 길이가 아니라 들어온 n의 값에 따라 오히려 더 작게 만들수도 있으니 

위의 코드가 더 좋지 않나 싶은데.. 음

 

문제 파악

cache = list([0 for _ in range(n+1)])

확인해보니 n = 1일 때 cache = [0, 0] 이 만들어지는데

cache[2] = 2를 하고 있던게 문제였다.

 

그럼 바로 에러 내뿜어주지 채점할 때마다 왜 2분씩이나 걸리냐고

 

백준에서는 문제 풀이가 처음이라 지인이 백준에서의 풀이 팁을 알려줬는데

메모리 제한이 있어도 생각보다 넉넉해서 문제 조건을 활용해 크기를 지정하라고 알려줬다.

해당 문제의 n에 대한 조건이 1 이상 1000 이하였기 때문에

cache 의 사이즈를 애초에 [0] * 1000으로 잡고 시작하게끔 변경했다.

 

def test(n):
    cache = list([0 for _ in range(1001)])
    cache[1] = 1
    cache[2] = 2
    
    for i in range(3, n+1):
        cache[i] = cache[i-1] + cache[i-2]
    return cache[n] % 10007
    
input_data = int(input())
print(test(input_data))

그렇게 해결 완료

 

문제 2. 파도반 수열

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

9461번: 파도반 수열

# 출력: 주어진 N에 대한 P(N)의 값

# 조건
# 1 <= N <= 100

# N = 10일 때
# 1, 1, 1, 2, 2, 3, 4, 5, 7, 9

# 패턴
# 2번째 인덱스부터 P(N) = P(N-2) + P(N-3)

문제 파악은 위와 같고

N = int(input())

dp = [0] * 101
dp[1] = 1
dp[2] = 1

for i in range(3, N+1):
    dp[i] = dp[i-2] + dp[i-3]
    
print(dp[N])

이렇게 제출했는데 실패

또 뭐가 문젠교

 

+ 해결

확실히 DP를 배운지 얼마 안됐을 때 작성된 포스팅이라 매우 허접하게 문제를 풀고 있었음

P(N) = P(N-2) + P(N-3)

위 점화식을 발견한거까진 좋았는데 이걸 활용하려면 dp[3] 까지는 초기화를 해줬어야 한다.

 

코드

import sys
input = sys.stdin.readline
for _ in range(int(input())):
  N = int(input())
  dp = [0] * 101
  dp[1] = 1
  dp[2] = 1
  dp[3] = 1
  for i in range(4, 101):
    dp[i] = dp[i-3]+dp[i-2]
  print(dp[N])

코드상으론 한 끗 차이지만 머릿속에 DP에 대한 개념이 자리잡기 전과 후의 차이가 큰 것 같다.