[알고리즘 공부] #2 백트래킹(BackTracking) 알고리즘 with Python

백트래킹 알고리즘(BackTracking)

어떤 알고리즘일까?

백트래킹 알고리즘은 비선형으로 구성된 자료 구조를 깊이 우선으로 탐색할 때, 더 이상 탐색할 수 없는 상황에서 이전 단계로 돌아가는 알고리즘을 말한다.

출처 : 백트래킹 알고리즘 블로그 글

위에 사진을 보면 4번 자료까지 탐색한 후 더 이상 탐색할 길이 없어 2번 자료로 돌아가는 것을 알 수 있다. 이런 알고리즘을 백트래킹 알고리즘 이라고 한다.

 

장점과 단점

• 장점
  백트래킹 알고리즘은 발생 가능한 모든 경우의 수를 탐색하기 때문에 100%확률로 조건에 맞는 값을 구할 수 있다는 장점이 있다.
• 단점
  백트래킹 알고리즘도 완전 탐색 알고리즘의 일부분으로써 모든 경우의 수를 탐색해야 한다는 점에서 데이터의 양이 많아지면 시간이 오래 걸리고 비효율적이라는 단점이 있다.

언제 사용하는가?

• 탐색문제
  그래프나 트리와 같은 자료구조에서 모든 경로를 탐색할 때 주로 사용된다.
• 조합문제
  조합적 문제에서 가능한 모든 조합을 찾거나, 조건에 만족하는 모든 조합을 찾는 경우에 백트래킹을 주로 사용한다. 예를 들어 N개의 요소 중에서 M개를 선택하는 경우의 수를 모두 찾는 문제가 이에 해당한다.
• 구해야 하는 값의 특별한 규칙이 없을 경우
  특별한 규칙이 없을 경우 사용하는 이유는 그 값을 구하기 위한 특별한 방법이 없기 때문에 전체 영역을 탐색할 수 밖에 없기 때문이다.

알고리즘 사용 예제

중복되지 않는 5개의 수에서 2개 수 조합을 모두 구하기

• 문제 설명
  중복되지 않는 5개의 수에서 2개 수 조합을 모두 구하기 위해서는 백트래킹 알고리즘을 사용해야 한다.
  먼저 5개의 수를 1,2,3,4,5라고 가정하자.
  처음에 1을 기준으로 조합을 구해보면 (1,2) → (1,3) → (1,4) → (1,5) 이런식으로 진행될 것이다.
  하지만 (1,5) 이후에 더 이상 탐색할 길이 없으므로 이전 단계인 기준인 수를 정하는 단계로 돌아와 1이 아닌 다른 수를 기준으로 정한다.
  그 후 다시 조합을 구하면 (2,1) → (2,3) → (2,4)→ (2,5)가 될 것이다.
  
  문제 작동 방식을 한번에 정리하자면,
  (1,2) → (1,3) → (1,4) → (1,5) → (백트래킹) → (2,1) → (2,3) → (2,4) → (2,5)
  위와 같은 방식으로 진행된다.
• 알고리즘 사용
  2개 수 조합을 찾기 위해서는 어떤 수를 기준으로 조합을 구하다가 더 이상 탐색할 길이 없을 때 이전 단계로 돌아와 기준이 되는 수를 바꿔야 한다. ← 백트래킹 알고리즘이 사용되는 부분 
• CODE

N = [1,2,3,4,5]
 
for i in N:
    for j in N:
        if i != j:
            print("(" + str(i) + "," + str(j) + ")")

---