[ 이것이 코딩테스트다 ] 13일차

안영우·2021년 1월 13일

[ 이것이 취업을 위한 코딩 테스트다. with 파이썬 ]

목록 보기

13/39

✏️ 서론

지난 챕터에서는 구현알고리즘(완전탐색, 시뮬레이션)을 배웠다.
이번 챕터에서는 DFS / BFS를 배워볼텐데,
주요 내용을 배우기에 앞서 탐색(Search)과 자료구조(Data Structure)를 알아보자.

✏️ 본론

탐색(Search)이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정을 의미한다.

프로그래밍에서는 그래프, 트리 등 자료구조 안에서 탐색을 하는 문제를 자주 다루는데, 대표적인 탐색 알고리즘은 DFS와 BFS를 꼽을 수 있다.

그런데, DFS와 BFS를 이해하려 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 하므로 사전 학습으로 스택과 큐, 재귀함수를 간단히 배워보자.

자료구조(Data Structure)란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다.

그 중 스택(Stack)과 큐(Queue)는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다.

삽입(Push): 데이터를 삽입한다.

삭제(Pop): 데이터를 삭제한다.

실제로 스택(Stack)과 큐(Queue)를 사용할 때 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야한다.

오버플로(Overflow): 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득찬 상태에서 삽입 연산을 수행할 때 발생한다. 즉, 저장 공간을 벗어나 데이터가 넘쳐흐를 때 발생한다.

언더플로(Underflow): 특정한 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는상태 즉, 더 이상 빠져 나갈 데이터가 존재하지 않을 때 발생한다.

📍 스택(Stack)

스택은 박스쌓기에 비유할 수 있다.
흔히 Box를 쌓는 모습을 연상하면 되는데 이러한 구조를 선입후출(First In Last Out) 또는 후입선출(Last In First Out) 구조라고 한다.

쉽게 말해, 먼저 들어온 수는 가장 나중에 나간다. 이때 시간복잡도는 O(1)이다.
다음은 간단한 스택(Stack)코드이다.

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)
👉🏽 [5, 2, 3, 1]

print(stack[::-1])
👉🏽 [1, 3, 2, 5]

파이썬에서 스택(Stack)을 이용할 때 별도의 라이브러리를 사용할 필요가 없다.
기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 작용한다.

append(): 가장 뒤쪽 데이터 삽입

pop(): 가장 뒤쪽 데이터를 꺼냄

📍 큐(Queue)

큐는 놀이공원에 입장하는 대기 줄에 비유할 수 있다.
새치기가 없다고 가정하면 먼저 줄은 선 사람은 먼저 놀이기구를 탑승 할 수 있다.
이러한 구조를 선입선출(First In First Out) 구조라고 한다.

다음은 간단한 큐(queue) 코드이다.

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)
👉🏽 deque([3, 7, 1, 4])
print(list(queue))
👉🏽 [3, 7, 1, 4]

queue.reverse()
print(queue)
👉🏽 deque([4, 1, 7, 3])
print(list(queue))
👉🏽 [4, 1, 7, 3]

파이썬으로 queue를 구현할때는 collection에서 제공하는 deque 자료구조를 활용하자. deque는 스택과 큐의 장점을 모두 채택한 것인데, 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다.
deque 객체를 리스트 자료형으로 변경할때는 마지막에 list()를 붙여주자.

📍 재귀함수(Recursive_function)

자기 자신을 다시 호출하는 함수이다. 가장 간단한 식을 살펴보자.

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

print(recursive_function())

RecursionError: maximum recursion depth exceeded while calling a Python object

실행시키면 다음과 같은 오류메시지를 볼 수 있는데, 이 오류메시지는 재귀의 최대 깊이를 초과했다는 내용이다.
보통 파이썬 인터프리터는 호출 횟수 제한이 있는데 이 한계를 벗어났기 때문이다. 따라서 무한대로 재귀 호출을 진행 할 수는 없다.

대신, 다음과 같이 종료조건을 준다.

def recursive_function(i):
    if i == 3:
        return
    print(f'{i}번째에서 {i+1}번째 재귀 함수를 호출합니다.')
    recursive_function(i+1)
    print(f'{i}번째에서 함수를 종료합니다.')

recursive_function(1)
👉🏽1번째에서 2번째 재귀 함수를 호출합니다.
2번째에서 3번째 재귀 함수를 호출합니다.
3번째에서 4번째 재귀 함수를 호출합니다.
4번째에서 5번째 재귀 함수를 호출합니다.
4번째에서 함수를 종료합니다.
3번째에서 함수를 종료합니다.
2번째에서 함수를 종료합니다.
1번째에서 함수를 종료합니다.

재귀 함수의 수행은 스택(Stack) 자료구조를 이용한다.
함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.
(스택구조는 선입후출 방식이다.)
결론적으로 재귀함수는 내부적으로 스택 자료구조와 동일하다는 것만 기억하자.

재귀함수를 이용하는 문제는 대표적으로 팩토리얼(factorial) 문제가 있다. 팩토리얼문제는 반복문, 재귀함수방식으로 풀 수 있다.

# 반복문
def for_factorial(n):
    result = 1
    for i in range(1, n+1):
        result = result * i
    return result

print(for_factorial(5))
👉🏽 120

# 재귀함수
def recursive_factorial(n):
    if n <= 1:
        return 1
    
    return result * for_factorial(n-1)

print(recursive_factorial(5))
👉🏽 120