❗유투브 채널 "코드없는 프로그래밍"의 [코딩테스트, 기초, 백트래킹 backtracking 소개]를 공부하며 정리한 내용입니다.
백트래킹이란?
➡️ 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
🟡 DP Array와 DP Table을 이용하여 중복 연산을 줄여가는 DP와 달리, 백트래킹은 Decision Space로 고려할 수 있는 모든 경우의 수를 탐색한다.
예시 문제(Phone keypad)
👀 어떤 숫자를 순서대로 입력하였을 때 나올 수 있는 알파벳 조합의 경우 구하기
ex) 2를 입력하면 >> A, B, C 출력
🔅 특정 key값에 대한 값이 따라오므로 hashmap으로 저장한다.
"259"가 입력되었을 때의 Candidate space
- 코드로 구조화 해보기(rough)
# 결과값을 저장할 array와 후보군 Hashmap은 global로 선언되었다고 가정한다.
def BT(index, letter) :
if index >= 입력값의 길이 :
outputArry.append(letter)
return outputArry
num = 입력값[index] # input값 중 현재 가리키고 있는 값
chars = Hashmap[num] # 해당 숫자가 가리키고 있는 알파벳 배열
for c in chars :
BT(index+!, letter+c)
letter에서 추가된 c 지우기
- index = 0, letter = ""
num = 2
chars = [a, b, c]
* for문
◾ BT(1, ""+a)
◾ BT(1, ""+b)
◾ BT(1, ""+c)
... 이런식으로 진행된다.
‼️ 주의 할 점
-
함수의 인자인 letter가 deepcopy 되는 것을 막기 위해 outputArry에 letter를 추가할 때 letter가 deepcopy된 object를 넣어주어야 한다.
-
함수의 인자로 넘겨지는 letter가 value인지 refer인지를 인지하고 있어야 한다.
-
function call이 발생할 때마다 copy가 일어나는지, 레퍼런스가 넘겨지고 있는지 구분할 수 있어야 한다.
👀 파이썬의 메모리 모델 공부 필요..
🔹시간 복잡도
- 한번의 호출로 이루어지는 연산은 O(1)(if문 제외)
- O(1)의 계산이 층마다 3번씩 이루어짐
- 층이 n개라면 3^n 번의 연산
- if문의 letter가 copy되는 부분이 n번 발생
- 따라서 총 n*3^n번의 연산
➡️ 시간 복잡도 = O(n3^n)
🔹 공간 복잡도
- 각 단계마다 함수 호출이 일어날 때 copy가 아닌 reference만 넘겨진다면 각 단계의 첫 번째 알파벳만 저장되면 되기 때문에 O(n)으로 볼 수 있다.
(이해 안됨..)
🔅 출처 🔅
