Algorithm

[이코테] 5. DFS/BFS - 자료구조 기초

hyeonzzz 2024. 2. 7. 20:50

자료구조 기초

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조

 

삽입 : 데이터를 삽입

삭제 : 데이터를 삭제

오버플로 : 자료구조가 수용할 수 있는 데이터의 크기를 벗어나 넘쳐흐를 때 발생

언더플로 : 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 발생

 

스택

  • 박스 쌓기와 비슷하다
  • 선입후출, 후입선출 구조

 

스택 코드

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)  # 최하단 원소부터 출력
print(stack[::-1])  # 최상단 원소부터 출력

[5, 2, 3, 1]

[1, 3, 2, 5]

 

별도의 라이브러리를 사용할 필요없이 append()와 pop() 메서드를 이용하면 된다

 

큐

  • 대기줄과 비슷하다
  • 선입선출

 

큐 코드

from collections import deque

# 큐 구현을 위해 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) # 나중에 들어온 원소부터 출력

deque([3, 7, 1, 4])

deque([4, 1, 7, 3])

 

파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용한다

deque 객체를 리스트 자료형으로 변경하고자 한다면 list() 메서드를 이용하자

 

재귀 함수

재귀 함수 : 자기 자신을 다시 호출하는 함수

 

재귀 함수 예제

def recursive_function():
  print('재귀 함수를 호출합니다.')
  recursive_function()

recursive_function()

코드를 실행하면 '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력한다. 하지만 무한대로 재귀 호출을 진행하지는 않고 어느 정도 출력하다가 오류 메시지를 출력하고 멈춘다.

 

재귀 함수 종료 조건

재귀 함수를 사용할 때는 종료 조건을 꼭 명시해야 한다.

 

def recursive_function(i):
  # 100번째 출력했을 때 종료되도록 종료 조건 명시
  if i == 100:
    return
  print(i, '번째 재귀 함수에서', i+1, '번째 재귀 함수를 호출합니다.')
  recursive_function(i+1)
  print(i, '번째 재귀 함수를 종료합니다.')

recursive_function(1)

1 번째 재귀 함수에서 2 번째 재귀 함수를 호출합니다.
2 번째 재귀 함수에서 3 번째 재귀 함수를 호출합니다.

...

99 번째 재귀 함수에서 100 번째 재귀 함수를 호출합니다.
99 번째 재귀 함수를 종료합니다.

98 번째 재귀 함수를 종료합니다.

...

1 번째 재귀 함수를 종료합니다.

 

→ 가장 안쪽에 있는 재귀 호출이 먼저 종료되고, 그 이후에 바깥쪽에 있는 재귀 호출이 종료된다.

 

재귀 함수와 스택

  • 재귀 함수의 수행은 스택 자료구조를 이용한다
  • 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다
  • 따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해 간편히 구현될 수 있다. 그 예가 DFS이다

 

팩토리얼 문제

n이 1 이하가 되었을 때 함수를 종료한다. 

# 반복적으로 구현한 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):
  # n이 1 이하인 경우 1을 반환
  if n <= 1:
    return 1
  # n! = n * (n-1)!를 그대로 코드로 작성하기
  return n * factorial_recursive(n-1)

print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))

재귀 함수의 코드가 더 간결하다