스택과 큐 자료구조
-
그래프 탐색 알고리즘: DFS / BFS
-
탐색(Search)이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정
-
DFS와 BFS가 대표적 그래프 탐색 알고리즘, 코테에 자주 등장
-
스택 자료구조
-
먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
-
입구와 출구가 동일한 형태로 스택 시각화, 예시: 박스 쌓기
-
스택 동작 예시
-
파이썬에선 리스트 자료형 이용
stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack[::1]) # 최상단 원소부터 출력 print(stack) # 최하단 원소부터 출력
-
-
큐 자료구조
- 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
- 입구와 출구가 모두 뚫려있는 터널과 같은 형태로 시각화, 예시: 대기열
- 큐 동작 예시
- 파이썬에선 deque 라이브러리 사용, 리스트를 이용하면 기능적으로는 구현할 수 있지만 시간복잡도가 높음
from collections import deque # 큐 구현을 위해 deque 라이브러리 사용 queue = deque() queue.append() queue.append() queue.append() queue.append() queue.popleft() queue.append() queue.append() queue.popleft() print(queue) # 먼저 들어온 순서대로 출력 queue.reverse() # 역순으로 바꾸기 print(queue) # 나중에 들어온 원소부터 출력- list를 이용해서 pop메소드를 호출해 원소를 꺼낸다면 원소의 위치를 저장하는 과정이 필요하기에 O(K)만큼의 시간복잡도가 필요함, deque를 이용하면 O(1), 즉 상수시간
재귀 함수
-
재귀 함수(Recursive Function): 자기 자신을 다시 호출하는 함수
-
어느 정도 출력하다가 최대 재귀 깊이 초과 메시지 출력
-
예시
def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() -
종료 조건을 명시하지 않으면 함수가 무한히 호출되므로 반드시 명시해야함
def recursive_function(i): if i == 100: return print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출합니다.') recursive_function(i+1) print(i, '번째 재귀함수를 종료합니다.') recursive_function(1) -
팩토리얼 구현 예제
-
0!과 1!의 값은 1
def factorial_recursive(n): if n <= 1: return 1 return n * factorial_recursive(n-1) print(factorial_recursive(5))
-
-
유클리드 호제법
-
두 자연수의 최대공약수를 구하는 방법
-
두 자연수 A, B(A>B)와 나머지 R이 있을 때 A와 B의 최대공약수는 B와 R의 최대공약수와 같음
def gcd(a,b): if a % b == 0: return b else: return gec(b, a % b) print(gcd(192, 162))
-
-
재귀 함수 사용의 유의 사항
- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있고 유리한 경우도 있고 불리한 경우도 있음
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓이므로 스택을 사용해야 할 때 구현상 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많음
참고: 이것이 취업을 위한 코딩 테스트다 with 파이썬 (취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드), 유튜브 강의 영상
