자료구조

탐색^Search이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다.

자료구조^{Data structure}란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 그 중 스택과 큐는 자료구조의 기초 개념으로 다음의 둗 핵심적인 함수로 구성된다.

• 삽입(Push): 데이터를 삽입한다.
• 삭제(Pop): 데이터를 삭제한다.

스택과 큐를 사용할 떄는 삽입과 삭제 외에도 오버플로나 언더플로를 고민해야 한다.

• 오버플로^Overflow: 저장 공간을 벗어나 데이터가 넘쳐흐를 때 발생
• 언더플로^Underflow: 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 발생

스택

박스 쌓기에 비유할 수 있다. 아래에서부터 위로 차곡차곡 쌓인다. 이러한 구조를 선입후출^{First In Las Out}구조 또는 후입선출^{Last In First Out}구조라고 한다.

큐

대기 줄에 비유할 수 있다. 나중에 온 데이터일수록 나중에 들어가기 때문에 흔히 ‘공정한’ 자료구조라고 비유된다. 이러한 구조를 선입선출^{First In First Out}구조라고 한다.

재귀 함수

재귀 함수^{Recursive Function}란 자기 자신을 다시 호출하는 함수를 의미한다.

아래 코드를 실행하면 ‘재귀 함수를 호출합니다.’라는 문자열을 무한히 출력한다. 어느 정도 출력되면 재귀의 최대 깊이를 초과했다는 오류 메세지를 출력하고 멈출 것이다.

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

recursive_function()

재귀 함수를 이용하는 대표적인 예제로는 팩토리얼^Factorial 문제가 있다. 팩토리얼 기호는 느낌표(!)를 사용하며 n!는 1 x 2 x 3 x … x (n - 1) x n을 의미한다.

팩토리얼을 반복적으로 구현한 방식과 재귀적으로 구현한 두 방식을 비교해보자.

# 반복적으로 구현한 n!
def factorial_iterative(n):
    result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n + 1):
        result *= i
    return result

# 재귀적으로 구현한 n!
def factorial_iterative(n):
    if n <= 1:  # n이 1이하인 경우 1을 반환
        return 1
    # n! = n * (n - 1)를 그대로 코드로 작성하기
    return n * factorial_iterative(n - 1)

실행 결과는 동일하다. 하지만 재귀 함수의 코드가 더 간결한 것을 알 수 있다. 이렇게 간결해진 이유는 재귀 함수가 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 떄문이다.

단, 재귀 함수를 이용할 때는 꼭 종료 조건을 구현해주자.

ref
이것이 취업을 위한 코딩 테스트다 with 파이썬
나동빈 유튜브 강의