완전탐색 알고리즘
탐색 알고리즘과 완전탐색은 다르다. 완전 탐색은 정답이 될 가능성이 있는 모든 후보를 체계적(반복문, 재귀, 비트마스크 등)으로 확인하는 것. 탐색 알고리즘은 원하는 값을 탐색하는 과정을 의미한다.
탐색 알고리즘
1.
선형탐색
2.
이진탐색
3.
비선형 탐색 (DFS, BFS)
완전 탐색
1.
반복문
2.
재귀
3.
비트마스크
1. 백트래킹 활용한 완전탐색
solution이 될 가능성이 없는 후보는 더 이상 탐색하지 않고 후보를 포기(BackTrack)하면서 탐색. 하나의 답이 나오는 문제의 유형의 경우 백트래킹 활용이 가능하다.
2. DP 활용한 완전탐색
중복계산을 줄이면서 완전탐색. 모든 경우의 수를 따져야 한다면 백트래킹이 불가능하다. 따라서 DP를 활용해서 최적화를 하는 방법을 생각해보자.
구현
1. 순열
Python 코드
def permutation(nums):
def backtrack(cur):
if len(cur) == len(nums):
ans.append(cur[:])
return
for num in nums:
if num not in cur:
cur.append(num)
backtrack(cur)
cur.pop()
ans = []
backtrack([])
return ans
print(f"==>> permutation(4): {permutation([1, 2, 3, 4])}")
Python
복사
2. 조합
Python 코드
def permutation(nums):
def backtrack(cur):
if len(cur) == len(nums):
ans.append(cur[:])
return
for num in nums:
if num not in cur:
cur.append(num)
backtrack(cur)
cur.pop()
ans = []
backtrack([])
return ans
print(f"==>> permutation(4): {permutation([1, 2, 3, 4])}")
Python
복사
3. 부분집합
Python 코드
def solution(nums):
def backtrack(k, start, cur):
if len(cur) == k:
ans.append(list(cur))
return
for i in range(start, len(nums)):
cur.append(nums[i])
backtrack(k, i+1, cur)
cur.pop()
ans = []
for i in range(len(nums)+1):
backtrack(i, 0, [])
return ans
print(f"==>> solution: {solution([1, 2, 3, 4])}")
Python
복사