[코드트리] 백트래킹 개념 정리 및 이해하기

 if len(arr) >= 2 and arr[-1] == num and arr[-2] == num:
      continue

코드트리에서 현재 학습하고 있는 개념은 백트래킹이다. 가능한 경우의 수를 탐색하는 방법인데, 조금 특이한 점은 '가지치기'이다. 즉, 탐색 도중 답이 될 수 없으면 다시 부모 노드로 되돌아가서 탐색을 시작하는 것이다.

 

백트래킹에서 가장 흔하게 쓰이는 기술은 '재귀함수'다. 그리고 부모 노드로 되돌아간다는 점이 큰 포인트인데, 코드를 구현할 때 pop()을 해서 원 상태로 복귀하는 코드가 많이 쓰인다. 또한 재귀함수이듯 탐색 제한 조건을 무조건 명시해야 한다. 이로써 불필요한 낭비를 줄이는 것이다.

 

예시로 코드트리의 한 문제를 보며 이해해보자.

 

 

숫자를 뽑고 서로 다른 순서쌍을 구하는 문제이다. 순서쌍을 추가해주어야 하기 때문에 arr 배열을 하나 만들 것이고, 제한 조건으로 N개를 골라야 하기 때문에 현재 숫자가 N일 때 그만 찾는다는 조건을 걸어주면 된다.

 

if curr_num == N:
        print(*arr)
        return

 

순서쌍을 출력하는 것이라 배열을 그대로 출력해 주기 위해 *arr를 사용했다.

 

그 다음은, 연속하여 같은 숫자가 3번 이상 나오는 경우는 제외한다는 조건인데, 배열을 돌면서 조건을 수행해야 한다. 

 

 if len(arr) >= 2 and arr[-1] == num and arr[-2] == num:
      continue

 

배열 크기가 3이고, 3개의 숫자가 같으면 배열을 만들지 않는다는 의미이다. 이 조건을 수행하고, 재귀 함수를 수행한 다음 원 상태로 pop() 해주면 기본 골격이 완성된다. 아래는 완성 코드다.

 

K, N = map(int, input().split())
arr = []

def choose(curr_num):
    if curr_num == N:
        print(*arr)
        return

    for num in range(1, K + 1):
        if len(arr) >= 2 and arr[-1] == num and arr[-2] == num:
            continue
        
        arr.append(num)
        choose(curr_num + 1)
        arr.pop()

choose(0)

 

 

아직도 조건이나 제한조건을 설정하는게 참 어렵지만 정작 정답코드를 보면, 스스로 생각할 수 있을 법한 코드이다. 겁먹지 말고 차근차근 도전하다 보면 스스럼 없이 풀 수 있는 날이 오겠지?

 

백트래킹에서 가장 중요한 점은 위에서 설명했듯 '제한 조건' 과 '조건'이다. 이 부분을 늘 유념하면서 백트래킹 문제를 대해야 한다. 

 

https://www.codetree.ai/accounts/sign-up-only?referralCode=pjy2163

Codetree: Master Coding Interviews - Data Structures & Algorithms

https://www.codetree.ai/ko

Codetree: Master Coding Interviews - Data Structures & Algorithms