DP와 백트래킹 차이점
DP
dp는 하나의 problem을 작은 sub problem으로 쪼개어 해결한다.
그 과정에서 중복되어 나타나는 sub problem을 memoization하여 불필요한 연산을 줄일 수 있다.
백트래킹
정의된 Decision Space에서 모든 경우를 하나씩 tracking하면서 또다른 Decision Space를 만들어간다.
tracking 과정에서 조건에 부합하지 않는 부분은 더이상 진행하지 않고 back tracking 하여 다른 경우를 살펴본다.
(이 과정이 brute force 알고리즘과 다른 점이다.)
Phone Keypad 문제
259숫자가 나타낼 수 있는 모든 알파벳 조합을 구하는 문제이다.
| 숫자 | 알파벳 |
|---|---|
| 2 | a b c |
| 5 | j k l |
| 9 | w x y z |
이 데이터를 hash map로 저장한다.
처음2,5,9 3가지 경우가 decision space가 된다.
-
2👉a, b, c3가지가 decision space이다.
이제 a, b, c 각각의 case에 대해 또 다시 decision space를 구할 수 있다. -
a가 선택이 된 경우,
5👉j k l3가지가 decision space가 된다. (b, c가 선택이 된 경우도 마찬가지이다) -
a, j가 선택이 된 경우,
9👉w x y z4가지가 decision space가 된다 (k, l이 선택이 된 경우도 마찬가지이다)
이와 같이 모든 후보 공간(candidate space)들을 하나씩 탐색해 간다
- 모든 공간을 훑어보기 때문에 놓치는 경우가 없다
- 살펴볼 필요가 없는 경우는 더이상 탐색하지 않으므로 brute force 방식보다 빠르다.
코드
수도코드
input "259"
output array
global HashMap 데이터
def BT(index, letter):
# index : input 변수에서 탐색중인 문자열의 인덱스
# letter : 현재 까지 만들어진 문자열을 담는 변수
if index >= len(input):
array.append(letter)
return
num = input[index] # 2, 5, 9 중 하나
chars = HashMap[num] # num이 2라면 chars는 a,b,c이다.
for c in chars:
BT(index + 1, letter + c)
코드
from typing import List
class Solution:
def __init__(self):
self._keypad = None
self._digits = None
self._comb = None
def letterCombinations(self, digits: str) -> List[str]:
self._keypad = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
if len(digits) == 0:
return []
self._digits = digits
self._comb = []
self._BT(index=0, crntStr=[])
return self._comb
def _BT(self, index: int, crntStr: List[str]):
if index >= len(self._digits):
self._comb.append("".join(crntStr))
return
num = int(self._digits[index])
chars = self._keypad[num]
for c in chars:
crntStr.append(c)
self._BT(index + 1, crntStr)
crntStr.pop()
letterComb = Solution()
print(letterComb.letterCombinations(digits="259"))Subset 문제
https://www.youtube.com/watch?v=gVijWUHWzAU
[1, 2, 3]의 부분집합을 구하는 문제이다.
코드
수도코드 : 재귀
def BT(index, letters[]):
if index == len(letters):
output.append(letters)
return
c = input[index] # 1, 2, 3 중 하나
BT(index + 1, letters + c) # 1이 선택된 경우 (오른쪽)
BT(index + 1, letters) # 1이 선택되지 않는 경우(왼쪽)C++에서는 letters 파라미터로 값이 넘겨진다. (by deepcopy)
def BT(index, letters[]):
if index == len(letters):
output.append(letters.copy())
return
c = input[index] # 1, 2, 3 중 하나
letters = letters + c # letters에 c를 추가한다
BT(index + 1, letters)
letters.remove(last) # c를 다시 없애준다.
# 여기까지가 1이 선택이 된 경우를 고려한 것이다.
# 마지막에 c를 없애 주어야 한다.
# 왜냐하면 밑의 코드에서 1이 선택되지 않은 경우를 고려할 수 있게 해야하기 때문이다.
BT(index + 1, letters) # 1이 선택되지 않는 경우(왼쪽)하지만 python, java에서는 letters 파라미터로 참조값이 넘어간다.
- 재귀 함수가 진행되면서 stack에는 letters를 가리키는 참조값이 들어간다.
- 값을 복사하여(deepcopy) 넘겨주는 것보다 참조값을 변경하는 방식이 더 빠르다.
수도코드 : iterative한 방식 (stack)
def subset():
stack.push(0, "")
while stack:
level, letters = stack.pop()
if level == len(input):
output.append(letters)
continue
c = input[level]
stack.push(index + 1, letters) # 공집합을 선택한 경우
stack.push(index + 1, letters + c) # 실제 letter를 선택한 경우코드
from typing import List
class Solution:
def __init__(self):
self._output = None
self._nums = None
def subsets(self, nums: List[int]) -> List[List[int]]:
self._nums = nums
self._output = []
self._BT(0, [])
return self._output
def _BT(self, index: int, nums: List[int]):
if index == len(self._nums):
self._output.append(nums.copy())
return
num = self._nums[index]
nums.append(num)
self._BT(index + 1, nums)
nums.pop()
self._BT(index + 1, nums)Permutation 문제
https://www.youtube.com/watch?v=lhy9mtUqZGc&list=PLDV-cCQnUlIaAKZbfdkMU01MrMkeTvVgP&index=4
위와 같이 탐색트리를 만들어보면 크게 어렵지 않다.
코드
수도코드
def BT(level, letters[]):
if level == len(input):
output.append(letters.copy())
return
for c in input[]:
if c not in letters: # 중복된 문자를 가진 경우를 거르기 위함
letters += c
BT(level + 1, letters)
letters.remove(last)코드
from typing import List
class Solution:
def __init__(self):
self._nums = None
self._output = None
def permute(self, nums: List[int]) -> List[List[int]]:
self._nums = nums
self._output = []
self._BT(0, [])
return self._output
def _BT(self, index: int, num_list: List[int]):
if index == len(self._nums):
self._output.append(num_list.copy())
return
for c in self._nums:
if c not in num_list:
num_list.append(c)
self._BT(index + 1, num_list)
num_list.pop()
solution = Solution()
print(solution.permute(nums=[1, 2, 3]))
Combination 문제
코드
수도코드
def BT(index, start, numbers[]):
if index == len(input):
output.append(numbers.copy())
return
n = len(numbers)
for i in range(start, len(input)):
numbers.append(input[i])
BT(index + 1, i + 1, numbers)
numbers.remove(last)코드
from typing import List
class Solution:
def __init__(self):
self._k = None
self._output = None
self._nums = None
def combine(self, n: int, k: int) -> List[List[int]]:
self._k = k
self._nums = [i for i in range(1, n + 1)]
self._output = []
self._BT(0, 0, [])
return self._output
def _BT(self, index: int, start: int, num_list: List[int]):
if index == self._k:
self._output.append(num_list.copy())
return
for i in range(start, len(self._nums)):
c = self._nums[i]
num_list.append(c)
self._BT(index + 1, i + 1, num_list)
num_list.pop()
solution = Solution()
print(solution.combine(4, 2))
print(solution.combine(5, 3))
