핵심개념 · 필수 코드 산출물 상세 학습

함수 정의는 반복해서 사용할 명령들을 하나의 이름으로 묶는 과정이다. Python에서는 def 키워드와 함수 이름, 괄호, 콜론을 사용하고 함수 본문은 들여쓰기한다. 정의 시점에는 함수 내부 코드가 실행되지 않고, 호출될 때 실행된다.

def greet():
    print("안녕하세요.")

print("함수 정의 완료")

함수 호출은 이미 정의된 함수를 실제로 실행시키는 것이다. 함수 이름 뒤에 괄호를 붙여 호출하며, 인수가 필요한 함수라면 괄호 안에 값을 전달한다. 호출이 끝나면 제어 흐름은 호출한 위치의 다음 문장으로 돌아온다.

def greet():
    print("반갑습니다.")

print("시작")
greet()
print("끝")

복귀는 함수 실행이 끝난 뒤 제어권이 함수 호출 지점으로 돌아오는 것을 뜻한다. return을 만나거나 함수 본문 끝에 도달하면 함수는 종료되고 호출한 곳의 다음 문장이 실행된다.

def show():
    print("함수 안")
    return

print("A")
show()
print("B")

매개변수(parameter)는 함수가 외부에서 값을 받아 사용하기 위해 함수 정의의 괄호 안에 선언하는 변수이다. 호출할 때 전달하는 실제 값을 인수(argument)라고 한다.

def add(a, b):
    print(a + b)

add(3, 5)

반환값은 함수가 처리 결과를 호출한 쪽에 돌려주는 값이다. Python에서는 return 식을 사용한다. 반환값은 변수에 저장하거나 다른 계산에 바로 사용할 수 있다.

def square(x):
    return x * x

n = square(4)
print(n)

지역 변수는 함수 내부에서 만들어져 보통 그 함수 안에서만 사용할 수 있고, 전역 변수는 함수 밖에서 정의되어 여러 영역에서 참조할 수 있다. 함수 내부에서 전역 변수의 값을 직접 변경하려면 global 사용 여부를 주의해야 한다.

x = 10

def test():
    y = 20
    print(x, y)

test()
print(x)

재귀 함수는 함수가 자기 자신을 다시 호출하여 문제를 더 작은 같은 형태의 문제로 바꾸어 해결하는 함수이다. 반드시 더 작은 문제로 진행되어야 하며 종료 조건이 필요하다.

def countdown(n):
    if n == 0:
        return
    print(n)
    countdown(n - 1)

countdown(3)

재귀 호출이 일어날 때 각 함수 호출의 지역 상태와 복귀 위치가 호출 스택에 쌓인다. 가장 나중에 호출된 함수가 먼저 종료되는 LIFO 구조로 복귀한다.

def f(n):
    print("들어감", n)
    if n > 1:
        f(n - 1)
    print("나옴", n)

f(3)

종료 조건(base case)은 더 이상 재귀 호출하지 않고 즉시 결과를 내거나 함수 실행을 끝내는 조건이다. 종료 조건이 없거나 도달하지 못하면 재귀 호출이 계속되어 오류가 발생할 수 있다.

def total(n):
    if n == 1:
        return 1
    return n + total(n - 1)

print(total(4))

한 번의 함수 실행에서 자기 자신을 한 번만 호출하는 형태를 단일 재귀 호출로 볼 수 있다. 카운트다운, 1부터 n까지의 합, 팩토리얼이 대표적이다.

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

print(factorial(5))

재귀에서는 각 호출이 자신만의 매개변수 값을 가진다. 반면 전역 변수는 여러 호출이 함께 공유할 수 있어 호출 횟수 집계 등에 사용할 수 있지만, 함수의 독립성을 떨어뜨릴 수 있으므로 신중히 사용한다.

calls = 0
def f(n):
    global calls
    calls += 1
    if n <= 0:
        return
    f(n - 1)

f(3)
print(calls)

한 번의 함수 실행에서 자기 자신을 두 번 이상 호출하는 재귀를 다중 재귀라고 할 수 있다. 피보나치 재귀처럼 동일한 부분 문제가 반복 계산될 수 있어 호출 수가 빠르게 늘어날 수 있다.

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(6))

피보나치 수열은 F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)로 정의할 수 있다. 이 수학적 정의를 그대로 재귀 함수로 옮길 수 있지만, 효율성 측면에서는 메모이제이션이나 반복문이 유리할 수 있다.

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

for i in range(7):
    print(fib(i), end=" ")

하노이 탑은 n개의 원판을 한 기둥에서 다른 기둥으로 옮기는 재귀 문제이다. n-1개를 보조 기둥으로 옮기고, 가장 큰 원판을 목표 기둥으로 옮긴 뒤, 다시 n-1개를 목표 기둥으로 옮긴다.

def hanoi(n, start, temp, end):
    if n == 1:
        print(start, "->", end)
        return
    hanoi(n-1, start, end, temp)
    print(start, "->", end)
    hanoi(n-1, temp, start, end)

hanoi(3, "A", "B", "C")

반복은 for/while로 같은 처리를 되풀이하고, 재귀는 함수 호출 구조로 같은 형태의 작은 문제를 해결한다. 반복은 보통 호출 스택 부담이 적고, 재귀는 문제의 구조를 직관적으로 표현할 수 있다는 장점이 있다.

def sum_loop(n):
    s = 0
    for i in range(1, n+1):
        s += i
    return s

def sum_rec(n):
    if n == 0:
        return 0
    return n + sum_rec(n-1)

재귀 문제를 설계할 때는 ① 가장 작은 문제의 정답인 종료 조건을 정하고 ② 큰 문제를 더 작은 같은 형태의 문제로 바꾸며 ③ 매 호출마다 종료 조건에 가까워지는지 확인한다.

def power(a, n):
    if n == 0:
        return 1
    return a * power(a, n-1)

print(power(2, 5))

큐(queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In, First Out) 자료구조이다. 줄 서기, 프린터 대기열, BFS 탐색 등에 활용된다.

queue = []
queue.append("A")
queue.append("B")
queue.append("C")
print(queue.pop(0))

front는 다음에 삭제될 데이터가 있는 큐의 앞쪽, rear는 새 데이터가 삽입되는 뒤쪽을 의미한다. 구현 방식에 따라 인덱스나 포인터로 관리할 수 있다.

queue = ["A", "B", "C"]
front = 0
rear = len(queue) - 1
print(queue[front], queue[rear])

큐의 삽입(enqueue)은 뒤쪽에 데이터를 추가하고, 삭제(dequeue)는 앞쪽 데이터를 꺼내는 연산이다. 빈 큐에서 삭제할 때는 언더플로 상황을 처리해야 한다.

q = []
q.append(10)   # enqueue
q.append(20)
x = q.pop(0)   # dequeue
print(x, q)

Python 리스트로도 큐를 만들 수 있지만 pop(0)은 뒤 원소들을 이동시켜 비효율적일 수 있다. collections.deque는 양쪽 끝 삽입·삭제에 최적화되어 큐 구현에 적합하다.

from collections import deque

q = deque()
q.append(1)
q.append(2)
print(q.popleft())

스택(stack)은 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last In, First Out) 자료구조이다. 실행 취소, 함수 호출 스택, 괄호 검사 등에 사용된다.

stack = []
stack.append("A")
stack.append("B")
stack.append("C")
print(stack.pop())

top은 스택의 맨 위 원소를 가리키는 개념이다. 보통 다음에 pop될 원소가 top이며, 리스트 구현에서는 마지막 원소가 top 역할을 한다.

stack = [10, 20, 30]
top = stack[-1]
print(top)

push는 스택 위에 새 데이터를 넣는 연산이고, pop은 스택 위 데이터를 제거하며 꺼내는 연산이다. Python 리스트의 append와 pop을 그대로 활용할 수 있다.

s = []
s.append(1)  # push
s.append(2)
x = s.pop()  # pop
print(x)

괄호 문자열 검사에서는 여는 괄호를 스택에 넣고, 닫는 괄호를 만나면 스택의 top과 짝이 맞는지 확인한다. 모든 문자를 처리한 뒤 스택이 비어 있어야 올바른 괄호열이다.

def valid(text):
    stack = []
    for ch in text:
        if ch == "(":
            stack.append(ch)
        elif ch == ")":
            if not stack:
                return False
            stack.pop()
    return not stack

print(valid("(())"))

스택에 문자를 순서대로 push한 뒤 모두 pop하면 입력의 역순으로 나온다. 이 성질을 이용하면 문자열 뒤집기를 구현할 수 있다.

text = "ABC"
stack = list(text)
result = ""
while stack:
    result += stack.pop()
print(result)

처리 순서가 도착 순서와 같아야 하면 큐, 가장 최근 상태부터 되돌아가야 하면 스택이 적합하다. 문제에서 '먼저 온 순서', '되돌아가기', '중첩' 같은 표현을 단서로 판단할 수 있다.

# 프린터 작업: 큐
# 실행 취소: 스택

자료구조 문제에서는 각 연산 후 내부 상태를 표나 순서로 기록하면 오류를 줄일 수 있다. enqueue/push로 무엇이 추가되고 dequeue/pop으로 무엇이 제거되는지 단계별로 추적한다.

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

프린터 작업은 일반적으로 먼저 들어온 작업부터 출력하는 큐로 모델링할 수 있다. 우선순위가 있다면 단순 큐보다 우선순위 큐가 필요할 수 있지만, 기본 선착순 모델은 FIFO이다.

from collections import deque
jobs = deque(["A.pdf", "B.pdf", "C.pdf"])
while jobs:
    print("인쇄:", jobs.popleft())

후위 표기식 계산에서는 피연산자를 스택에 넣고 연산자를 만나면 필요한 피연산자를 pop하여 계산한 뒤 결과를 다시 push한다. 괄호와 연산자 우선순위를 별도로 처리하지 않아도 된다는 장점이 있다.

# 후위식: 2 3 + 4 *
stack = []
stack.append(2)
stack.append(3)
b = stack.pop(); a = stack.pop()
stack.append(a + b)
stack.append(4)
b = stack.pop(); a = stack.pop()
stack.append(a * b)
print(stack.pop())

그래프는 정점(vertex)과 정점을 연결하는 간선(edge)으로 구성된다. 사람-친구 관계, 도시-도로, 웹페이지-링크 등 다양한 관계를 표현할 수 있다.

vertices = ["A", "B", "C"]
edges = [("A","B"), ("B","C")]
print(vertices, edges)

방향 그래프는 간선에 방향이 있어 A→B와 B→A를 구분한다. 무방향 그래프는 연결 방향을 구분하지 않아 A-B와 B-A가 같은 간선이다.

directed = {"A": ["B"], "B": []}
undirected = {"A": ["B"], "B": ["A"]}

가중 그래프에서는 간선에 거리, 비용, 시간 같은 수치를 부여한다. 최단 경로 문제에서는 이 가중치를 이용해 경로의 총 비용을 비교한다.

graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("C", 1)]
}

인접행렬은 정점 수가 n일 때 n×n 행렬로 연결 관계를 나타낸다. 두 정점의 연결 여부를 빠르게 확인할 수 있지만 정점 수가 크고 간선이 적으면 공간을 많이 사용할 수 있다.

matrix = [
    [0,1,1],
    [1,0,0],
    [1,0,0]
]
print(matrix[0][2])

인접리스트는 각 정점마다 연결된 이웃 정점 목록을 저장한다. 간선 수가 적은 희소 그래프에서 공간 효율이 좋고, 특정 정점의 이웃을 순회하기 편하다.

graph = {
    0: [1,2],
    1: [0],
    2: [0]
}
print(graph[0])

루트(root)는 트리의 가장 위에 있는 시작 정점으로, 부모가 없는 노드이다. 하나의 일반적인 트리는 하나의 루트를 기준으로 계층 구조를 표현한다.

tree = {
    "A": ["B", "C"],
    "B": [],
    "C": []
}
root = "A"
print(root)

트리에서 직접 연결된 상하 관계를 부모(parent)와 자식(child)이라고 한다. A가 B와 C의 상위 노드라면 A는 부모, B와 C는 자식이다.

tree = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": [],
    "D": []
}

리프(leaf)는 자식이 없는 끝 노드이다. 파일 시스템의 빈 폴더/파일 구조, 의사결정트리의 최종 분류 결과 등에서 말단 노드 개념으로 활용된다.

tree = {
    "A": ["B", "C"],
    "B": [],
    "C": ["D"],
    "D": []
}
leaves = [v for v, children in tree.items() if not children]
print(leaves)

노드의 깊이(depth)는 보통 루트에서 그 노드까지의 간선 수로 정의한다. 트리의 높이(height)는 가장 깊은 리프까지의 최대 깊이로 정의하는 경우가 많다.

# A(depth 0)
# ├─ B(depth 1)
# │  └─ D(depth 2)
# └─ C(depth 1)

트리는 각 노드의 자식 목록을 인접리스트 형태로 저장하거나, 이진트리라면 left/right 참조를 가진 노드 객체로 표현할 수 있다.

tree = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": [],
    "D": []
}

for child in tree["A"]:
    print(child)

이진트리 순회는 방문 순서에 따라 전위(루트-왼쪽-오른쪽), 중위(왼쪽-루트-오른쪽), 후위(왼쪽-오른쪽-루트)로 구분한다.

#     A
#    / \
#   B   C
# 전위: A B C
# 중위: B A C
# 후위: B C A

트리는 그래프의 특수한 형태로 볼 수 있다. 일반적인 연결 무방향 트리는 모든 정점이 연결되어 있고 사이클이 없으며, 정점이 n개일 때 간선이 n-1개이다.

# 정점 4개, 간선 3개인 연결 무방향 무사이클 그래프
graph = {
    0: [1,2],
    1: [0,3],
    2: [0],
    3: [1]
}

BFS(너비 우선 탐색)는 시작 정점에서 가까운 정점부터 층별로 탐색한다. 일반적으로 큐를 사용하며, 방문 여부를 기록해 같은 정점을 반복 방문하지 않도록 한다.

from collections import deque

graph = {0:[1,2], 1:[0,3], 2:[0], 3:[1]}
visited = {0}
q = deque([0])

while q:
    cur = q.popleft()
    print(cur, end=" ")
    for nxt in graph[cur]:
        if nxt not in visited:
            visited.add(nxt)
            q.append(nxt)

DFS(깊이 우선 탐색)는 한 경로를 가능한 깊게 따라간 뒤 더 갈 곳이 없으면 되돌아와 다른 경로를 탐색한다. 재귀 호출이나 명시적 스택으로 구현할 수 있다.

graph = {0:[1,2], 1:[0,3], 2:[0], 3:[1]}
visited = set()

def dfs(v):
    visited.add(v)
    print(v, end=" ")
    for nxt in graph[v]:
        if nxt not in visited:
            dfs(nxt)

dfs(0)

연결 요소는 서로 경로로 도달 가능한 정점들의 묶음이다. 모든 정점을 훑으면서 아직 방문하지 않은 정점에서 BFS나 DFS를 새로 시작하면 연결 요소의 개수를 셀 수 있다.

graph = {0:[1], 1:[0], 2:[3], 3:[2]}
visited = set()
count = 0

for v in graph:
    if v not in visited:
        count += 1
        stack = [v]
        visited.add(v)
        while stack:
            cur = stack.pop()
            for nxt in graph[cur]:
                if nxt not in visited:
                    visited.add(nxt)
                    stack.append(nxt)

print(count)

경로 탐색은 시작 정점에서 목표 정점까지 도달 가능한 연결 순서를 찾는 문제이다. BFS는 가중치가 없는 그래프에서 최단 간선 수 경로를 찾는 데 적합하고, DFS는 경로 존재 여부나 깊은 탐색에 활용할 수 있다.

# BFS에서 parent를 기록하면 경로를 복원할 수 있다.
parent = {0: None, 1: 0, 3: 1}
# 0 -> 1 -> 3

문제를 풀 때는 데이터 관계와 필요한 연산을 기준으로 구조를 선택한다. 선착순은 큐, 최근 상태 복원은 스택, 일반 관계망은 그래프, 계층 구조는 트리가 자연스럽다.

examples = {
    "프린터 대기열": "queue",
    "실행 취소": "stack",
    "도로망": "graph",
    "폴더 계층": "tree"
}
print(examples)