PYTHON › 파이썬을 이용한 다시만난 재귀(Week1_Day2)
2일차는 공부했던 내용을 바탕으로 알고리즘을 풀어보며 몰랐던 것을 정리한다.
아스키코드 변환
chr(숫자:int) : 숫자에 맞는 아스키 코드 반환 함수 ord(문자:str) : 문자에 맞는 아스키 코드 반환 함수
소수 찾기
에라토스테네스의 체를 공부하기 전에는
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def find_prime(numbers):
cnt = 0
prime = [2, 3]
if max(numbers) == 1:
return 0
elif max(numbers) == 2:
return 1
elif max(numbers) == 3:
if 2 in numbers:
return 2
else:
return 1
else:
for num in range(5, max(numbers) + 1, 2):
for p_num in prime:
if p_num * p_num <= num:
if num % p_num == 0:
break
else:
prime.append(num)
for number in numbers:
if number in prime:
cnt += 1
return cnt
주어진 numbers라는 리스트 안에 소수가 몇 개 인지 구하는 문제였는데, 이런 식으로 무조건 소수인 2,3 은 미리 소수배열에 넣어두고, numbers 안의 값 중 가장 큰 값 보다 작은 소수만 prime 배열에 넣고, 소수 탐색 시 그 수의 루트 보다 작은 값들로만 나누어 중복계산을 막고 소수로 나누어 떨어지지 않는 값이 곧 소수이기에 prime 배열에 넣었다.
반면 골드바흐 파티션을 구하는 문제에서는 이렇게 풀었을 때 시간초과가 발생했다. 그래서 에라토스테네스의 체에 대해서 찾아보니 기본 2 부터 n까지의 모든 정수를 나열하고 증가시키면서 소수들의 배수를 지워나가는 방식이였다. 그렇게 되면 소수만이 남아있는 것이다. 처음에는 이해를 잘못해서 “2의 배수를 모두 지워버리고 숫자를 증가시키면 그럼 4의 배수를 지워가는 과정에서 중복이 발생” 하는것이 아닌가 라는 생각에
1
2
3
4
5
6
7
8
9
def find_prime(n):
prime = [False, False] + [True] * (n - 1)
for i in range(4, n+1, 2):
prime[i] = False
for p in range(3, int(n ** 0.5) + 1, 2):
if prime[p]:
for j in range(p*p, n+1, p):
prime[j] = False
return [p for p in range(2, n+1) if prime[p]]
이렇게 2의 배수를 따로 다 False로 처리해버리고 홀수에 대해서만 진행하는 것이 효율적이라고 생각했다. 하지만 알고보니
1
2
3
4
5
6
7
8
9
def find_prime(n):
prime = [False, False] + [True] * (n - 1)
p = 2
while (p * p <= n):
if prime[p]:
for i in range(p*p, n+1, p):
prime[i] = False
p += 1
return [k for k in range(n+1) if prime[k]]
여기서 보듯이 “if prime[p]” 라는 조건에서 “소수일때” 이기 때문에 2의 배수인 짝수가 다시 지워질 일은 없는것이였다. 또한 for문의 범위가 p*p 부터 인 것은 p보다 작은 곱셈은 이미 앞선 단계에서 진행했기 때문에 결국 중복이 발생할 곳이 없는 효율적인 방법이였다.😂
재귀
이전에 알고리즘 공부할 때도 정말 힘들었던 재귀함수를 다시 만났다. 재귀라는 것은 단순하게 다시 자기자신을 호출하는 함수를 말하지만 실제로 그렇게 단순하지가 않다. 대표적 예시로 하노이의 탑을 풀어보았다. 이 문제를 풀기 전 전체 과정을 간소화 해 보는게 먼저였다. 원반을 그룹으로 묶어서 이동한다면 맨 아래층을 남기고 중간기둥으로 옮긴 후 -> 아래층을 목표기둥으로 옮기고 -> 다시 그룹을 목표기둥으로 옮기면 되는 간단한 과정이다. 이 과정을 머릿속에 기억해 놓고, 코드를 짜게 되면
1
2
3
4
5
6
7
8
def move(num, x, y):
if(N <= 20):
if num == 1:
print(x, y)
return
move(num-1, x, 6-x-y)
print(x, y)
move(num-1, 6-x-y, y)
num이 원반 갯수, x가 시작기둥, y가 목표기둥이라고 했을 때, 마지막 남은 원반이 아니라면 아래층을 뺀 그룹을 시작기둥에서 6-x-y인 중간기둥으로 옮기고(print) 다시 중간기둥에서 목표기둥으로 옮기는 것을 반복하는 것이다. 처음에는 이게 원반을 하나씩 옮겨야 한다는 규칙을 위반한다고 생각을 했었는데, 재귀함수의 특성 상 num-1개의 원반을 옮기는 함수의 값을 위해서 num-2개의 원반을 옮기는 함수가 실행되어야 하고 쭉 이어져서 결국엔 원반이 하나일때까지 진행되기 때문에 규칙을 지키고 있는 셈이였다. 아직 완벽히 이해하진 못했지만 하나에서 출발하여 분기별로 가지가 복잡하게 생기는 것을 머릿속으로 그려보면 얼추 이해가 됬다.
다음으로는 NQueen문제를 풀어보았다. 이전에 공부할 때는 너무 어려워서 포기했었는데 이번에도 포기 할 수는 없어서 조금이라도 이해해보려 하였다. 이 문제의 특징은 체스에서의 퀸이라는 말의 기능을 이용해 N x N 체스판에서 가로, 세로, 대각선으로 겹치는 일이 없도록 퀸을 N개 배치하는 문제이다. 이 문제도 3가지 규칙으로 단순화 하여 먼저 각 열에서 퀸이 겹치지 않게, 다음은 행에서 겹치지 않게, 마지막으로 대각선에서 겹치지 않도록. 의 과정으로 생각하였다. 이렇게 되면 각 분기에 따라 필요하지 않은 조합은 생략하는 것으로 답을 찾아가는 것이다.
1
2
3
4
5
6
7
8
9
10
pos = [0] * N
def set_queen(i):
global cnt
for j in range(N):
pos[i] = j
if i == N - 1:
cnt += 1
else:
set_queen(i + 1)
set_queen(0)
set_queen()함수는 pos라는 배열을 통해, 퀸의 배치를 기록 할 수 있도록 하고, i=0 일 때를 살펴보면 pos[0] = 0, 1, 2 … 에 따라서 각각 set_queen(1)이 호출되고 그 아래로 계속 나아가는 것을 알 수 있다. 그럼 00000000, 00000001로 가지가 쭉 생기는 것이다. 다음으로 행에서 겹치지 않는 것 까지 고려하게 되면
1
2
3
4
5
6
7
8
9
10
11
12
13
14
pos = [0] * N
flag_a = [False] * N
def set_queen(i):
global cnt
for j in range(N):
ifnot flag_a[j]:
pos[i] = j
if i == N - 1:
cnt += 1
else:
flag_a[j] = True
set_queen(i + 1)
flag_a[j] = False
set_queen(0)
flag_a라는 리스트를 통해 해당 행에 퀸이 배치 되었는지를 체크하는 것이 추가되었다. 이렇게 되면 flag_a[0] = True일 경우 해당 행에 이미 퀸이 있으므로 더 이상 이 조합은 고려하지 않아도 되고 flag_a[1] = False 일때 배치를 하는 것이다. 호출한 set_queen(i+1) 함수가 끝이나면 퀸을 다시 제거해 주는 것이다. 다음으로 대각선을 고려하게 되면
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pos = [0] * N
flag_a = [False] * N
flag_b = [False] * (2 * N - 1)
flag_c = [False] * (2 * N - 1)
def set_queen(i):
global cnt
for j in range(N):
if(not flag_a[j] and not flag_b[i + j] and not flag_c[i - j + (N - 1)]):
pos[i] = j
if i == N - 1:
cnt += 1
else:
flag_a[j] = flag_b[i + j] = flag_c[i - j + (N - 1)] = True
set_queen(i + 1)
flag_a[j] = flag_b[i + j] = flag_c[i - j + (N - 1)] = False
set_queen(0)
이렇게 행, 대각선 오른쪽위, 대각선 왼쪽위 로 퀸이 겹쳐서 배치되는 일이 없도록 하는 것이다. 우여곡절 끝이 풀긴 했으나 다음에 시간이 나면 좀 더 고민을 해봐야 할 것 같다. 누구든지 쉽게 이해할 수 있게 설명이 가능해야 이해를 한 것인데 아직 머릿속에서 정리가 안된 것 같다.