정글사관학교 6일차 TIL: 재귀, 정렬 알고리즘

오늘은 총 7 문제를 풀었다. 어제 하루만에 스무 문제 넘게 풀었던 것에 비하면 아쉬운 성적표다(난이도는 어제가 낮긴 했다.)

 

하루종일 발목을 붙잡았던 문제는 N-Queen 문제와 수 정렬하기 3 이 두 문제였다. 각각 재귀, 정렬 알고리즘으로 푸는 문제다.

 

 

 

1. 재귀 알고리즘

어떤 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 이를 '재귀(recursion)'라고 한다. 이 개념을 활용하면 계속해서 자신이 반복되는 이벤트를 명료하고 간단하게 정의할 수 있다.

 

예시로 자연수의 정의를 보자.

 

- 1은 자연수이다.
- 어떤 자연수의 바로 다음 수도 자연수다.

여기까지만 보면 간단해 보이는데..N-Queen 문제는 쉽게 와닿지 않더라. 하노이의 탑까지도 어찌어찌 해냈다만 N-Queen은 진짜...(천하의 가우스도 오답을 발표했다는 걸 보면 나름 안심이 된다)

 

책에서는 8-Queen 문제로 해당 문제를 소개하고 있다.

 

8개의 퀸이 서로 공격하여 잡을 수 없도록 8 X 8 체스판에 배치하세요 (N-Queen의 경우 8 => N으로 바꾸면 됨)

 

퀸의 행마법을 보자. 자기 자신을 기준으로 상하좌우&대각선까지 이동 가능하다. 따라서 이를 제외한 곳에 배치해야 하는데, 문제는 어떤 퀸도 서로의 행마 범위 안에 들어와서는 안된다는 점이다.

 

이를 재귀로 풀기 위해 본 책의 풀이법에서는 체스의 행렬을 리스트로 표현하는 방법을 제안한다. 리스트의 인덱스에는 열을 배치하고 해당 인덱스에 들어가는 값을 해당 열에서 퀸이 위치하는 행을 나타내는 방식으로 구현했다.

 

책에서는 리스트에서 퀸이 위치하는 방식을 이해시키기 위해 단계별로 차근차근 풀어서 써줬지만 오히려 더 헷갈리게 만드는 터라..여기서는 바로 문제 해결하는 코드로 넘어간다.

 

리스트는 총 4개를 만든다.

 

1. pos: 처음에 설명했던 퀸을 배치하는 체스판을 구현한 리스트

pos = [0] * 8

2. flag_a: 각 행에 퀸을 배치했는지 체크하는 리스트

3. flag_b: 각 대각선(↙↗)에 퀸을 배치했는지 체크하는 리스트

4. flag_c: 각 대각선(↖↘)에 퀸을 배치했는지 체크하는 리스트

flag_a = [False] * 8
flag_b = [False] * 15
flag_c = [False] * 15

 

 

다음으로는 두 개의 함수를 코드로 짠다.

1. put(): 각 열에 배치한 퀸의 위치를 출력하는 함수

2. set(): 각 열의 알맞은 위치에 퀸을 배치하는 함수

 

먼저 put()부터 짠다.

def put() -> None:
	for i in range(8):
    	print(f'{pos[i]:2}', end='') #pos[i]:2 => pos[i]를 출력할 때 한 칸씩 띄워서 출력
    print() # 출력할 때 줄 띄워서 출력

def set(i: int) -> None:
	for j in range(8) # 8-Queen에서는 8이나 N-Queen에서는 range에 N을 대입한다.
    	if (    not flag_a[j]		# j행에 퀸이 배치되지 않았다면
        	and not flag_b[i+j]		# 대각선 방향으로 퀸이 배치되지 않았다면
            and not flag_c[i-j+7]):	# 대각선 방향으로 퀸이 배치되지 않았다면
            pos[i] = j				# 퀸을 j행에 배치
            if i == 7:				#모든 열에 퀸을 배치 완료
            	put()				#퀸 위치 출력
            else:
            	flag_a[j] = flag_b[i+j] = flag[i-j+7] = True #퀸 배치했다고 표시
                set(i+1) #다음 열에 퀸을 배치
                flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = False

set(0) #0열에 퀸 배치

 

 

 

2. 정렬 알고리즘

#내일 마저 작성할 예정..!