[코드트리 조별과제] 백트래킹 (Python) - 8월 1주차

👀  백트래킹(Backtracking)

 

 

정처기 보고 땡땡이친 사이에 우리 학교 이용권이 사라질 위기에 처했다.

누추한 글이라도 기간 안에 인증되기를🙏 (plz)

 

 

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition/introduction

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

오늘은 백트래킹에 대한 글이다.

백트래킹의 핵심은 재귀를 돌리는 도중에, 다음 depth의 함수를 호출한 뒤 '갱신 취소' 하는 것이라고 생각한다.

 

 

 

 

다음과 같은 코드를 이해하지 못하면 백트래킹이 어렵다. 

내가 그렇다.

def choose(i):
	•••중략•••
    for j in range(k):
        if ps[j] < m:
            ps[j] += turns[i]
            choose(i + 1)
            ps[j] -= turns[i]

 

Q. 재귀함수에 다음 depth를 실행하고 → 왜 갱신한 값을 취소하는가?

 

A. ps[j]가 갱신된 상태에서 재귀를 호출했으니, ps[j]가 갱신되지 않은 상태에서도 재귀를 한 번 호출해야 하기 때문이다.

 

백트래킹은 '선택하는 경우의 수'를 구하는 문제에서 사용되는 경우가 많다. 순열/조합을 만드는 용도로 사용되는 것이 백트래킹 알고리즘이다. (삼성 코테보러 가면 파이썬의 itertools를 사용할 수 없다. 순열이나 조합이 필요하면 백트래킹으로 직접 만들어 써야 한다)

 

예시로, 1~10번의 출석번호를 가진 학생들이 10명 있는 교실에서 3명의 학생을 교무실로 호출해야 한다 가정해보자. 

for 문 안에서 바로바로 학생을 선택해 재귀를 호출해버리면 결과는 [1, 2, 3] 하나뿐일 것이다. 

예를 들어 2번을 선택한 뒤 재귀를 돌렸다면, 2번을 선택하지 않은 상태에서도 함수가 호출되어야 한다. 

 

나는 이 개념이 확 와닿지 않아서 여러 개의 가능세계라고 생각하기로 했다. 

2번이 선택된 가능세계에 재귀를 날렸다면 당연히 2번이 없는 가능세계도 열어줘야 하느니........

 

😇

 

 

관련된 문제를 소개한다.

 

 

K개 중 하나를 N번 선택하기(Conditional) / 1차원 윷놀이

https://www.codetree.ai/missions/2/problems/yutnori-1d/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

제출한 코드

n, m, k = list(map(int, input().split()))
turns = list(map(int, input().split()))

locations = [1 for _ in range(k)]
max_score = 0

def choose(i):
    global max_score
    score = 0
    for loc in locations:
        if loc >= m:
            score += 1

    max_score = max(max_score, score)
    if i == n:
        return
    for j in range(k):
        if locations[j] < m:
            locations[j] += turns[i]
            choose(i + 1)
            locations[j] -= turns[i]

choose(0)
print(max_score)

 

 

위처럼 전역으로 사용되는 변수를 갱신했다가 취소했다가 하면서 재귀를 돌려야 하는 문제도 있고,

재귀의 파라미터로 계속 이번 선택을 넘기면서 함수를 호출해야 하는 문제도 있다. 이 경우, 중단조건에 걸리면 전역으로 선언한 리스트에 결과를 append하고 리턴하는 것이 일반적이다. 

 

정확히 어떤 케이스에 어떤 방식을 이용해야 하는지 정리하기엔 아직 확신이 없다. 문제를 보고 판단한다. ✨

 

백트랙 에브리띵~^^