#26 동적 계획법(Dynamic Programming) 2 - 심화(2)
저번 글에 이어서 동적 계획법을 활용하여 풀 수 있는 문제의 유형을 조금 더 알아본다.
1. 내리막 길(https://www.acmicpc.net/problem/1520)
2차원 배열의 형태로 지도가 주어지고 각 칸마다 그 지점의 높이가 10000 이하의 자연수로 주어졌을 때, 가장 왼쪽 위 칸에서 시작하여 가장 오른쪽 아래 칸으로 내리막길을 통해서만 이동하는 경로의 수를 구하는 문제이다. 풀이자체는 보자마자 떠올릴 수 있을정도로 간단한 완전탐색 문제이다. 다만 당연하게도 그냥 완전탐색을 실행하면 시간초과가 발생하기 때문에 동적 계획법을 적용하여 문제를 해결한다.
탐색은 가장 왼쪽 위나 가장 오른쪽 아래중 어느쪽에서 시작해도 좋다. 여기서는 가장 오른쪽 아래에서부터 시작하기로 한다. dfs(r, c) 가 가장 왼쪽 위, 즉 Map[0][0] 에서 시작하여 Map[r][c] 에 도달할 수 있는 경로의 수를 의미한다고 할 때, dfs(r, c) 는 인접한 네 칸 중 현재 지점보다 높이가 높은 칸들의 경로의 수의 합이된다. 이를 Python 코드로 표현하면 다음과 같다.
def dfs(r, c):
if r == c == 0:
return 1
res = 0
for nr, nc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= nr < m and 0 <= nc < n and Map[nr][nc] > Map[r][c]:
res += dfs(nr, nc)
return res하지만 위와 같이 실행하면 같은 계산을 매번 반복해야하기 때문에 동적 계획법을 적용시켜야한다. dfs(r, c)를 한번 계산하고나면 dp[r][c] 에 저장하여 다시 계산하지 않도록 한 코드는 다음과 같다.
def dfs(r, c):
if dp[r][c] != -1:
return dp[r][c]
dp[r][c] = 0
for nr, nc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= nr < m and 0 <= nc < n and Map[nr][nc] > Map[r][c]:
dp[r][c] += dfs(nr, nc)
return dp[r][c]이차원배열 dp는 -1로 초기화하여 방문여부를 알 수 있도록 하고 dp[0][0]은 시작위치이기 때문에 1로 초기화해준 상태에서 실행되는 것이 전제인 함수이다. 전체 코드는 다음과같다.
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
def sol1520():
# 세로, 가로의 크기
m, n = map(int, input().split())
# 각 지점의 높이 데이터
Map = [list(map(int, input().split())) for _ in range(m)]
# dp[r][c] 는 Map[0][0] 에서 Map[r][c] 로 이동할 수 있는 경로의 수
# 방문여부를 나타내기 위해 값은 모두 -1로 초기화
dp = [[-1] * n for _ in range(m)]
# 경로 탐색 함수
def dfs(r, c):
# 이미 계산된 값이라면 계산해둔 값을 반환
if dp[r][c] != -1:
return dp[r][c]
# 상하좌우 인접칸중 현 지점보다 높은 지점까지의 경로 수를 모두 더한여 dp[r][c]에 저장한다
dp[r][c] = 0
for nr, nc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= nr < m and 0 <= nc < n and Map[nr][nc] > Map[r][c]:
dp[r][c] += dfs(nr, nc)
# 결과값을 반환한다.
return dp[r][c]
# 시작지점의 경로 수는 1로 초기화
dp[0][0] = 1
# 가장 오른쪽 아래 칸의 경로 수를 탐색하여 결과를 반환
return dfs(m-1, n-1)
2. 팰린드롬?(https://www.acmicpc.net/problem/10942)
임의의 수열 seq가 주어졌을때, 수열의 시작점과 끝점인 s, e로 구성된 질의에 대해 seq[s:e+1] 이 팰린드롬을 이루는지 여부를 구하는 문제이다. (팰린드롬이란 앞으로 읽어도 뒤로 읽어도 같은 결과가 나오는 수열이나 문자열 등을 의미한다.) 당연하게도 모든 질의에 대해 팰린드롬 여부를 일일히 검사했다가는 O(NM)의 시간복잡도가 되는데, M의 크기 상한이 1,000,000이기 때문에 시간초과가 발생한다. 이 또한 동적 계획법을 적용시켜야 한다.
점화식을 찾는게 생각보다 간단한 문제이다. s부터 e까지의 수열이 팰린드롬을 이루기 위한 조건은 다음과 같다.
① seq[s] 와 seq[e] 의 값이 같다. => 앞뒤가 같아야 하기 때문에 첫 숫자와 끝 숫자는 당연히 같을 수 밖에 없다
② seq[s+1:e] 은 팰린드롬을 이뤄야한다. => 앞뒤로 숫자 하나씩을 떼더라도 앞뒤가 같은 상태는 유지되어야 한다.
이를 Python 코드로 표현한 코드는 다음과 같다.
# s부터 e까지의 수열이 팰린드롬인지 여부를 반환한다. (팰린드롬이라면 1, 아니라면 0)
def isPalindrome(s, e):
if s==e:
return 1
if e-s==1:
if seq[s]==seq[e]:
return 1
else:
return 0
return 1 if seq[s] == seq[e] and isPalindrome(s+1, e-1) else 0s와 e가 같은 경우, 즉 길이 1의 수열이라면 항상 팰린드롬을 이루며, s와 e의 차가 1인 경우, 즉 길이 2의 수열이라면 seq[s] 와 seq[e] 가 같다면 팰린드롬을 이루며 그렇지 않다면 팰린드롬을 이루지 않는다. 그 외의 경우 위에서 찾은 점화식에 따라 재귀호출을 통해 답을 찾을 수 있다. 여기에 동적 계획법을 적용한 코드는 다음과 같다.
# 방문여부 판별을 위해 dp 리스트 -1로 초기화
dp = [[-1]*n for _ in range(n)]
# 길이 1의 수열은 항상 팰린드롬
# 길이 2의 수열은 양 끝 값이 같다면 팰린드롬, 다르다면 팰린드롬이 아니다.
for i in range(n):
dp[i][i] = 1
if i < n-1:
dp[i][i+1] = 1 if seq[i] == seq[i+1] else 0
# s부터 e까지의 수열이 팰린드롬인지 여부를 반환한다. (팰린드롬이라면 1, 아니라면 0)
def isPalindrome(s, e):
# 아직 계산하지 않은 값이라면 점화식에 따라 계산
if dp[s][e] < 0:
dp[s][e] = 1 if seq[s] == seq[e] and isPalindrome(s+1, e-1) else 0
# 결과값 반환
return dp[s][e]이제 중복연산은 미리 저장해둔 dp값을 반환하여 효율적으로 문제를 해결할 수 있다. 전체 코드는 다음과 같다.
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
def sol10942():
# 수열의 크기
n = int(input())
# 수열
seq = list(map(int, input().split()))
# 각 질의에 대한 정답
answer = []
# dp[s][e] 는 s부터 e까지의 수열이 팰린드롬인지 여부를 저장 (팰린드롬이라면 1, 아니라면 0)
dp = [[-1]*n for _ in range(n)]
# 길이 1의 수열은 항상 팰린드롬
# 길이 2의 수열은 양 끝 값이 같다면 팰린드롬, 다르다면 팰린드롬이 아니다.
for i in range(n):
dp[i][i] = 1
if i < n-1:
dp[i][i+1] = 1 if seq[i] == seq[i+1] else 0
# 팰린드롬 여부를 반환하는 함수
def isPalindrome(s, e):
# 아직 계산하지 않은 값이라면 점화식에 따라 계산
# 양 끝 값이 서로 같고 양 끝 값을 제외한 부분이 팰린드롬이라면 자신도 팰린드롬이다.
if dp[s][e] < 0:
dp[s][e] = 1 if seq[s] == seq[e] and isPalindrome(s+1, e-1) else 0
return dp[s][e]
# 각 질의에 대해 isPalindrome 함수를 호출하여 정답을 answer 리스트에 저장
for m in range(int(input())):
s, e = map(int, input().split())
answer.append(isPalindrome(s-1, e-1))
# 출력 조건에 맞춰 정답 리스트 반환
return '\n'.join(map(str, answer))
오늘 풀어본 문제들의 경우 dp[i][j] 를 계산하기 위해 그 이전까지의 dp값을 모두 계산할 필요는 없기 때문에 반복문을 사용하 bottom-up 방식의 동적 계획법을 구현하는 대신 재귀를 활용한 top-down 방식의 동적 계획법을 구현하여 문제를 해결했다. 물론 이런 경우에도 bottom-up 방식의 동적 계획법으로 구현한 풀이는 여전히 잘 동작하지만 불필요한 계산이 들어가 오히려 재귀를 사용한 top-down 방식의 동적계획법에 비해 비효율적일 수 있으며 top-down 방식은 직관적이고 구현도 간단하기 때문에 실전에서 빠르게 문제를 해결하는데 유용하다. 문제 유형에 따라 적절한 방식을 채택하여 해결하는 것이 좋겠다.