📌 12장 백트래킹과 백트래킹 알고리즘(자료구조)
📌💡 12-1. 개념:
백트래킹 :가능성이 없는 곳은 패스, 가능성이 있는 곳을 탐색(=따라서, 시간복잡도는 특정 X (문제마다 효율이 달라짐))
해가 될 가능성을 판단하는 것
<-> 완전탐색 : 모든 경우의 수를 탐색하는 방법 ex) 깊이 우선 탐색, 너비 우선 탐색
백트래킹 알고리즘의 핵심 = 유망함수 : 해가 될 가능성을 판단하는 함수
1. 유효한 해의 집합을 정의
2. 위 단계에서 정의한 집합을 그래프로 표현
3. 유망 함수를 정의
4. 백트래킹 알고리즘을 활용해서 해 찾기(-> 이곳에서 찾을 것만 찾음)
가장 대표적인 문제 예시)
- 문제 1) 합이 6이 넘는 경우 : [1,2,3,4] 중 2개 숫자 뽑아서, 합 6 초과하는 경우 알아내기
유망 함수가 없다면? : 경우의 수 다 확인해야함,N개의 숫자를 뽑는 조합 2^N
유망 함수 : 처음에 뽑은 숫자가 3 미만이면 탐색 X
- 문제 2) N-퀸 문제 : N X N 체스판에 N개 배치했을 때 서로를 공격할 수 없는 위치에 놓을 수 있는 방법이 있는지 찾는 문제
유망 함수가 없다면? : 경우의 수 다 확인해야함
유망 함수 :
여왕이 추가될 때 -> 행, 대각선 방향에 겹치는 여왕 있으면 탐색 X
📌 10. 문제
🩶 몸풀기 문제 47. 1부터 N까지 숫자 중 합이 10 되는 조합 구하기
권장 시간 복잡도 : O(N!)
백트래킹인 이유?
-> 정수 N을 입력받아, 1부터 N까지의 숫자 중에서 합이 10이 되는 조합을 구하려면 원래 모든 경우의 수를 봐야함
근데 합이 10이상이면 굳이 조합할 필요없음 -> 백트래킹!
제약조건 :
- 백트래킹을 활용
- 숫자 조합은 오름차순으로 정렬되어야 합니다.
- 같은 숫자는 한 번만 선택할 수 있음
- N은 1이상 10이하인 정수
def solution(N):
results = [] #진짜 조합 결과를 담을 리스트
def backtrack(sum, selected_nums, start):
if sum == 10: #합이 10이 될때만 진짜 결과 리스트에 추가
results.append(selected_nums)
return
for i in range(start, N + 1): #다음에 선택할 수 있는 숫자들을 하나씩 선택하면서
if sum + i <= 10: #선택한 숫자의 합이 10보다 작거나 같으면
backtrack(
sum + i, selected_nums + [i], i + 1
) #백트래킹 함수를 재귀적으로 호출
#else 조건, 이때 유망함수 사용, 10보다 클 경우에는 추가할 필요없음
backtrack(0, [], 1) #백트래킹 함수 호출, 한번 돌면 sum값은 항상 0으로 재시작 (* 처음에는 빈 열 값이 들어가지만, if절에 속하면 추가함)
return results # 조합 결과 반환
# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
# print(solution(5)) # 반환값 : [[1, 2, 3, 4], [1, 4, 5], [2, 3, 5]]
# print(solution(2)) # 반환값 : []
# print(solution(7)) # 반환값 : [[1, 2, 3, 4], [1, 2, 7], [1, 3, 6], [1, 4, 5], [2, 3, 5], [3, 7], [4, 6]]
🩶 문제 50. N-퀸 문제
def check(idx, i, arr): #대각선에 있는지 체크
for j in range(idx):
if idx - j == abs(arr[j] - i):
return True
return False
def dfs(n, idx, visited, arr):#전체크기, 인덱스, visited, arr
if idx == n:#현재 인덱스가 n가 괕으면 조건 만족해서, 퀸 모두 배치
global answer
answer += 1#카운트
return#종료
for i in range(n):#n번 반복
if visited[i] == 1:#i번째 열에 퀸이 있을시
continue
if check(idx, i, arr):#대각선에 퀸이 있을시
continue
#현재 위치에 두는것 가능
arr[idx] = i#행의 상태 arr idx 에 i저장
visited[i] = 1#열 visited의 i위치를 1로 바꾸기
dfs(n, idx+1, visited, arr)# 다음 행(idx+1)로 재귀호출
visited[i] = 0#재귀호출 dfs 끝날때마다 0으로 바꿔주기(* 다시 이전 위치에서 for문을 이어나갈 수 있도록)
answer = 0
def solution(n):
visited = [0] * n #열기준
arr = [0] * n #행기준
dfs(n, 0, visited, arr)
return answer
우당탕탕