[백준BOJ] 단계별로 문제풀기 - 동적 계획법1 정답 및 후기[1](파이썬, python)

백준 알고리즘에서 제공되는 문제들 중 단계별로 문제 풀기 - 동적 계획법 1 1번~8번을 파이썬으로 풀어보았다. 코드는 8문제 통째로 깃허브에 올려놓았으며 각 문제마다 주석으로 표시해놨다. 남은 문제들도 빠른 시일 안에 풀어볼 예정이다.

www.acmicpc.net/step/16

동적 계획법 1 단계

원본 코드는 깃허브에!

https://github.com/tomy9729/Algorithm/tree/master/BaekJoon/Step-by-step%20troubleshooting(%EB%8B%A8%EA%B3%84%EB%B3%84%EB%A1%9C%20%EB%AC%B8%EC%A0%9C%ED%92%80%EA%B8%B0)/14.%20%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%951

tomy9729/Algorithm

 

0. 동적 계획법

동적 계획법은 재귀 함수의 비효율성에서 고안된 알고리즘이다. 재귀함수의 장점은 반복적인 구조를 가지는 코드를 작성할 때, 함수가 자기 자신을 다시 호출함으로써 함수를 한 번만 작성한다는 것이다. 하지만 이 과정에서 매우 비효율적인 상황이 발생한다. 이미 연산을 해서 결과를 알고 있음에도 또다시 같은 연산을 한다. 예를 들어 다음과 같이 재귀 함수를 통해 구현한 피보나치수열 함수를 통해 fibo(4)을 수행한다고 해보자.

def fibo(n) : if n == 0 : return 0 elif n == 1 : return 1 else : return fibo(n-1) + fibo(n-2)

fibo(4)는 1. fibo(3)과 2. fibo(2)를 호출한다.

1. fibo(3)은 1-1. fibo(2)와 1-2. fibo(1)을 호출한다.

2. fibo(2)는 2-1. fibo(1)과 2-2. fibo(0)을 호출한다.

1-1. fibo(2)는 fibo(1)과 fibo(0)을 호출한다.

 

위에서 1-1과 2는 완전히 같은 연산임에도 수행됨을 볼 수 있다. 연산이 짧으면 크게 문제가 되지 않지만 연산이 길고 반복 횟수가 많아질수록 급속도로 비효율적이게 된다. 동적 계획법을 통해 이러한 문제를 보완할 수 있다.

동적 계획법의 원리는 간단하다. 어떠한 연산이 수행될 때마다 연산의 결과를 저장한다. 그리고 해당 연산이 필요할 때마다 연산을 수행하지 않고 저장된 값을 불러온다. 불필요한 연산과정을 없앰으로써 훨씬 빠른 코드를 구현할 수 있다. 이처럼 동일한 문제를 반복할 때 한 번 계산할 결과를 저장하고 필요할 때마다 사용하는 방식을 메모제이션(memoization)라고 한다.

 

모든 재귀 함수는 반복문으로 재 구현할 수 있다. 동적 계획법은 기본적으로 재귀함수에서 고안된 알고리즘이기 때문에 모든 재귀 함수적 동적계획법은 반복문을 통해 구현하는 반복적 동적계획법으로 재구현할 수 있다. 또한 대부분 재귀함수적 동적계획법이 반복적 동적계획법보다 메모리 사용량도 많고 느리기 때문에 반복적 동적계획법으로 구현하는 걸 추천한다. 추가로 동적 계획법은 점화식을 기반으로 문제를 해결해나가기 때문에 때때로 규칙성을 통해 정답을 유추할 수도 있다.

 

문제를 풀면서 쉬운 문제의 경우 재귀 함수적 동적 계획법으로도 해결되거나, 바로 반복적 동적 계획법을 구현할 수 있었다. 그러나 복잡한 문제의 경우 처음에는 재귀함수로 만들 수 있는 반복되는 과정을 찾기 위해 노력했다. 그리고 반복되는 과정을 찾으면 우선 재귀함수를 구현했다. 재귀함수만 만들면 재귀함수적 동적계획법을 구현하는 건 비교적 쉽다. 재귀함수적 동적계획법을 구현하고 다시 반복적 동적계획법으로 변환했다. 중간과정이 많아 오래 걸리기는 했지만 동적 계획법에 대해 확실히 이해할 수 있었다. (적어도 내가 짠 코드에서는..) 어느 정도 익숙해진 후에는 바로 반복적 동적 계획법으로 구현하려 했지만 아직 완전히 익숙하지는 않았는지 구현 과정이 조금 헷갈렸다.

---

 

 

1. 1003번 피보나치 함수

동적 계획법으로 피보나치 함수를 구현하되 문제가 요구하는 것은 fibonacci(0)과 fibonacci(1)의 각 호출 횟수이다. 재귀 함수로 구현한 피보나치 함수를 따라가 보면 fibonacci(x)는 fibonacci(0)을 fibonacci(x-1)번, fibonacci(1)을 fibonacci(x)번수행했음을 알 수 있다. fibonacci함수의 계산된 결괏값들을 배열 fibonacci_arr[x]에 저장하고 필요시마다 호출함으로써 재귀 함수적 동적 계획법을 구현할 수 있다.

#1003번 피보나치 함수
fibonacci_arr = [0]*41

def fibonacci(n) :
  global count
  global fibonacci_arr
  if n == 0 :
    count[0] += 1 
    return 0
  elif n == 1 :
    count[1] += 1 
    return 1
  else : 
    if fibonacci_arr[n] == 0 : #불필요한 재귀함수를 막기 위함
      fibonacci_arr[n] = fibonacci(n-1) + fibonacci(n-2) #값을 배열에 저장함
    return fibonacci_arr[n]

count = [0]*2
T = int(input())
for i in range(T) :
  count[0] = 0
  count[1] = 0
  x = int(input())
  if x == 0 : 
    print("1 0")
  elif x == 1 :
    print("0 1")
  elif x == 2 :
    print("1 1")
  else :
    fibonacci(x)
    print("{} {}".format(fibonacci_arr[x-1],fibonacci_arr[x]))

---

 

2. 9184번 신나는 함수 실행

이미 구현된 재귀 함수인 w를 동적 계획법으로 재구현함으로써 속도 향상을 노리고 있다. 메모제이션을 위해 abc라는 3차 배열을 선언했으며 메모리 공간 최적화를 위해 필요한 최소크기인 21x21x21로 선언했다. 함수w안에서 첫 번째와 두 번째 if문은 함수 정지 조건이다. 세 번째 if문이 동적 계획법에서 가장 핵심적인 문장인 메모제이션을 사용하는 문장이다. 이미 계산된 값이 존재하다면 바로 사용함으로써 동적 계획법을 구현할 수 있다.

#9184번 신나는 함수 실행
abc = [[[0]*21 for i in range(21)] for j in range(21)]

def w(a,b,c) : 
  if a <= 0 or b <= 0 or c <= 0 :
    return 1
  if a > 20 or b > 20 or c > 20 :
    if abc[20][20][20] == 0 :  
      abc[20][20][20] = w(20,20,20)
    return abc[20][20][20]

  if abc[a][b][c] :
    return abc[a][b][c]
  if a < b and b < c : 
    abc[a][b][c] =  w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
    return abc[a][b][c]

  abc[a][b][c] = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1)
  return abc[a][b][c]

while True :
  a,b,c = map(int,input().split())
  if a == -1 and b == -1 and c == -1 : 
    break
  print("w(%d, %d, %d) = %d"%(a,b,c,w(a,b,c)))

---

 

3. 1904번 01타일

타일은 00타일 1타일로 두 종류이다. 이 두 가지 타일을 활용하여 만들 수 있는 길이가 n인 수열의 개수를 구하면 된다. 가장 먼저 해야 할 일은 점화식을 찾는 것이다. 점화식이 한눈에 보이지 않으면 숫자들을 쭉 늘여놓는 것도 하나의 방법이다.

• n = 1 : 1 (1개)
• n = 2 : 00 11 (2개)
• n = 3 : 001 100 111 (3개)
• n = 4 : 0000 0011 1001 1100 1111 (5개)
• n = 5 : 00001 00100 10000 00111 10011 11001 11100 11111 (8개)

더 해봐도 좋지만 이쯤 하면 점화식이 보이기 시작한다. 길이가 n일 때 수열의 개수를 tile_num(n)이라고 할 때 다음과 같은 점화식이 성립된다.

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

해당 점화식으로 반복적 동적 계획법을 구현한 것이 아래 코드이다. 문제에서 15746으로 나눈 나머지를 출력하라고 했으므로 점화식 뒤에 %15746을 추가하였다.

#1904번 01타일
n = int(input())

tile_num = [0]*1000001
tile_num[1] = 1
tile_num[2] = 2

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

print(tile_num[n])

---

 

4. 9641번 파도반 수열

3번 문제와 매우 유사하다. 이 문제의 경우 직접 그림을 그리면서 점화식을 찾아봤는데 계속 그리다 보면 금방 점화식을 찾을 수 있다. 파도반 수열 P(N)에 대하여 점화식은 다음과 같다.

P(N) = P(N-1) + P(N-5)

초기값 P(1)부터 P(5)까지는 직접 구하는데도 얼마 안 걸리기 때문에 직접 구해서 저장한다. 그 후 반복적 동적 계획법을 구현하면 된다.

#9641번 파도반 수열

T = int(input())
p = [0]*101
p[1] = 1
p[2] = 1
p[3] = 1
p[4] = 2
p[5] = 2

for i in range(6,101) : 
  p[i] = p[i-1] + p[i-5]

for i in range(T) : 
  x = int(input())
  print(p[x])

---

 

5. 1149번 RGB 거리

앞서 복잡한 문제의 경우 나만의 문제 푸는 과정을 언급했는데 이 문제에서 그 과정을 볼 수 있다. 아래 코드는 RGB거리 문제를 재귀 함수적 동적계획법과 반복적 동적 계획법으로 구현한 코드이다. 재귀함수적 동적계획법으로 제출하면 재귀 함수의 깊이가 너무 깊어 에러를 발생시킨다. 그러한 이유로 반드시 반복적 동적 계획법으로 구현해야 한다. 코드 길이만 봐도 둘의 차이가 느껴진다.

집마다 세 가지 색으로 칠할 수 있으며 각 색마다 드는 비용이 다르다. 또한 이웃하는 집은 같은 색으로 칠할 수 없다. 이때 모든 집을 칠하는 최소 비용을 구하면 된다. 각 색의 비용을 저장하는 color배열과 어떤 색을 칠할 때 최소 비용을 저장하는 min_point배열을 선언했다. 이웃하는 두 집은 같은 색을 칠할 수 없기 때문에 만약 x번 째 집에 빨간색을 칠할 때는 x-1번째 집에서 초록색을 칠할 때와 파란색을 칠할 때 중 더 적은 비용을 선택하면 된다. 그리고 선택한 비용을 min_point에 저장한다.

#1149번 RGB거리 - 재귀함수 + 동적계획
import sys
sys.setrecursionlimit(10**6) 
n = int(input())
home = [0]*1001
color = [[0]*3 for i in range(1001)]
min_point = [[0]*3 for i in range(1001)]

for i in range(1,n+1) : 
  color[i] = list(map(int,input().split()))

def paint_home(x,color_num) : #x번째 집을 칠할 때
  global color
  global min_point
  if x == 1:
    return color[1][color_num]
  if color_num == 0 : 
    if min_point[x][0] == 0 : 
      min_point[x][0] = color[x][0] + min(paint_home(x-1,1),paint_home(x-1,2))
    return min_point[x][0]
  elif color_num == 1 : 
    if min_point[x][1] == 0 :
      min_point[x][1] = color[x][1] + min(paint_home(x-1,0),paint_home(x-1,2))
    return min_point[x][1]
  elif color_num == 2 : 
    if min_point[x][2] == 0:
      min_point[x][2] = color[x][2] + min(paint_home(x-1,0),paint_home(x-1,1))
    return min_point[x][2]

print(min(paint_home(n,0),paint_home(n,1),paint_home(n,2)))

#1149번 RGB거리 - 반복문 + 동적계획
n = int(input())
min_point = [[0]*3 for i in range(1001)] #최솟값

min_point[1] = list(map(int,input().split()))
for x in range(2,n+1) :
  r,g,b = map(int,input().split())
  min_point[x][0] = r + min(min_point[x-1][1],min_point[x-1][2]) # x번 째 집에 빨간색을 칠하는 경우
  min_point[x][1] = g + min(min_point[x-1][0],min_point[x-1][2]) # x번 째 집에 초록색을 칠하는 경우
  min_point[x][2] = b + min(min_point[x-1][0],min_point[x-1][1]) # x번 째 집에 파란색을 칠하는 경우

print(min(min_point[n]))

---

 

6. 1932번 정수 삼각형

숫자들이 피라미드 모양으로 있으며 가장 위에서부터 왼쪽 대각선, 오른쪽 대각선으로만 이동할 수 있다. 이동 경로에 있는 숫자를 총합이 가장 큰 경우를 찾는 문제이다. 피라미드 모습이 마치 트리 같아 트리로 풀 수도 있겠다 생각했다.

각 층마다 왼쪽 끝에 있는 숫자와 오른쪽 끝에 있는 숫자가 선택될 수 있는 경우는 그 위층에 왼쪽 끝 숫자와 오른쪽 끝 숫자로부터 선택되는 방법밖에 없다. 이 두 가지 경우는 따로 정의해주고 나머지의 경우 선택될 수 있는 왼쪽 대각선과 오른쪽 대각선 중 더 큰 값에게 선택받으면 된다.

#1932번 정수 삼각형 - 재귀 + 동적계획
n = int(input())
triangle = [[0]*n for i in range(n)]
for i in range(n) :
  triangle[i] = list(map(int,input().split()))
max_point = [[0]*n for i in range(n)]

def select_num(floor, num) : 
  global triangle
  if max_point[floor][num] : 
    return max_point[floor][num]
  if floor == 0 : 
    max_point[floor][num] = triangle[floor][num]
    return max_point[floor][num] 
  if num == 0 : 
    max_point[floor][num] = triangle[floor][num] + select_num(floor-1,num)
    return max_point[floor][num]
  if num == floor :
    max_point[floor][num] = triangle[floor][num] + select_num(floor -1,num-1)
    return max_point[floor][num] 
  max_point[floor][num] = max(triangle[floor][num] + select_num(floor - 1, num-1),triangle[floor][num] + select_num(floor - 1 ,num))
  return max_point[floor][num]

result = []
for i in range(n) :
  result.append(select_num(n-1,i))
print(max(result))

#1932번 정수 삼각형 - 반복문 + 동적계획
n = int(input())
triangle = [[0]*n for i in range(n)]
for i in range(n) :
  triangle[i] = list(map(int,input().split()))
max_point = [[0]*n for i in range(n)]

max_point[0][0] = triangle[0][0]
for i in range(1,n) : 
  max_point[i][0] = triangle[i][0] + max_point[i-1][0]
  max_point[i][i] = triangle[i][i] + max_point[i-1][i-1]
  for j in range(1,i) : 
    max_point[i][j] = triangle[i][j] + max(max_point[i-1][j-1],max_point[i-1][j])

print(max(max_point[n-1]))

---

 

7. 2576번 계단 오르기

지금까지 푼 동적 계획법 문제 중 가장 오래 걸린 문제이다. 점화식을 찾는데 굉장히 오래 걸렸다. 계단은 세 개 이상 연속해서 밟을 수 없으며 마지막 계단은 반드시 밟아야 한다. 계단을 밟을 때마다 계단에 쓰인 점수를 얻는데 얻을 수 있는 최대 점수를 구하는 게 문제이다.

마지막 계단은 반드시 밟아야 하는게 문제의 핵심이다. 마지막 계단은 반드시 밟아야 하고 계단은 연속으로 두 개까지만 밟을 수 있기 때문에 마지막 전 계단을 밟을 경우와 밟지 않을 경우가 있다. 마지막 전 계단을 밟을 경우 마지막 전전 계단은 밟지 못하기 때문에 그 밑에 계단까지의 최고 점수를 고려해야 한다. 마지막 전 계단을 밟지 않을 경우 마지막 전전 계단까지의 최고 점수를 고려해야한다. 그 둘 중 더 큰 점수를 선택하면 된다. 계단이 n개 있을 때 이를 식으로 표현하면 다음과 같다.

최고 점수 =

n번 째 계단 점수 + n-2번째 계단까지의 최고 점수

or

n번 째 계단 점수 + n-1번째 계단 점수 + n-3번째 계단까지의 최고 점수

각 계단의 점수는 step배열에 저장했으며 n번 째 계단까지의 최고 점수는 point배열에 저장했다. 위 식을 다시 쓰면 다음과 같다.

point [n] = step [n] + max(point [n-2], point [n-3] + step [n-1])

해당 식까지 구하면 지금까지와 같은 방법으로 반복적 동적 계획법을 구현할 수 있다.

#2579번 계단 오르기
n = int(input()) 
step = [] #계단
for i in range(n) : 
  step.append(int(input()))
point = [False]*n
if n == 1 : #계단이 하나
   point[0] = step[0]
elif n == 2 : #계단이 둘
  point[1] = step[0] + step[1]
else :  #계단이 셋 이상
  point[0] = step[0]
  point[1] = step[0] + step[1]
  point[2] = max(step[1]+step[2],step[0]+step[2])
  for i in range(3, n) : 
    point[i] = step[i] + max(point[i-2], point[i-3] + step[i-1])

print(point[n-1])

---

 

8. 1463번 1로 만들기

어떤 수 n에 대하여 3으로 나누거나 2로 나누거나 1을 빼서 1로 만들어야 한다. 이때 같은 최소한으로 연산하는 횟수를 구하면 된다. 어떤 수 n에 대하여 연산하는 최솟값을 저장하는 배열 min_count를 선언했다. 어떤 수 n에 대하여 3으로 나누거나 2로 나누거나 1을 빼야 한다. n이 3으로 나눠진다면 3으로 나누는 경우와 1을 뺴는 경우 중 연산 횟수가 더 작은 값을 선택해야 한다. n이 2로 나눠진다면 2로 나누는 경우와 1을 뺴는 경우 중 연산횟수가 더 작은 값을 선택해야한다. n이 6으로 나눠진다면 3으로 나누는 경우와 2로 나누는 경우와 1을 빼는 경우 중 연산횟수가 더 작은 값을 선택해여한다. n이 2와 3으로 나눠지지 않으면 1을 빼는 경우를 선택해야한다.

#1463번 1로 만들기
n = int(input())
count = 0
min_count = [0]*(n+1)
def cal(n, count) : #재귀함수로 풀 경우 Recursion error 발생, 해답이 나오긴한다.
  global min_count
  if min_count[n] : 
    return min_count[n]
  if n == 1 : 
    return count
  if n % 6 == 0 : 
    min_count[n] = min(cal(n//3,count+1),cal(n//2,count+1),cal(n-1,count+1))
    return  min_count[n]
  if n % 3 == 0 : 
    min_count[n] = min(cal(n//3,count+1),cal(n-1,count+1))
    return  min_count[n]
  if n % 2 == 0 :
    min_count[n] = min(cal(n//2, count+1),cal(n-1,count+1))
    return  min_count[n]
  min_count[n] = cal(n-1,count+1)
  return min_count[n]

min_count[1] = 0
for i in range(2,n+1) :
  if i % 6 == 0 : # 6의 배수일 때, 3으로 나눈 경우/2로 나눈 경우/1을 뺀 경우 중 최솟값
    min_count[i] = 1 + min(min_count[i//3],min_count[i//2],min_count[i-1]) 
    continue
  if i % 3 == 0 : # 3의 배수일 때, 3으로 나눈 경우/1을 뺀 경우 중 최솟값
    min_count[i] = 1 + min(min_count[i//3],min_count[i-1])
    continue
  if i % 2 == 0 : # 2의 배수 일 때, 2로 나눈 경우, 1을 뺀 경우 중 최솟값
    min_count[i] = 1 + min(min_count[i//2],min_count[i-1])
    continue
  min_count[i] = min_count[i-1] +1 # 2,3의 배수가 아닌경우 그냥 1을 뺀다

#print(cal(n,0))  # 재귀함수로 풀 경우 답 출력
print(min_count[n])

---

 

[BaekJoon] 백준 알고리즘 단계별로 문제 풀기 - 동적 계획법 1 정답 및 후기[2](파이썬, python)에서 계속...