-
[DFS / BFS] 스택자료구조, 큐자료구조, 재귀함수코딩/🤦 ALGORITHM 2022. 2. 8. 01:11
그래프 탐색 알고리즘에 있어 대표적인 알고리즘 DFS와 BFS를 알아보기 전에 선행되어야 할 개념이 있다.
바로 스택(stack)자료구조와 큐(Queue)자료구조가 그것이다.
Stack 자료구조
마치 책을 쌓아 놓고 위에서부터 꺼내는 방식의 알고리즘이라고 생각하면 쉽다.
FILO 즉, 선입후출의 방식인 것이다.
예를 들어 삽입을 5 - 2 - 7 - 삭제 - 1 - 4 삭제의 과정이 있다면
stack을 출력하면, 5 2 1 만 밑에서부터 남게 될 것이다.
이를 파이썬 코드로 표현하자면 append와 pop으로 구현할 수 있다.
stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.pop() stack.append(4) print(stack) >>> [5, 2, 3, 4]
큐 자료구조
큐는 마치 파이프에서 물이 빠지듯이 나가는 구조라고 생각하면 된다.
선입후출 (FIFO) 방식으로 먼저 들어온 정보가 먼저 빠져나가는 알고리즘이다.
이를 파이썬 코드로 작성하게 된다면, deque라는 내부라이브러리를 사용할 수 있다.
파이썬 코드로 구현이 가능하지만 deque로 구현하는 것이 더 효율적이라고한다.
from collections import deque queue = deque() queue.append(5) queue.append(2) queue.append(3) queue.append(7) queue.popleft() queue.append(1) queue.append(4) #먼저 들어온 순서부터 queue.reverse() print(queue) >>> deque([4, 1, 7, 3, 2]) #나중에 들어온 순서부터 print(queue) >>> deque([2, 3, 7, 1, 4])
재귀함수
재귀함수란 자기함수를 다시 호출하는 함수로 반복해서 자기를 호출하는 경우 사용한다,
영어로는 Recursive Function이라고 하는데, 반드시 종료조건을 넣어야 멈추게 되는 함수라는 걸 잊지 말아야 한다.
예를 들어보자.
#재귀함수 def recursive_function(i): if i == 10: return print(i,'번째', i+1, '번째 호출') recursive_function(i+1) print(i, '종료')
recursive_function(1) 1 번째 2 번째 호출 2 번째 3 번째 호출 3 번째 4 번째 호출 4 번째 5 번째 호출 5 번째 6 번째 호출 6 번째 7 번째 호출 7 번째 8 번째 호출 8 번째 9 번째 호출 9 번째 10 번째 호출 9 종료 8 종료 7 종료 6 종료 5 종료 4 종료 3 종료 2 종료 1 종료
함수를 호출하는 로직을 살펴보면
- 1번 호출하고 2번째 자기함수를 호출하다가
- 10번째 호출이 되고나서 차례대로 9번째 호출한 것이 종료되고, 8번째 호출한 것이 종료되고
- 마지막으로 1번째가 종료되는 것을 알 수 있다.
마치 스택에서 데이터를 꺼내는 것과 같이 작동하는 것을 알 수 있다.
이를 토대로 팩토리얼과 최대공약수를 구현할 수 있다!
팩토리얼 구현
이를 토대로 팩토리얼을 구현하자면
n! = 1 * 2 * 3 * (n-1) * n
0 ! = 1 ! = 1 이라는 사실은 알아두고 구현하자.
# 팩토리얼 구현예제 def factorial_recursive(n): if n <= 1: return 1 return n * factorial_recursive(n-1)
이를 반복문으로도 구현할 수 있지만, 재귀함수를 통해서 구현할 수 있으며, 시간복잡도 또한 반복문보다 낮은 평가를 받을 수 있어 효율적이다.
최대공약수 구현 (유클리드 호제법)
두개의 자연수에 대한 최대공약수를 찾으려면 두가지 전제조건을 만족시켜야한다.
- 두 자연수 A, B (A>B)에 대해서 A를 B로 나눈 나머지가 R
- 이때, A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다
예를 들어 GCD(192,162)를 구한다고 해보자.
여기서 GCD는 최대공약수를 뜻한다.
A B 192 162 162 30 -> R 30 12 -> R 12 6 -> R 정리하면, 192와 162 최대공약수와 12와 6의 최대공약수가 같다는 것이므로
6 이 최대 공약수인 것이다.
# 재귀함수 def gcd(a,b): # a와 b가 나눴을 때 0이란 말은 a가 b의 배수라는 뜻이다. 전제조건이 (a>b)이기 때문에! if a % b == 0: return b else: # b와 a를 b로 나눈 나머지 R의 최대공약수 return gcd(b, a % b)
gcd(192, 162) >>> 6
참고문헌
더보기이것이 취업을 위한 코딩테스트다 동영상을 공부하고 TIL입니다
'코딩 > 🤦 ALGORITHM' 카테고리의 다른 글
[TEST] Frog Possible Distance (0) 2022.02.16 [BFS] 너비우선탐색 (Breath-First Search) (0) 2022.02.10 [DFS] 깊이탐색알고리즘(Depth-First Search) (0) 2022.02.10 알고리즘 성능평가 (0) 2021.09.19 Selection Sort (선택정렬) (0) 2021.03.19