꼭 필요한 자료구조 기초

이코테 124p

탐색

• 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• DFS / BFS가 해당됨

자료구조

• 데이터를 표현하고 관리하고 처리하기 위한 구조(오버플로와 언더플로 고려)
  • push : 데이터 삽입
  • pop : 데이터 삭제

스택

• 선입 후출

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
stack.pop()
stack.append(4)
print(stack)

큐

• 선입 선출
• deque를 사용하는 것이 list 자료형에서 pop, push 하는 것보다 더 좋음.

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.popleft()

print(queue)
queue.reverse()
print(queue)

재귀함수

• DFS / BFS를 구현하려면 재귀함수를 이해하고 있어야 한다.
• 재귀함수 : 자기 자신을 다시 호출하는 함수
• 종료 조건을 꼭 명시해주어야 한다.

재귀함수를 안썼을 때

def factorial_iterative(n):
    result = 1
    for i in range(n):
        result *= i + 1
    return result

재귀함수를 썼을 때

def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)