[항해99 취업 리부트 코스 학습일지] Day 9 - 알고리즘 : 백트래킹

[팀스터디에서 얻은 인사이트]

중요한건 각 알고리즘이나 문제 장르에서 공식적으로 들어가는 풀이 방법이 있다. 그 방법을 확실히 인지하기만 해도 대부분의 알고리즘 문제는 큰 틀에서 벗어나지 않는다. 정확히는 코딩테스트에서 출제하는 문제들은 그 틀에서 벗어나는 문제는 잘 출제되지 않는다. 그 공식을 얻으려고 하자

---

[학습 내용]

백준 문제 N과 M 문제를 처음에는 멘토님이 가르쳐주시지 않았더라면 파이썬에 있는 itertools를 이용해서 그저 단순하게 순열과 조합으로 풀어버렸을지도 모른다. 하지만 분명하게 백트래킹 문제라고 인지를 시켜주시고 해답을 알려주셨는데 제대로 공부한 적이 없어 코드의 실행 과정을 이해하는데 애를 먹었다.

백준 15649 N과 M(1)

15649번: N과 M (1)

# 백트래킹 : 재귀함수를 이용하여 모든 경우의 수를 탐색하는 방법. 다만, 불필요한 경우의 수를 탐색하지 않도록 가지치기(뒤로 돌아가기)를 해야 함.
from sys import stdin
read = stdin.readline

# n : 1부터 n까지의 자연수 중에서
# m : 중복 없이 m개를 고른 수열
n, m = map(int, read().split())
# 방문 여부를 체크할 리스트(중복 방지)
visited = [False] * n
answers = [] # 정답을 쌓아두는 배열(최적화를 위해 리스트에 담아 한번에 출력)
answer = []

def back_tracking(index, n, m):
    # index가 m과 같아지면 answer를 출력하고 함수를 종료
    if index == m:
        # answer에 추가 후
        answers.append(' '.join(map(str, answer)))
        return # 해당 branch는 제거
    for i in range(n):
        if not visited[i]:
            visited[i] = True
            answer.append(i+1)
            back_tracking(index+1, n, m)
            visited[i] = False
            answer.pop()

back_tracking(0, n, m)
print('\n'.join(answers))

ㅁ

백트래킹은 기본적으로 트리 기반의 탐색 방법 중 하나로 DFS, BFS와 유사하다. 다만 차이가 있다면 DFS, BFS는 전체를 다 탐색하지만 백트래킹은 모든 부분을 탐색하는 것이 아니라 탐색할 필요가 없는 상태를 제외하는 가지치기를 한다. 즉 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴본다. 
앞에서 말했던 순열과 조합도 사실 백트래킹의 예 중 하나라고 할 수 있다. 이걸 인지하고 코드를 확인하자.

• N과 M을 4,2라고 가정하자.
• 정답을 쌓는 배열과 방문기록을 담는 리스트를 만든다.
• M개를 고른 수열을 뽑을 것이기 때문에 M보다 더 고른 수열은 고려할 필요가 없다. 따라서 back_tracking 함수 내부에 if index == m으로 정지조건을 먼저 확정짓는다.
• 이제 순환하면서 방문하면 배열의 인덱스를 True로 변경하고, answer에 1부터 넣는다.
  • 재귀함수로 [1] 로 시작하는 수열 중에 맞는 수열을 찾는다.
  • 0번 인덱스는 True이므로 if 문 이하는 실행하지 않는다.( [1, 1]의 수열은 없다 )
  • 1번 인덱스(값은 2)를 True로 바꾸고 answer에 2를 넣는다.([1,2])
  • 그 이하(재귀함수)를 탐색하려 하지만 정답 배열의 길이가 이미 2이므로 정답 리스트에 넣고 탈출한다.
  • 1번 인덱스는 False로 변경하고 answer의 2는 제거한다.
  • 반복문을 통해 2번 인덱스(값은 3)을 True로 바꾸고 answer에 3를 넣는다([1,3])
  • 그 이하(재귀함수)를 탐색하려 하지만 정답 배열의 길이가 이미 2이므로 정답 리스트에 넣고 탈출한다.
  • 2번 인덱스는 False로 변경하고 answer의 3는 제거한다.
  • 반복문을 통해 3번 인덱스(값은 4)을 True로 바꾸고 answer에 4를 넣는다([1,4])
  • 그 이하(재귀함수)를 탐색하려 하지만 정답 배열의 길이가 이미 2이므로 정답 리스트에 넣고 탈출한다.
  • 3번 인덱스는 False로 변경하고 answer의 4는 제거한다.
  • 재귀함수를 다 돌았으므로, 나와서 0번 인덱스(값은 1)를 False로 바꾸고 1을 제거한다.
  • 2로 시작하는 수열을 다시 탐색한다

위 과정을 계속 반복한다. 이런 로직을 통해서 순서대로 방문했던 곳은 방문하지 않고 차례대로 해결해나간다.

---

문제점

• 재귀함수 자체를 많이 겪어보지 않아서 코드의 구조를 이해하는게 너무 힘들었다.
• 백트래킹이라는 개념과 탐색이라는 개념이 알고리즘에서 어떻게 이루어지는지 잘 알지 못해 기반 개념부터 학습하려다보니 더 어려웠다.

해결책

• 재귀함수 문제를 우선시 풀고, 그 뒤에 백트래킹 관련 문제를 더 푼다.
• 완전탐색, BFS, DFS, 그래프에 대해서 알아보고 로직이 어떻게 흘러가는지 이해하며, 백트래킹과 어떤 부분이 다른지 이해하자. 

---

 

강의 이외에 아래 블로그가 가장 설명을 초보자도 이해하기 쉽게 잘 적어놓은 것 같아 참조했다.

백트래킹(Backtracking)이란?

---

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠입니다.

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지