#점화식 #분할정복 #피보나치 수열
1) 개념
- 점화식
- 반드시 종료하기 위한 초기 조건이 있어야 한다.
- n! = n * (n-1)!
- 수학적 귀납법
- p(1)이 성립한다.
- p(n)이 성립하면, p(n+1)도 성립한다.
- 피보나치 수열 : 첫째 둘째 항은 1이고, 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열
2) 재귀 알고리즘 분석
- 상향식 분석 : 큰 값에서 작은 값으로 줄여 가면서 데이터의 변화(이동)을 파악한다.
- 하향식 분석 : 작은 값에서 큰 값으로 늘려 가면서 데이터의 변화(이동)을 파악한다.
- 재귀 → 비재귀 : 꼬리 재귀를 제거하거나, 스택을 이용해 재귀를 제거한다.
잠깐! 재귀호출, 왜 알아야 할까?
비효율적이나, 꼭 필요할 때가 있어서? → 분할 정복 알고리즘에 사용됨! → 이는 곧 merge sort의 작동 방식
3) 재귀호출을 점화식/수학적 귀납법과 연관지어 생각해야 하는 이유
- 점화식은 n번째 텀을 이전 텀들과의 관계로 표현해야 한다.
- 근데 우리는 이 점화식을 solve 즉, explict formula (명시적인 식)으로 표현할 수 있어야 한다.
- 다시 말해,
f(n) = n * f(n-1)이러한 식을 n에 대한 수식으로 표현할 수 있어야 한다는 것이다. - 왜? → 시간복잡도를 계산하려면 n에 대한 수식으로 다뤄야 하고, 이는 곧 세타 n이 되기 때문!
▶ 알고리즘 중 ‘분할정복’ 기법에서는 시간복잡도 함수가 반드시 점화식의 형태로 나온다.
▶ (왜?) 재귀함수(호출)에 대한 시간복잡도는 반드시 점화식의 형태로 나오기 때문이다. 따라서, 점화식이 주어졌을 때 n에 대한 수식으로 바꾸는 것이 중요하다!
▶ 그래야지 시간복잡도를 구할 수 있다.
4) 대표 예1. 피보나치 수열
def fibo(n: int) -> int:
if n == 1 or n == 2:
return 1
else:
return fibo(n-1) + fibo(n-2)→ 일반적이나, 비효율적 (함수 호출에 따른 오버헤드 + 매번 중복 계산)
▶ 효율적으로 하려면 동적 프로그래밍 기법으로 가야! / 아니면 반복문 활용 재귀로..
즉, 배열에 저장해서 필요할 때마다 꺼내 쓴다. (여기) https://richwind.co.kr/3
피보나치 수열 시간복잡도 계산
- 이전 텀을 한 번 쓰면 1차 → iteration 기법으로, (즉, 반복하면서 규칙을 찾아내어 n에 대한 식을 만들기) / 두 번 쓰면 2차
- 피보나치 수열은 두 번 쓰므로 2차가 된다.
(피보나치 수열 풀이 방정식 업로드)
5) 대표 예2. 팩토리얼
# 양의 정수 n의 팩토리얼 값을 재귀적으로 구함
def factorial(n: int) -> int:
if n >= 1:
return n * factorial(n-1)
else:
return 14) 대표 예2. 유클리드 호제법
# 정숫값 x와 y의 최대 공약수를 반환
def gcd(x: int, y: int) -> int:
if y == 0:
return x
else:
return gcd(y, x % y)5) 대표 예3. 하노이의 탑
# 원반 no개를 start 기둥에서 end 기둥으로 옮김
def move(no: int, start: int, end: int) -> None:
if no > 1:
move(no-1, start, 6-start-end)
print(f'원반 [{no}]을(를) {start}기둥에서 {end}기둥으로 옮깁니다.')
if no > 1:
move(no-1, 6-start-end, end)우선, 문제에서 "뭘 해야 하는지"를 명확하게 명시하고 시작한다.
move(no, start, end) → 즉, no개의 원반을 start에서 end로 옮긴다.
그 다음, 전체적인 로직을 그려본다. (6-start-end == mid라 간주하겠다.)
1. move(no-1, start, mid)
2. move(1, start, end) → print(no, start, end)
3. move(no-1, mid, end)
재귀함수와 점화식/수학적 귀납법은 서로 연관되어 있다.
"p(1)이 참이라 가정할 때, p(n-1)이 참이면 p(n)도 참이다"라는 수학적 귀납법을 적용함에 있어서, 재귀함수도 마찬가지로 종료 조건이 반드시 필요하다!
여기서 종료조건은 n == 1일 때라고 볼 수 있다.
6) 대표 예4. 8퀸 문제 (N-Queen)
대표적인 DFS과 backtracking 문제이다.
DFS(Depth First Search)란,
- 그래프의 탐색 방법 중 하나로, 루트 노드(혹은 다른 임의의 노드)부터 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.
- 즉, 넓게 탐색하기 전에 깊게 탐색하는 것이다.
- 그래프의 경우, 어떤 노드를 방문했는지 반드시 검사해야 한다. (무한 루프에 빠질 수 있기 때문)
- DFS는 모든 노드를 방문해야 할 때 사용한다.
backtracking이란,
- 모든 경우의 수를 전부 고려하는 알고리즘이다.
- 답을 찾아가는 도중 막히면, 다시 역추적해서 돌아가 결국에는 답을 찾아가는 방법이다.
- 상태공간트리(State Space Tree)에서 DFS와 함께 탐색 알고리즘으로 사용된다.
# 일반적인 백트래킹 알고리즘
class Node:
...
def checknode (v: Node) -> None:
u = Node()
if promising(v):
if (v에 해답이 있으면)
해답을 출력;
else:
for (v의 모든 자식 노드 u에 대해서)
checknode(u)
결국 8퀸(N퀸) 문제를 풀기 위해,
일반적인 백트래킹 알고리즘과 promising() 함수를 구현함으로써, 해당 노드의 유망성(즉, 정답이 있는지)를 파악하고 없다면 필요없는 자식 노드들은 가지치기 한다.
조금 스포하자면, 결과를 출력했을 때 결과값이 대칭을 이룬다는 사실 또한 알 수 있다.
⭐ 분할 정복법 (분할 해결법)
- 큰 문제를 작은 문제로 분할하고, 작은 문제 풀이법을 결합하여 전체 풀이법을 얻는 방법
- 문제를 분할할 때 작은 문제 풀이법에서 원래의 문제 풀이법을 쉽게 도출할 수 있도록 설계해야 한다.
방법1. 배열을 이용
# 8퀸 문제 알고리즘 구현하기 (배열 활용)
pos = [0] * 8 # 각 열에 배치한 퀸의 위치
flag_a = [False] * 8 # 각 행에 퀸을 배치했는지 체크
flag_b = [False] * 15 # 대각선(/) 방향으로 퀸을 배치했는지 체크
flag_c = [False] * 15 # 대각선(/ 반대) 방향으로 퀸을 배치했는지 체크
""" 함수 1) 각 열에 배치한 퀸의 위치를 출력 """
def put() -> None:
for i in range(8):
print(f'{pos[i]:2}', end=' ')
print()
""" 함수 2) i열의 알맞은 위치에 퀸을 배치 """
def set(i: int) -> None:
for j in range(8):
if ( not flag_a[j] # j행에 퀸이 배치되지 않았다면
and not flag_b[i + j] # 대각선 방향(/)으로 퀸이 배치되지 않았다면
and not flag_c[i - j + 7]): # 대각선 방향(/ 반대)로 퀸이 배치되지 않았다면
pos[i] = j
if j == 7:
put()
else:
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = True
set(i+1) # 다음 열에 퀸을 배치
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = False
flag_a와 flag_b는 대각선의 인덱스로 0 ~ 2 * (n - 1)까지이다.
(4 x 4 이상부터 직접 그려보면 그 규칙을 찾을 수 있었다.)
방법2. 백트래킹 기본 알고리즘을 이용
이건 백준 풀이에 설명하겠다.
