알고리즘
[종만북] DP 돌려깎기
nahowo
2025. 2. 3. 19:56
[종만북] 외발 뛰기 (난이도 하, 1권 215 페이지) - 2025.2.2
1. 문제 이해하기
- 종만북 215p에 나온 문제이다.
2. 이론 세우기
- 이동 방향은 아래쪽, 오른쪽뿐이므로 해당 위치에서 재귀를 호출한다.
3. 이론 검증하기
- for문에서 왼쪽 → 오른쪽, 위 → 아래로 순회할 때 정답이 나오는 이유
- 이동 가능한 방향이 왼쪽 → 오른쪽, 위 → 아래 두 방향밖에 없으므로 가로 이동 시 0, 7에 도착하기 위해서는 0, 0과 0, 6 사이 어떤 블럭에서 이동하는 경우밖에 없다. 상하 이동도 동일하다.
4. 의사코드 작성하기
**- for문 dp**
방문 배열을 False로 초기화한다.
0, 0은 시작점이니까 True로 초기화한다.
배열을 순회한다.
현재 위치의 방문 배열이 True라면:
현재 위치에서 오른쪽 이동이 가능하다면 True로 체크한다.
현재 위치에서 아래쪽 이동이 가능하다면 True로 체크한다.
반복문 종료 후 방문 배열의 [n - 1][n - 1]을 출력한다.
**- 재귀 함수**
현재 위치가 범위를 벗어난다면 0을 반환한다.
현재 위치가 도착점(n - 1, n - 1)이라면 1을 반환한다.
현재 위치를 방문한 적이 있다면(cache[i][j] != -1):
현재 위치의 캐시값을 반환한다.
현재 위치에서 이동 방향을 더한 값으로 재귀 함수를 호출한다.
오른쪽 이동 | 왼쪽 이동 함수를 현재 캐시값으로 저장한다.
**- 재귀 dp 호출 함수**
캐시를 -1로 초기화한다.
재귀 함수(0, 0)을 호출한 뒤 반환값을 출력한다.
import sys
input = sys.stdin.readline
MAP = [[2,5,1,6,1,4,1],
[6,1,1,2,2,9,3],
[7,2,3,2,1,3,1],
[1,1,3,1,7,1,2],
[4,1,2,3,4,1,2],
[3,3,1,2,3,4,1],
[1,5,2,9,4,7,0]]
n = len(MAP)
def solutionFor():
canVisit = [[False] * n for _ in range(n)]
canVisit[0][0] = True
for i in range(n):
for j in range(n):
if canVisit[i][j]:
if i + MAP[i][j] < n:
canVisit[i + MAP[i][j]][j] = True
if j + MAP[i][j] < n:
canVisit[i][j + MAP[i][j]] = True
return canVisit[n - 1][n - 1]
def recursion(i, j):
if i >= n or j >= n:
return 0
if i == n - 1 and j == n - 1:
# cache[i][j] = 1
return 1
if cache[i][j] != -1:
return cache[i][j]
jump = MAP[i][j]
cache[i][j] = recursion(i + jump, j) | recursion(i, j + jump)
return cache[i][j]
def solutionRec():
global cache
cache = [[-1] * n for _ in range(n)]
return recursion(0, 0)
print(solutionRec())
5. 복기하기
- 재귀 방식에 대해
- 지금까지 계속 for문 방식으로 dp를 풀었어서 그런지 캐시 테이블이 dp 테이블이라고 생각했다. 그래서 계속 solutionRec에서 recursion(0, 0) 호출 종료 후 cache[n - 1][n - 1]을 출력하도록 했는데, cache는 해당 위치에 대한 답이 아니라 같은 입력이 호출된 적 있는지 확인만 하는 부분이었다. 그래서 도착지에 도달한 부분에서는 해당 캐시값을 1로 세팅하는 게 아니라 1을 반환한다. 재귀를 사용할 때는 항상 반환값에 신경써서 작성하자!
[백준] ls (골3) - 2025.2.2
https://www.acmicpc.net/problem/5015
1. 문제 이해하기
- 종만북 1의 218p 와일드 카드 문제와 유사하다.
2. 이론 세우기
- 패턴이 주어지고, 일치하는 파일의 이름을 출력하는 문제이다. 패턴은 *과 알파벳 소문자로만 이루어져 있다. *이 몇 개의 문자열을 포함할 수 있는지 확인하면 된다.
- 패턴과 문자열을 맞춰가다가 패턴에 *이 등장하면 해당 *이 몇 개의 문자열을 포함하는지 확인한다.
3. 이론 검증하기
- w는 와일드카드 패턴, s는 파일 이름이다.
-
- 등장 시 해당 위치에서 호출한 함수는 현재 위치의 문자열 이후로 등장하는 문자열들을 접미사로 가진다. 즉 help의 접미사 는 p, lp, elp, help이다. elp에서 재귀를 호출하면 elp의 접미사인 p, lp, elp를 동일하게 가지므로 메모이제이션을 이용할 수 있다.
- 재귀 함수에서 필요한 정보
- w 시작 위치, s 시작 위치
- cache의 의미
- cache[w][s]는 시작 위치가 w인 와일드카드 패턴과 시작 위치가 s인 파일 이름이 대응되는지 여부를 의미한다.
4. 의사코드 작성하기
**- 재귀 함수**
이미 호출한 접미사라면 캐시값을 그대로 반환한다.
w와 s가 각 범위를 벗어나지 않고, 패턴[w]와 파일[s]가 일치하는 동안 아래 과정을 반복한다.
w와 s를 1씩 증가시킨다.
패턴[w]가 범위를 벗어난다면:
파일도 끝난 경우만 1을 반환한다.
~~파일[s]가 범위를 벗어난다면:
나머지 패턴에 *만 남아있는 경우만 1을 반환한다.~~
현재 패턴이 "*"인 경우:
파일 범위 내에서 skip 값을 0부터 1씩 증가시키며 반복한다.
w + 1를 w, s + skip을 s로 하는 재귀 함수를 호출한다.
반환값이 하나라도 1이라면 1을 반환한다.
캐시[원래 w][원래 s]에 0을 캐싱하고 0을 반환한다.
5. 복기하기
- 추가: while문과 반복문을 사용하지 않고 한 글자씩 이동하며 재귀를 호출하는 방법
- while문 대신 현재 패턴[w]와 파일[s]가 동일하다면 w + 1, s + 1로 재귀 호출
- *을 만나는 경우 반복문 대신 현재 *에 문자 0개나 문자 1개를 포함시키도록 하는 재귀 호출
- *에 문자가 대응되지 않는 경우: (s + 1, w) → 파일이름에서 뺄 문자 없음
- *에 문자를 1개 대응시키는 경우: (s, w + 1) → 현재 *이 다음 문자도 포함시키는 경우는 해당 재귀문에서 다시 호출, 파일[s]의 문자를 하나 사용했으므로 w + 1
**- 재귀 함수** 이미 호출한 접미사라면 캐시값을 그대로 반환한다. 패턴과 파일이 범위 내에 있고 패턴[w]와 파일[s]가 동일한 경우: 재귀함수(w + 1, s + 1)을 호출한다. 패턴[w]가 범위를 벗어난다면: 파일도 끝난 경우만 1을 반환한다. 현재 패턴이 "*"인 경우: 재귀함수(w + 1, s)와 재귀함수(w, s + 1)를 호출해 둘 중 하나라도 1이면 반환한다. 두 번째 재귀를 호출할 때에는 s가 길이보다 작은 경우만 호출한다. 캐시[원래 w][원래 s]에 0을 캐싱하고 0을 반환한다.import sys input = sys.stdin.readline def recursion(w, s, file): # w는 와일드카드 시작 위치, s는 파일 시작 위치 if cache[w][s] != -1: return cache[w][s] if w < W and s < S and p[w] == file[s]: cache[w][s] = recursion(w + 1, s + 1, file) return cache[w][s] if w == W: cache[w][s] = int(s == S) return cache[w][s] if p[w] == "*": if recursion(w + 1, s, file): cache[w][s] = 1 return cache[w][s] if s < S and recursion(w, s + 1, file): cache[w][s] = 1 return cache[w][s] cache[w][s] = 0 return cache[w][s] def solution(): global W, S, cache, p p = input().rstrip() W = len(p) n = int(input()) for _ in range(n): file = input().rstrip() S = len(file) cache = [[-1] * (S + 1) for _ in range((W + 1))] if recursion(0, 0, file): print(file) solution()
[백준] 정수 삼각형(실1) - 2025.2.2
https://www.acmicpc.net/problem/1932
1. 문제 이해하기
- 종만북 226p에 나온 기본 최적화 문제이다.
2. 이론 세우기
- 예전에 이미 풀었었던 문제라 바텀업 대신 탑다운으로 풀어보자.
- 이동 가능한 위치는 아래, 아래 오른쪽 2가지 경우뿐이므로 해당 위치에서 마지막 단계까지 갔을 때 최대합을 비교해 갱신한다. 반환 시에는 두 비교값 중 큰 값과 현재 위치의 값을 반환한다.
- 기저 사례는 현재 위치가 마지막 단계일 때이다. 즉 x == n - 1일 때이다.
- 메모이제이션을 사용하기 위해 cache를 사용한다. n * n 크기에 삼각형 수가 0 이상이므로 방문 이전에는 -1로 초기화한다.
3. 이론 검증하기
- 재귀 함수는 현재 위치 x, y를 필요로 한다.
- 재귀 함수는 현재 위치에서 마지막 단계까지 내려갔을 때 얻을 수 있는 최대합과 현재 위치값의 합을 반환한다.
4. 의사코드 작성하기
**- 재귀 함수**
현재 단계가 마지막 단계라면 현재 위치의 값을 반환한다.
캐시값이 존재하면 해당 값을 반환한다.
캐시에 max(재귀 함수(x + 1, y), 재귀 함수(x + 1, y + 1)) + 현재 위치 값을 저장한다.
현재 캐시값을 반환한다.
5. 복기하기
import sys
input = sys.stdin.readline
def recursion(i, j):
if i == n - 1:
return square[i][j]
if cache[i][j] != -1:
return cache[i][j]
cache[i][j] = max(recursion(i + 1, j), recursion(i + 1, j + 1)) + square[i][j]
return cache[i][j]
def solution():
global n, square, cache
n = int(input())
cache = [[-1] * n for _ in range(n)]
square = [list(map(int, input().split())) for _ in range(n)]
return recursion(0, 0)
print(solution())
- 재귀로 하니까 캐시를 자꾸 까먹는다… 언제 값이 캐시에 저장되는지, 언제 캐시를 사용하는지 생각하면서 코드를 작성하자.
- 시간복잡도 계산하기
- 이론상 둘 다 시간복잡도는 동일(O(n^2))할텐데 바텀업이 절반정도 빠르다고 나왔다.
[프로그래머스] 등굣길(LEVEL 3) - 2025.2.2
https://school.programmers.co.kr/learn/courses/30/lessons/42898?language=python3
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
1. 문제 이해하기
- 종만북에 나온 문제와 유사하다. 중간에 웅덩이만 제외해주면 된다.
2. 이론 세우기
3. 이론 검증하기
4. 의사코드 작성하기
**- 재귀 함수**
기저 사례: n, m이 도착지일 때 1을 반환한다.
메모이제이션 적용: 방문했던 경우 캐시값을 반환한다.
현재 위치에서의 경우의 수를 0으로 초기화한다.
아래쪽, 오른쪽 방향을 순회한다.
범위 내이고 이동할 수 있다면 재귀 함수(n + 1, m)/(n, m + 1)을 호출하고 해당 반환값을 경우의 수에 더한다.
현재 위치 캐시값을 저장한 뒤 반환한다.
**- 호출 함수**
캐시를 -1로 초기화한다.
puddles를 순회한다.
좌표에서 puddle의 위치를 이동 불가능으로 표시한다.
재귀 함수(0, 0)을 호출하고 반환값을 출력한다.
5. 복기하기
D = [(1, 0), (0, 1)]
DIV = 1000000007
def route(i, j, m, n, grid):
if i == n - 1 and j == m - 1:
return 1
if cache[i][j] != -1:
return cache[i][j]
ret = 0
for di, dj in D:
ni, nj = i + di, j + dj
if ni < n and nj < m and grid[ni][nj]:
ret += (route(ni, nj, m, n, grid) % DIV)
cache[i][j] = ret % DIV
return ret
def solution(m, n, puddles):
global cache
grid = [[True] * (m) for _ in range(n)]
cache = [[-1] * (m) for _ in range(n)]
for j, i in puddles:
grid[i - 1][j - 1] = False
answer = route(0, 0, m, n, grid)
return answer
- 정확성은 맞았는데 효율성은 틀렸다. 크기는 m이 100, n이 100이기 때문에 O(mn) 즉 O(10^4)인데, 왜 효율성 오류가 나는 거지..?
- ㅋㅋ 재귀함수 return 시 모듈러 연산을 해준 cache[i][j]가 아니라 기존 ret을 리턴하고 있었다…
[백준] 다리 놓기(실5) - 2025.2.3
https://www.acmicpc.net/problem/1010
1. 문제 이해하기
- 경우의 수를 구하는 DP 문제이다.
2. 이론 세우기
- 오른쪽에 있는 m개 중에서 n개의 점을 선택하면 왼쪽의 n개 점과 연결하는 방법은 1개뿐이다(다리끼리 교차할 수 없으니 위에서부터 차례대로 연결한다).
- 따라서 m개 중 n개의 점을 선택하는 조합의 수와 동일하다.
3. 이론 검증하기
- 너무 모르겠어서 재귀 풀이를 찾아보았다…
4. 의사코드 작성하기
**- 재귀 함수**
n이 m과 동일하다면 경우의 수는 하나뿐이므로 1을 반환한다.
n이 1이라면 경우의 수는 n과 나머지 m을 순서대로 연결하는 경우의 수만 존재하므로 m을 반환한다.
캐시값이 존재한다면 그대로 반환한다.
재귀 호출(n - 1, m - 1) + (n, m - 1)을 현재 캐시값으로 저장한다.
현재 캐시값을 반환한다.
5. 복기하기
import sys
input = sys.stdin.readline
def bridge(n, m):
if n == m: # n <= m 유지
return 1
if n == 1:
return m
if cache[n][m] != -1:
return cache[n][m]
ret = bridge(n - 1, m - 1) + bridge(n, m - 1)
cache[n][m] = ret
return cache[n][m]
def solution():
global cache
n, m = map(int, input().split())
cache = [[-1] * (m + 1) for _ in range(n + 1)]
return bridge(n, m)
t = int(input())
for _ in range(t):
print(solution())
- 가장 위 1쌍을 연결하며 n - 1, m - 1을 호출한다.
- n이 1이라면 연결할 수 있는 경우의 수는 m개이고 이것이 기저 사례이다.
- m을 하나씩 제거하며 n, m - 1을 호출한다.
- n과 m이 동일하다면 연결할 수 있는 경우의 수는 1개이다(순서대로).
- 메모이제이션을 유지하면 O(n*m) 시간으로 풀 수 있다.
- 결론적으로 bridge(n - 1, m - 1), bridge(n, m - 1)가 배타적인 이유는,
- 왼쪽 첫 번째 점과 오른쪽 첫 번째 점을 잇는 경우 1
- 왼쪽 첫 번째 점과(왼쪽 점은 모두 이어져야 하므로) 오른쪽 두 번째 점(즉 오른쪽 첫 번째 점을 선택하지 않음)을 잇는 경우 2
- 왼쪽 점을 기준으로 보았을 때 오른쪽 첫 번째 점을 선택하거나 선택하지 않거나의 두 가지 방법만 존재하기 때문이다. (누락 없음)
- 또한 두 가지 경우에 모두 포함되는 방법은 없다. (중복 없음)
