기본 자료구조
•
탐색 알고리즘 DFS와 BFS 이해를 위해선 기본 자료구조인 스택과 큐에 대한 이해가 필수
스택과 큐의 핵심 함수
•
삽입(Push) : 데이터를 삽입
•
삭제(Prop) : 데이터를 삭제
스택 (Stack)
선입후출(FILO) or 후입선출(LIFO) 구조
•
스택은 라이브러리 사용할 필요 X
•
기본 리스트의 append()와 pop() 메소드가 스택 자료구조에서도 동일하게 동작
•
스택 예제
stack []
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) -삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack) # 최하단 원소부터 출력
print(stack[::01]) # 최상단 원소부터 출력
Python
출력 결과
큐 (Queue)
선입선출(FIFO) 구조
•
파이썬에서 큐 사용을 위해선 collections 모듈의 deque 자료구조 활용
•
deque
◦
스택과 큐의 장점을 모두 채택
◦
데이터 삽입과 삭제 속도가 리스트에 비해 효율적
◦
queue 라이브러리를 이용하는 것보다도 간단
◦
deque 객체를 리스트 자료형으로 변환하고 싶으면 list() 메소드 이용
▪
list(queue)
•
큐 예제
from collections import deque
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력
Python
출력 결과
재귀 함수 (Recursive Function)
•
자기 자신을 다시 호출하는 함수
•
DFS와 BFS 구현을 위해 이해가 필요
•
무한히 재귀 호출은 되지 않으며, 호출 제한 횟수를 넘어가면 에러
•
재귀 함수 예제
def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_fuction()
recursive_function()
Python
재귀 함수의 종료 조건
•
재귀 함수를 사용할 때는 반드시 종료 조건을 명시!
◦
재귀 함수가 언제 끝날지 정해 주어야, 무한 호출되지 않음.
•
재귀 함수 종료 예제
def recursive_function():
# 100번째 출력했을 때 종료되도록 종료 조건 명시
if i == 100:
return
print(i, '번째 재귀 함수에서', i + 1, '번째 재귀 함수를 호출합니다.')
recursive_function(i + 1)
print(i, '번째 재귀 함수를 종료합다.')
recursive_function(1)
Python
재귀 함수는 내부적으로 스택 자료구조와 동일!
•
연속으로 호출되는 함수는 메인 메모리의 스택 공간에 적재됨.
◦
마지막으로 호출된 함수가 수행 후 종료되야, 그 앞 함수 호출이 종료됨.
→ 스택을 활용하는 상당수 알고리즘은 재귀함수로 간편히 구현 가능
•
2가지 방식으로 구현한 팩토리얼 예제
# 반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
# 1부터 n까지의 수를 차례대로 곱하기
for i in range(1, n + 1):
result *= i
return result
# 재귀적으로 구현한 n!
def factorial_recursive(n):
if n <= 1: # n이 1 이하인 경우 1을 반환
return 1
# n! = n * (n - 1)!를 그대로 코드로 작성하기
return n * factorial_recursive(n - 1)
# 각각의 방식으로 구현한 n! 출력(n = 5)
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))
Python
출력 결과