DP

개요

그리디 알고리즘 문제인줄 알고 풀다가 막혀서 정리해본다.

한 번 계산한 문제는 다시 계산하지 말자

피보나치 수열

피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 수열이다.
첫 번째 항과 두 번째 항은 1, 1이다.
그렇다면 세 번째 항은 1+1인 2가 되고 네 번째 항은 1+2로 3이된다.
이런 패턴으로 수열이 진행된다.
만약 특정 항의 값을 구하려면 다음과 같이 코드를 작성할 수 있다.

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

print(fibo(20))

시간복잡도는 얼마나될까?
빅 오 표기법을 기준으로는 한 번의 연산을 위해 2번의 연산이 필요하므로 2의 n제곱이 된다.
만약 n이 30이라면 약 10억번의 연산을 수행해야한다.
그러나 한발짝 떨어져서 살펴본다면 뭔가 아이디어를 찾을 수 있을지 모른다.
예를 들어 f(5)를 구한다면 다음과 같다.

f(5) -> f(4) + f(3)
f(4) -> f(3) + f(2)
f(3) -> f(2) + f(1)

보면 똑같은 함수가 반복적으로 호출된다는 점이다. f(4)를 구하기 위해산 f(3)과 f(2)가 호출되어야하고 또 연쇄적으로 호출되니 한 번 계산 결과를 전역 공간에서 저장하여 이를 재사용하는 아이디어를 떠올려보는 것이다.

d = [0] * 100

def fibo(n):
  if n == 1 or n == 2:
    return 1
  if d[n] != 0:
    return d[n]
  d[n] = fibo(n-1) + fibo(n-2)
  return d[n]

print(fibo(100))

이렇게 코드를 작성한다면 시간복잠도는 획기적으로 줄어든다.

직접 확인해보자.

d = [0] * 100

def fibo(n):
  if n == 1 or n == 2:
    return 1
  if d[n] != 0:
    return d[n]
  d[n] = fibo(n-1) + fibo(n-2)
  print(f'f({n})')
  return d[n]

print(fibo(6))

f(3)
f(4)
f(5)
f(6)
8

만약 적용하지 않았다면

f(6)
f(5)
f(4)
f(3)
f(3)
f(4)
f(3)
8

20번째 항도 구해보면 차이는 더 극명하다.
적용하지 않았을 때

20번째 항: 6765
연산 횟수: 13529

적용했을 때

20번째 항: 6765
연산 횟수: 18

시간복잡도는 O(N)이 된다.

위에서 살펴본대로 재귀 호출을 통해 해결하는 방법을 탑다운 방식이라고 하고 단순 반복문을 사용하는 경우를 바텀업이라고 한다.

d = [0] * 100
d[1] = 1
d[2] = 2

for i in range(3, n+1):
  d[i] = d[i-1] + d[i-2]

print(d[20])

예제

1로 만들기

정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 4가지다. 
1. x가 5로 나누어 떨어지면 5로 나눈다.
2. x가 3으로 나누어 떨어지면 3으로 나눈다.
3. x가 2로 나누어 떨어지면 2로 나눈다.
4. x에서 1을 뺀다.

이 연산 4개를 활용해서 1을 만들려고 한다. 최소 연산값을 구하시오

x = int(input())

d = [0] * 30001

for i in range(2, x+1):
    d[i] = d[i-1] + 1
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2] + 1)
    if i % 3 == 0:
        d[i] = min(d[i], d[i//3] + 1)
    if i % 5 == 0:
        d[i] = min(d[i], d[i//5] + 1)
print(d[x])

우선 기본적으로 1을 빼는 경우를 먼저 갱신한다.
1을 빼는 경우 d[2]는 d[1] + 1이 된다. 그런 다음 만약 2로 나누어지는 경우 1을 빼는 연산과 2로 나누는 연산과 비교해 더 작은 값을 현재 값으로 갱신한다.
3으로 나누어지는 경우 만약 더 적은 횟수로 1을 만들 수 있는지 확인하고 갱신한다.
이런 식으로 마치 피보나치 수열을 DP로 구현했을 때처럼 답을 찾을 수 있다.

어떻게 보면 그리디 알고리즘의 성격을 띄는 것처럼 보인다.
그러나 이전에 그리디 알고리즘에서 설명한 것처럼 국소적 최적해가 최적해를 보장하지 않는 경우엔 그리디 알고리즘을 사용할 수 없다.
예를 들어 일반적으로 생각했을 때 가능한 큰 수로 나누면 더 빠르게 숫자가 줄어든다.
그럼 3으로 나누어야하는데 답은 4가 나온다.

26 // 3 = 12
12 // 3 = 4
4 // 2 = 2
2 // 2 = 1

그러나 최적해는 다음과 같이 3이 나오기 때문이다.

26 - 1 = 25
25 // 5 = 5
5 / 5 = 1

이렇게 모든 가능한 선택을 고려하면서 최소 값을 구하는 방식인 DP 문제라고 하는 것이 더 적합하다.

백준 병사 배치하기

문제
N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.

또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.

예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자.

이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다.

병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.

출력
첫째 줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력한다.

예제 입력 1 
7
15 11 4 8 5 2 4
예제 출력 1 
2

주어진 데이터의 구조를 유지한채로 특정 원소를 제거시켜 내림차순 수열을 만들면 된다.
이러한 수열을 최장 증가 수열이(LIS)라고 한다.
LIS문제다.
두 가지 풀이법이 있다.

1. 2중 반복문을 통해 탐색하며 DP에 기록하는 방법

     for i in range(1, n):
    for j in range(0, i):
      if arr[i] > arr[j]:
        dp[i] = max(dp[i], dp[j] + 1)
   

   시간복잡도는 O(N^2)이다.

2. 이진 탐색으로 알아내는 방법
   배열에 요소를 추가하는데 적절히 들어가야할 위치를 이진 탐색으로 찾아 삽입하는 방법이다. 시간복잡도는 O(logN)

   for i in arr:
    idx = bisect_left(result, i)
   
    if idx == len(result):
        result.append(i)
    else:
        result[idx] = i
   

주의점

재귀 호출의 경우 시험 환경에서 스택 크기가 한정되어있는 경우 재귀 함수 깊이와 관련된 오류가 생길 수 있다.
해결 방법은 setrecursionlimit를 사용하여 재귀 깊이를 직접 설정하여 관련 오류를 피할 수 있다.
또 한가지 방법은 탑다운(재귀)방법이 아닌 보텀업(반복문)방법을 사용하여 풀이하는 것이다.

import sys

sys.setrecursionlimit(10 ** 6)