꼭 필요한 자료구조 기초

이것이 취업을 위한 코딩 테스트다 with 파이썬을 공부하면서 정리한 내용입니다.

---

• 탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
  • 대표적인 탐색 알고리즘: DFS, BFS
• DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 필요
• 자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조
• 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성됨
  • 삽입(Push): 데이터를 삽입
  • 삭제(Pop): 데이터를 삭제
• 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야 함
  • 오버플로: 특정한 자료구조가 수용할 수 있는 데이터의 크기가 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생, 즉 저장 공간을 벗어나 데이터가 넘쳐흐를 때 발생
  • 언더플로: 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생

---

스택

• 스택은 박스 쌓기에 비유할 수 있음
• 박스는 아래에서부터 위로 차곡차곡 쌓아야 하고 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려 놓아야 함
• 스택은 선입후출(First In Last Out) 구조
• 파이썬에서 스택을 이용할 때 별도의 라이브러리를 사용할 필요는 없음
• 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작
  • 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[::-1]) # 최상단 원소부터 출력

[5, 2, 3, 1]
[1, 3, 2, 5]

---

큐

• 큐는 대기 줄에 비유할 수 있음
• 놀이공원에 입장하기 위해 줄을 설 때, 먼저 온 사람이 먼저 들어가게 됨
• 나중에 온 사람일수록 나중에 들어감
• 큐는 선입선출(First In First Out) 구조
• 파이썬에서 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용
• deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단
• deque 객체를 리스트 자료형으로 변경하려면 list()를 사용
• 대부분의 코딩 테스트는 collections 모듈과 같은 기본 라이브러리 사용을 허용
• 파이썬에서 큐를 사용한 예시 코드

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) # 나중에 들어온 원소부터 출력

---

재귀 함수

• 재귀 함수란 자기 자신을 다시 호출하는 함수
• 간단한 재귀 함수는 다음과 같음

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

recursive_function()

재귀 함수의 종료 조건

• 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 함
• 종료 조건을 명시하지 않으면 함수가 무한 호출될 수 있음
• 재귀 함수를 100번 호출하도록 작성한 코드 예시는 다음과 같으며 if문이 종료 조건 역할을 수행

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

recursive_function(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)

# 각각의 방식으로 구현한 n! 출력(n = 5)
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))

반복적으로 구현: 120
재귀적으로 구현: 120

• 실행 결과는 동일하나 재귀 함수를 사용하면 코드가 더 간결해짐
• 재귀 함수의 코드가 간결한 이유는 수학의 점화식(재귀식)을 그대로 코드로 옮겼기 때문
• 수학에서 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미
• 팩토리얼을 수학적 점화식으로 표현하면 다음과 같음
  1. n이 0 혹은 1일 때: $factorial(n) = 1$
  2. n이 1보다 클 때: $factorial(n) = n \times factorial(n - 1)$
• 일반적으로 점화식에서 종료 조건을 찾을 수 있음
• 재귀 함수 내에서 특정 조건일 때 더 이상 재귀적으로 함수를 호출하지 않고 종료하도록 if문을 이용하여 꼭 종료 조건을 구현해야 함