일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- effective C++
- Silver
- two pointer
- 8-Puzzle
- level3
- Zenject
- C++11
- programmers
- smart pointer
- Bronze
- LEVEL2
- level1
- algorithm
- binary search
- trie
- stack
- Project
- 프로그래머스
- 3D RPG
- Unity
- SWEA
- algoritm
- Modern C++
- BFS
- Euclidean
- knapsack Problem
- PrefixSum
- Gold
- BOJ
- Greedy
- Today
- Total
Patrick's Devlog
[Algorithm] 백트래킹(Backtracking) 본문
1. DP vs Backtracking
DP는 problem과 sub-problem을 나누어 진행하고, 이 sub-problem은 더 작은 sub-problem으로 나누어 질 수 있다. 겹치는 sub-problem은 memorization을 통해 저장하면서 중복된 계산을 줄여갔다.
그러나, Backtracking은 우리가 가져갈 수 있는 모든 경우의 수를 하나씩 살펴보고, Decision space를 만들어 나간다. 여기서 어떠한 경우의 수가 의미가 없게되면 가지치기를 하게 되고 backtracking을 하면 된다.
2. Backtracking
ex> Phone keypad 문제(leetcode 17)
우리가 아는 휴대폰의 키패드는 아래의 사진과 같다.
"25"가 입력이 되었을 때, AJ / AK / AL / BJ / BK / BL / CJ / CK / CL라는 알파벳이 나올 수 있다. 여기서 HashMap으로 예를 들자면, {1 : null, 2 : [a, b, c], 3 : [d, e, f] ... , 9 : [w, x, y, z]}가 된다. 숫자는 key값이 되고, 알파벳은 value가 된다. 이때 "259"라는 숫자가 input으로 들어왔다는 가정을 해보자.
2같은 경우는 [a, b, c] 가 있는데 이 세 가지 모두가 decision space가 된다. 이처럼 가지를 내려가면 아래의 그림처럼 경우의 수를 나타낼 수 있다.
실제 코드는 당연히 하나의 단계씩 진행될 것이다. 이를 모든 경우로 정리해보면 ajw, ajx, ... 이런식으로 할 수 있다. DP같은 경우는 DP Array, Table을 채워나간다고 생각하면 구현가능하지만, Backtracking은 위의 그림을 코드로 나타내기에는 어려울 수 있다. 우리는 위의 내용을 코드로 쉽게 확인하기 위해 수도 코드를 확인할 수 있다.
input : input (ex> "259")
output : output
def Backtracking(index : 몇번째 숫자인지, letter(depth) : 몇번째 단계까지 만들어졌는지) {
// 초기 index는 0, letter은 ""
if (index >= input의 length) {
output.add(letter)
}
num = input[index]
chars = Hashmap[num] <- a, b, c / j, k, l / w, x, y, z
for (c : chars) {
Backtracking(index + 1, letter + c) // 재귀
erase(c) // 백트래킹이 끝난 경우 c를 지워주는 코드를 넣어야 함
}
}
이론 자체는 어렵지 않지만, 많이 응용해보고 연습해야 손에 익을 것 같다.
참고문서
https://www.youtube.com/watch?v=Ar40zcPoKEI
'Study > Algorithms & Data Structure' 카테고리의 다른 글
[Algorithm] Dijkstra Algorithm(다익스트라 알고리즘) (0) | 2022.11.08 |
---|---|
[Algorithm] Greedy (0) | 2022.10.27 |
[Algorithm] DFS/BFS (0) | 2022.07.12 |
[Algorithm] 이진 탐색 (0) | 2022.06.29 |
[Algorithm] Knapsack Problem (0) | 2022.06.22 |