백트래킹, 이진탐색
백트래킹
백트래킹은 필요 없는 경우를 가지치기(pruning)함으로써 시간복잡도를 줄이는 방법이다.
바로 문제로 살펴보자.
N-Queen
문제
N-퀸 퍼즐은 두 여왕이 서로 공격하지 않도록 n x n 체스판 위에 n개의 여왕을 배치하는 문제입니다.
여왕은 상하좌우 대각선으로 원하는만큼 움직일 수 있습니다.
정수 n이 주어졌을 때, N-퀸 퍼즐에 대한 모든 고유한 해를 반환합니다. 어떤 순서로든 답을 반환할 수 있습니다.
각 해는 n개의 여왕 배치에 대한 고유한 보드 구성을 포함하며, 여기서 'Q'와 '.'는 각각 여왕과 빈 칸을 나타냅니다.
설명
모든 행과 열에는 하나의 퀸만 놓일 수 있고, 대각선 조건에서도 단 하나만 놓여야한다.
r행 c열에 퀸을 놓았다면, checked[r] = c에 저장하여 checked라는 리스트에는 퀸들의 위치를 저장하도록 하자.
재귀함수로 r+1을 넘겨주면서, (이미 행은 확인한 셈) 열과 대각선을 체크해주면서 checked 리스트를 채워주면 된다.
만약 is_ok 함수에서 False를 반환한다면, 그 다음의 경우들에 대해서는 살펴볼 필요도 없기 때문에 효율적인 방법이 된다.
구현
def nQueen(n):
# n은 시작할 열의 위치이다.
# checked 인덱스는 행, 값은 열을 나타낸다.
# 2차원 배열로도 나타낼 수 있지만,
# 한 행에 하나의 값만 들어갈 수 있기 때문에 1차원 배열로 나타낼 수 있는 특수한 경우이다.
checked = [-1] * n
cnt = 0
def is_ok(nth_row):
for row in range(nth_row):
# 열 번호가 겹치는지는 않은지
# 또는 대각선으로 존재하지는 않은지 체크한다.
if checked[nth_row] == checked[row] or nth_row - row == abs(checked[nth_row] - checked[row]):
return False
return True
def dfs(row):
# row는 퀸을 놓을 행번호를 의미한다.
# row는 n-1까지 가능하며, n이 되었다는 것은 n개의 퀸을 모두 올바른 위치에 두었다는 의미이다.
if row >= n:
# 0 ~ n-1 행에 퀸을 모두 하나씩 두었을 때 경우의 수를 1 증가시키고 재귀탐색을 종료한다.
nonlocal cnt
cnt+=1
return
for col in range(n):
checked[row] = col
if is_ok(row):
dfs(row + 1)이진탐색
이진탐색은 배열이 정렬되어있을 경우, 절반씩 줄여나가면서 탐색하는 기법이다.
오름차순으로 정렬된 정수 배열 nums와 정수 target이 주어졌을 때, nums에서 대상을 검색하는 함수를 작성한다.
함수는 대상이 존재하면 그 색인을 반환하고 그렇지 않으면 -1을 반환한다.
def binary_search(nums, target):
def bs(start,end):
if start > end: return -1
mid = (start + end) // 2
if nums[mid] == target: return mid
if nums[mid] > target: return bs(start, mid - 1)
if nums[mid] < target: return bs(mid + 1, end)
return bs(0,len(nums)-1)문제 - 순열 생성하기
문제
- 주어진 정수 배열에서 모든 가능한 순열을 생성하는 프로그램을 작성하세요.
- 배열에는 중복된 숫자가 없다고 가정합니다.
- 백트래킹 알고리즘을 사용하여 효율적으로 모든 가능성을 탐색합니다.
설명
재귀함수를 통해서 숫자를 하나씩 배열에 추가하도록 한다. 이때, visited 배열을 참고하여 중복된 숫자를 넣지 않도록 한다.
- len를 통해 숫자 배열이 N개가 되면 종료한다.
- N개 이하인 경우에는 재귀함수를 다시 호출한다.
- 재귀함수를 호출할 때에, nums를 복사하여 넘겨준다.
구현
from collections import deque
inputNums= list(map(int,input().replace('[','').replace(']','').split(',')))
queue= deque()
answers = []
def make_permutation(nums):
if len(nums) == len(inputNums):
answers.append(nums)
return
for num in inputNums:
if num in nums:
continue
else:
new_nums = nums.copy()
new_nums.append(num)
make_permutation(new_nums)
for inputNum in inputNums:
nums = []
nums.append(inputNum)
make_permutation(nums)
print("\n".join(map(str,answers)))