[Algorithm] Brute-force(완전탐색) , Backtracking(백트래킹)

완전탐색(Brute-force)

완전탐색은 굉장히 단순한 아이디어이다. 답을 찾기 위해 모든 경우를 다 살펴 본다는 전략으로 확실하게 반드시 답을 찾을 수 있다는 장점이 있다. 그러나 모든 경우를 다 살펴 보므로 시간이 오래 걸린다는 게 단점이다. 아무리 컴퓨터의 연산 속도가 빠르다지만, 탐색 범위가 너무 넓거나 필요한 연산 수가 많다면 한참이 걸려도 답이 나오지 않는다. 

 

백트래킹(Backtracking)

백트래킹을 활용한 대표적인 문제풀이 전략은 스도쿠이

원하는 정답을 찾기 위해 모든 경우를 골라보며 완전탐색을 하는 알고리즘이다. 백트래킹은 DFS,BFS와 같은 완전탐색 방식이지만, 진행 과정에서 답이 아닌 분기를 만나면 탐색을 진행하지 않고 돌아가 다른 분기로 감으로써 가지치기를 한다는 차이가 있다.  

백트래킹은 DFS와 비슷하지만 전체를 탐색하는 깊이 우선 탐색과 달리 백트래킹은 전체를 탐색하지 않는 다는 점에서  다르다. 

15663번: N과 M (9) (acmicpc.net)

15663번: N과 M (9)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n,m = map(int,input().split())
arr = sorted(map(int,input().split()))
visited = [False] * n
result = []

def dfs() :
    # 길이가 m인지 확인 
    if len(result) == m :       
        print(*result)
        return
    # 중복 체크
    remember = 0
    # dfs 실시
    for i in range(n) :
        if visited[i] == False and remember != arr[i] :
            visited[i] = True
            result.append(arr[i])
            remember = arr[i]
            dfs()
            visited[i] = False
            result.pop()
            
dfs()

순열(permutation)과 조합(combination)

순열과 조합은 경우의 수를 구할 때 유용하게 사용되는 개념이다.  우선 순열(permutation)은 순서를 고려하여 뽑는 경우의 수를 의미한다. n개의 수중에서 r개를 뽑아 줄을 세우는 총 방법의 수는

 

이다. python에서는 itertools의 permutations를 import 후 사용하면 된다(from itertools import permutations). python의 permutations는 몇 개를 고를지도 선택할 수 있다. 함수 인자 2번째 값으로 전달하면 된다. 

from itertools import permutations

arr = [0,1,2,3]

for i in permutations(arr,4) :
  print(i)

(0, 1, 2, 3)
(0, 1, 3, 2)
(0, 2, 1, 3)
(0, 2, 3, 1)
(0, 3, 1, 2)
(0, 3, 2, 1)
(1, 0, 2, 3)
(1, 0, 3, 2)
(1, 2, 0, 3)
(1, 2, 3, 0)
(1, 3, 0, 2)
(1, 3, 2, 0)
(2, 0, 1, 3)
(2, 0, 3, 1)
(2, 1, 0, 3)
(2, 1, 3, 0)
(2, 3, 1, 0)
(3, 0, 1, 2)
(3, 0, 2, 1)
(3, 1, 0, 2)
(3, 1, 2, 0)
(3, 2, 0, 1)
(3, 2, 1, 0)

ex) baekjoon - 15649

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

from itertools import permutations

N, M = map(int, input().split())
items = [i for i in range(1,N+1)]
for i in permutations(items, M):
    print(*i)

조합(combination)은 순서를 고려하지 않고 뽑는 경우의 수를 의미한다. n개의 수에서 r개를 뽑는 가지 수는 

이다. python에서는 itertools의 combinations를 import 후 사용하면 된다(from itertools import combinations). 마찬가지로  조합도 몇개 고를 지 선택할 수 있다.

 

순열과 조합을 알아두면 완전 탐색, 경우의 수 문제들을 쉽게 풀 수 있을 떄가 많아서 유용하다. 

Permutation을 사용하여 순열을 만들면 편하지만... 코딩테스트 문제에서 m과 n이 무지하게 커진다면 시간 초과가 날 수 있다. 그러므로 백트래킹을 이해하고 백트래킹 방법으로 푸는 것이 필요하다. 

n,m = map(int,input().split())

visited = [False] * (n+1)             # 방문 관리
 
result = []                           

def dfs() :
    if len(result) == m :               # 길이를 m으로 제한
        print(*result)
        return 
    else :
        for i in range(1,n+1) :
            if visited[i] :             # 이미 방문했다면 무시
                continue
            visited[i] = True           # 방문 표시
            result.append(i)            
            dfs()                       # 재탐색
            visited[i] = False
            result.pop()
            
dfs()

GPT)

백트래킹 알고리즘을 이용하여 주어진 n과 m에 따라 모든 가능한 조합을 생성하는 과정은 깊이 우선 탐색 (DFS)을 사용합니다. 주어진 조건에서 n = 4이고 m = 2일 때, 프로그램의 실행 흐름과 result 배열의 변화를 단계별로 설명하겠습니다.

1. 초기 설정:
   • visited 배열: [False, False, False, False, False] (0부터 n까지, 총 n+1개의 요소)
   • result 리스트: [] (빈 리스트)
2. 첫 번째 dfs 호출 (depth 0):
   • len(result) == m 조건을 만족하지 않으므로 for 루프 시작.
   • i = 1:
     • visited[1] = True
     • result = [1]
     • dfs() 재귀 호출 (depth 1)
3. 두 번째 dfs 호출 (depth 1):
   • len(result) == m 조건을 만족하지 않으므로 for 루프 시작.
   • i = 1:
     • visited[1]이 True이므로 continue.
   • i = 2:
     • visited[2] = True
     • result = [1, 2]
     • dfs() 재귀 호출 (depth 2)
4. 세 번째 dfs 호출 (depth 2):
   • len(result) == m 조건을 만족하므로 [1, 2] 출력.
   • 백트랙킹:
     • visited[2] = False
     • result = [1]
   • 루프 종료 후 리턴 (depth 1로 복귀)
5. 두 번째 dfs 복귀 (depth 1):
   • i = 3:
     • visited[3] = True
     • result = [1, 3]
     • dfs() 재귀 호출 (depth 2)
6. 세 번째 dfs 호출 (depth 2):
   • len(result) == m 조건을 만족하므로 [1, 3] 출력.
   • 백트랙킹:
     • visited[3] = False
     • result = [1]
   • 루프 종료 후 리턴 (depth 1로 복귀)
7. 두 번째 dfs 복귀 (depth 1):
   • i = 4:
     • visited[4] = True
     • result = [1, 4]
     • dfs() 재귀 호출 (depth 2)
8. 세 번째 dfs 호출 (depth 2):
   • len(result) == m 조건을 만족하므로 [1, 4] 출력.
   • 백트랙킹:
     • visited[4] = False
     • result = [1]
   • 루프 종료 후 리턴 (depth 1로 복귀)
9. 두 번째 dfs 복귀 (depth 1):
   • visited[1] = False
   • result = []
   • i = 2:
     • visited[2] = True
     • result = [2]
     • dfs() 재귀 호출 (depth 1)
10. 두 번째 dfs 호출 (depth 1):
    • len(result) == m 조건을 만족하지 않으므로 for 루프 시작.
    • i = 1:
      • visited[1] = True
      • result = [2, 1]
      • dfs() 재귀 호출 (depth 2)
11. 세 번째 dfs 호출 (depth 2):
    • len(result) == m 조건을 만족하므로 [2, 1] 출력.
    • 백트랙킹:
      • visited[1] = False
      • result = [2]
    • 루프 종료 후 리턴 (depth 1로 복귀)
12. 두 번째 dfs 복귀 (depth 1):
    • i = 3:
      • visited[3] = True
      • result = [2, 3]
      • dfs() 재귀 호출 (depth 2)
13. 세 번째 dfs 호출 (depth 2):
    • len(result) == m 조건을 만족하므로 [2, 3] 출력.
    • 백트랙킹:
      • visited[3] = False
      • result = [2]
    • 루프 종료 후 리턴 (depth 1로 복귀)
14. 두 번째 dfs 복귀 (depth 1):
    • i = 4:
      • visited[4] = True
      • result = [2, 4]
      • dfs() 재귀 호출 (depth 2)
15. 세 번째 dfs 호출 (depth 2):
    • len(result) == m 조건을 만족하므로 [2, 4] 출력.
    • 백트랙킹:
      • visited[4] = False
      • result = [2]
    • 루프 종료 후 리턴 (depth 1로 복귀)
16. 두 번째 dfs 복귀 (depth 1):
    • visited[2] = False
    • result = []
    • i = 3:
      • visited[3] = True
      • result = [3]
      • dfs() 재귀 호출 (depth 1)
17. 두 번째 dfs 호출 (depth 1):
    • len(result) == m 조건을 만족하지 않으므로 for 루프 시작.
    • i = 1:
      • visited[1] = True
      • result = [3, 1]
      • dfs() 재귀 호출 (depth 2)
18. 세 번째 dfs 호출 (depth 2):
    • len(result) == m 조건을 만족하므로 [3, 1] 출력.
    • 백트랙킹:
      • visited[1] = False
      • result = [3]
    • 루프 종료 후 리턴 (depth 1로 복귀)
19. 두 번째 dfs 복귀 (depth 1):
    • i = 2:
      • visited[2] = True
      • result = [3, 2]
      • dfs() 재귀 호출 (depth 2)
20. 세 번째 dfs 호출 (depth 2):
    • len(result) == m 조건을 만족하므로 [3, 2] 출력.
    • 백트랙킹:
      • visited[2] = False
      • result = [3]
    • 루프 종료 후 리턴 (depth 1로 복귀)
21. 두 번째 dfs 복귀 (depth 1):
    • i = 4:
      • visited[4] = True
      • result = [3, 4]
      • dfs() 재귀 호출 (depth 2)
22. 세 번째 dfs 호출 (depth 2):
    • len(result) == m 조건을 만족하므로 [3, 4] 출력.
    • 백트랙킹:
      • visited[4] = False
      • result = [3]
    • 루프 종료 후 리턴 (depth 1로 복귀)
23. 두 번째 dfs 복귀 (depth 1):
    • visited[3] = False
    • result = []
    • i = 4:
      • visited[4] = True
      • result = [4]
      • dfs() 재귀 호출 (depth 1)
24. 두 번째 dfs 호출 (depth 1):
    • len(result) == m 조건을 만족하지 않으므로 for 루프 시작.
    • i = 1:
      • visited[1] = True
      • result = [4, 1]
      • dfs() 재귀 호출 (depth 2)
25. 세 번째 dfs 호출 (depth 2):
    • len(result) == m 조건을 만족하므로 [4, 1] 출력.
    • 백트랙킹:
      • visited[1] = False
      • result = [4]
    • 루프 종료 후 리턴 (depth 1로 복귀)
26. 두 번째 dfs 복귀 (depth 1):
    • i = 2:
      • visited[2] = True
      • result = [4, 2]
      • dfs() 재귀 호출 (depth 2)
27. 세 번째 dfs 호출 (depth 2):
    • len(result) == m 조건을 만족하므로 [4, 2] 출력.
    • 백트랙킹:
      • visited[2] = False
      • result = [4]
    • 루프 종료 후 리턴 (depth 1로 복귀)
28. 두 번째 dfs 복귀 (depth 1):
    • i = 3:
      • visited[3] = True
      • result = [4, 3]
      • dfs() 재귀 호출 (depth 2)
29. 세 번째 dfs 호출 (depth 2):
    • len(result) == m 조건을 만족하므로 [4, 3] 출력.
    • 백트랙킹:
      • visited[3] = False
      • result = [4]
    • 루프 종료 후 리턴 (depth 1로 복귀)
30. 두 번째 dfs 복귀 (depth 1):
    • visited[4] = False
    • result = []
    • 루프 종료

이로써 n = 4이고 m = 2일 때, 가능한 모든 조합을 백트래킹을 이용하여 출력하게 됩니다. 최종 출력은 다음과 같습니다:

 

ex)

baekjoon - 3040
https://www.acmicpc.net/problem/3040

3040번: 백설 공주와 일곱 난쟁이

from itertools import combinations 
arr = []

for _ in range(9) :
  arr.append(int(input()))

for i in combinations(arr,7) :
  if sum(i) == 100 :
    arr = i

for i in arr :
  print(i)

ex)baekjoon - 15650

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

from itertools import combinations
N,M = map(int,input().split())
arr = [i for i in range(1,N+1)]
for i in combinations(arr,M) :
  print(*i)

 

중복 순열은(permutation with Repetition) 순열에서 중복 선택이 가능한 것을 의미한다.  python에서 from itertools import product를 사용 하면 product를 이용하여 중복 순열을 구현 할 수 있다. 

Combination을 사용하여 조합을 만들면 편하지만... 코딩테스트 문제에서 m과 n이 무지하게 커진다면 시간 초과가 날 수 있다. 그러므로 백트래킹을 이해하고 백트래킹 방법으로 푸는 것이 필요하다. 

n,m = map(int,input().split())
visited = [False] *(n+1)

result = []

def dfs(start) :
    if len(result) == m :
        print(*result)
        return
    else :
        remember = ''                               # 중복된 수가 안나오도록
        for i in range(start,n+1) :                 # 하기 위해 start 변수 추가
            if visited[i] :
                continue
            else :
                if remember != i:               
                    remember = i
                    visited[i] = True
                    result.append(i)
                    dfs(i+1)           
                    visited[i] = False
                    result.pop()
                    
dfs(1)

# 예제 입력
4 2
# 예제 출력
1 2
1 3
1 4
2 3
2 4
3 4

GPT)

1. 초기 상태:
   • n = 4, m = 2로 설정합니다.
   • visited 배열은 [False, False, False, False, False]로 초기화됩니다. 인덱스 0은 사용하지 않습니다.
   • result는 빈 리스트입니다.
2. 첫 번째 호출 (dfs(1)):
   • start는 1입니다.
   • if len(result) == m 조건에 의해 result의 길이가 m과 같지 않으므로, else 블록이 실행됩니다.
   • remember는 초기에 빈 문자열('')입니다.
   • for 루프에서 i가 1부터 n까지 반복됩니다.
3. i = 1일 때:
   • visited[1]이 False이므로 조건이 참입니다.
   • remember와 i가 같지 않으므로 remember = 1이 됩니다.
   • visited[1] = True로 표시하고, result.append(1)을 실행하여 result는 [1]이 됩니다.
   • dfs(i + 1) 즉, dfs(2)가 재귀적으로 호출됩니다.
4. 두 번째 호출 (dfs(2)):
   • start는 2입니다.
   • if len(result) == m 조건에 의해 result의 길이가 m과 같지 않으므로, else 블록이 실행됩니다.
   • remember는 초기에 빈 문자열('')입니다.
   • for 루프에서 i가 2부터 n까지 반복됩니다.
5. i = 2일 때:
   • visited[2]가 False이므로 조건이 참입니다.
   • remember와 i가 같지 않으므로 remember = 2가 됩니다.
   • visited[2] = True로 표시하고, result.append(2)을 실행하여 result는 [1, 2]가 됩니다.
   • if len(result) == m 조건이 만족되어 print(*result)가 실행됩니다. 따라서 결과는 "1 2"가 출력됩니다.
6. 백트래킹:
   • 이제 dfs(2) 호출이 종료되고, 이전 호출 dfs(1)로 되돌아갑니다.
   • visited[2] = False로 표시되고, result.pop()을 실행하여 result는 [1]이 됩니다.
   • 이후 for 루프에서 i = 3으로 이동하여 다음 가능한 숫자를 찾습니다.
7. i = 3일 때:
   • visited[3]가 False이므로 조건이 참입니다.
   • remember와 i가 같지 않으므로 remember = 3이 됩니다.
   • visited[3] = True로 표시하고, result.append(3)을 실행하여 result는 [1, 3]가 됩니다.
   • dfs(i + 1) 즉, dfs(4)가 재귀적으로 호출됩니다.
8. 세 번째 호출 (dfs(4)):
   • start는 4입니다.
   • if len(result) == m 조건에 의해 result의 길이가 m과 같지 않으므로, else 블록이 실행됩니다.
   • remember는 초기에 빈 문자열('')입니다.
   • for 루프에서 i가 4부터 n까지 반복됩니다.
9. i = 4일 때:
   • visited[4]가 False이므로 조건이 참입니다.
   • remember와 i가 같지 않으므로 remember = 4가 됩니다.
   • visited[4] = True로 표시하고, result.append(4)을 실행하여 result는 [1, 4]가 됩니다.
   • if len(result) == m 조건이 만족되어 print(*result)가 실행됩니다. 따라서 결과는 "1 4"가 출력됩니다.
10. 백트래킹:
    • 이제 dfs(4) 호출이 종료되고, 이전 호출 dfs(3)로 되돌아갑니다.
    • visited[4] = False로 표시되고, result.pop()을 실행하여 result는 [1, 3]이 됩니다.
    • 이후 for 루프에서 i = 4으로 이동하여 다음 가능한 숫자를 찾습니다.
11. i = 4일 때 (다시):
    • visited[4]가 이미 True이므로 건너뜁니다.
12. 백트래킹:
    • dfs(3) 호출이 모두 완료되고, 이전 호출 dfs(1)로 되돌아갑니다.
    • visited[3] = False로 표시되고, result.pop()을 실행하여 result는 [1]이 됩니다.
    • 이후 for 루프에서 i = 3으로 이동하여 다음 가능한 숫자를 찾습니다.
13. i = 3일 때 (다시):
    • 위와 같은 과정이 반복되며, dfs(1) 호출에서 모든 가능한 조합을 찾고 출력합니다.

이 과정을 통해 백트래킹 알고리즘이 중복된 숫자를 피하면서 가능한 모든 조합을 생성하고 출력하는 방식을 이해할 수 있습니다.

 

 

 

 

ex)baekjoon - 15651

https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

from itertools import product
N,M = map(int,input().split())
arr = [i for i in range(1,N+1)]

for i in product(arr,repeat=M) :
  print(*i)

중복 조합(combination with Repetition)은 조합에서 중복 선택이 가능한 것을 의미한다. python에서 from itertools import combinations_with_replacement를 사용 하면 중복 조합을 구현 할 수 있다.

ex)baekjoon -15652

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

from itertools import combinations_with_replacement

N,M = map(int,input().split())
arr = [i for i in range(1,N+1)]

for i in combinations_with_replacement(arr,M) :
  print(*i)