Search

꼭 필요한 자료구조 기초

기본 자료구조

탐색 알고리즘 DFSBFS 이해를 위해선 기본 자료구조인 스택에 대한 이해가 필수

스택과 큐의 핵심 함수

삽입(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)

자기 자신을 다시 호출하는 함수
DFSBFS 구현을 위해 이해가 필요
무한히 재귀 호출은 되지 않으며, 호출 제한 횟수를 넘어가면 에러
재귀 함수 예제
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
출력 결과

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.