이번 주차에서는 알고리즘과 자료구조를 공부하고 백준 문제를 풀면서 컴퓨터에게 대신 계산을 맡길 수 있는 코드를 작성하는 방법을 배운다.
나는 기초적인 조건문, 반복문 사용부터 재귀함수, 정렬, 완전탐색 등을 주제로 주어진 알고리즘 문제들을 풀었다. 그 중에서도 이해하는데 시간이 오래 걸렸던 문제와 이론들을 정리해보고자 한다.
재귀함수(recursive function)란?
재귀라는 것은 원래 있던 곳으로 다시 돌아오는 것을 뜻한다. 즉, 자기 자신을 다시 호출하는 함수이다.
def recursive(a,b):
if a == b:
return
recursive(a+1, b)
recursive(0,3)위 함수를 통해 설명하자면, 우선 함수 안에서 자기 자신을 호출한다. 호출하게 되면 같은 구조의 함수를 생성하여 함수가 다시 반복된다.
recursive(0,3)을 호출하면 a+1의 영향으로 recursive(1,3)이라는 함수를 생성하여 처음부터 다시 실행된다. (1,3)에서도 a+1이 똑같이 진행되고 recursive(2,3)이라는 함수를 또 생성한다. recursive(3,3)에 도달하면 a와 b 값이 같기 때문에 리턴한다. 재귀함수는 자신을 불러오는 함수여서 탈출할 수 있는 구간을 만들어주지 않으면 무한 루프가 생성되기 때문에 주의해야한다.
재귀함수는 이 하나의 함수 안에서 실행되는 것이 아니고 해당 함수가 복사되어 다른 곳에서 진행되는 것이라는 것을 명심해야한다.
recursive(0,3) -> recursive(1,3) -> recursive(2,3) -> recursive(3,3)까지 진행되었다면 리턴되어 다시 이전으로 돌아간다.
recursive(3,3) -> recursive(2,3) -> recursive(1,3) -> recursive(0,3)으로 돌아가서 사라진다.
백트래킹이란?
백트래킹(DFS)이란 원하는 값을 탐색하던 도중 정답이 아니면 다시 돌아가서 탐색을 진행하는 것을 일컫는다. 답이 될만한 것인지 판단하고 답이 아닌 것 같다고 판단하면 그 부분은 탐색하지 않는다. 따라서 반복문의 횟수를 줄일 수 있어 효율적이다. 해가 될 가능성이 있는 노드는 '유망하다' 라고 판단하고 탐색하며, 유망하지 않은 노드는 방문하지 않는다. 이를 가지치기라고도 한다.
백준 문제 9663 N-Queen
-
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
-
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
(1 ≤ N < 15)
def n_queen(x):
if x == N:
global count
count += 1
return
for y in range(N):
board[x] = y
if check(x):
n_queen(x+1)
def check(x):
for y in range(x):
if board[x] == board[y] or (x-y == abs(board[x]- board[y])):
return False
return True
N= int(input())
count = 0
board = [0 for _ in range(N)]
n_queen(0)
print(count)풀이
백트래킹과 재귀함수를 통해 구현하는 문제이다. 퀸을 놓을 수 없는 위치, 즉 퀸이 놓아져 있는 위치에서 상하좌우 대각선에 놓지 못하게끔 구현하는 게 가장 큰 포인트이다. 이 문제를 구현할 수 있는 흐름은 대강 이러하다.
-
N * N 체스판을 만든다.
board = [0 for _ in range(N)]가 그 역할을 수행한다. -
board[x]= y, 즉 (x,y)라는 좌표 지점을 설정한다. 해당 좌표 지점에 놓을 수 있다면 놓고, 그게 아니라면 바로 다음 좌표로 이동시킨다.
-
퀸을 해당 좌표에 놓을 수 있는지의 여부를 판단할 수 있어야한다. 퀸이 이미 배치되었다면 배치된 퀸의 상하좌우 대각선에는 놓을 수 없다.
board[x] == board[y] >> 상하좌우가 같고
(x-y == abs(board[x]- board[y]) >> 대각선이 같다면 놓을 수 없다.만약 퀸이 (3,3)에 있다면 왼쪽 대각선은 (2,2), (1,1), (0,0)
오른쪽 대각선은 (2,4), (1,5), (0,6)이다. 위에서부터 퀸을 놓으니 아래 대각선은 확인할 필요가 없다.(3,3) - (2,2) = (1,1) (3,3) - (2,4) = (1, -1) (1,1) == abs(1, -1)퀸이 있는 좌표에서 대각선의 좌표를 빼면 왼쪽과 오른쪽 대각선의 좌표는 동일하다. 고로 x-y == abs(board[x]- board[y])라는 식이 성립한다.
- check 함수를 사용해 퀸을 놓을 수 있는 자리인지 체크해주고 재귀를 통해 다시 함수의 처음으로 돌아간다. 다시 탐색을 진행하고 탐색이 끝나면 퀸을 놓을 수 있는 경우의 수를 도출해줄 count라는 변수를 사용한다. 초기값은 0, 경우의 수가 증가할 때마다 1씩 증가시킨다. 카운트가 증가하면 또 다른 경우의 수를 찾아나설 수 있게끔 탈출조건을 설정한다.
++ 추가예정
