동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나누어 해결하고, 그 결과를 저장해두었다가 재사용하는 방식이다. 핵심 아이디어는 단순하다. 이미 한 번 계산한 값을 다시 계산하지 말자는 것이다. 계산 결과를 어딘가에 저장해두고, 같은 문제가 다시 등장하면 바로 꺼내서 사용하는 방식이다.

DP가 필요한 이유는 보통 같은 계산이 반복적으로 발생할 때다. 단순한 반복문이나 재귀로 문제를 풀면, 눈에 보이지 않게 같은 계산을 여러 번 수행하는 경우가 많다. 이때 DP를 사용하면 불필요한 반복을 제거할 수 있고, 시간 복잡도를 크게 줄일 수 있다.

하지만 모든 문제에 DP를 적용할 수 있는 것은 아니다. DP가 의미를 가지려면 반드시 두 가지 조건이 만족되어야 한다.

첫 번째 조건은 부분 문제의 중복이다. 문제를 작은 단위로 나눴을 때, 동일한 하위 문제가 여러 번 등장해야 한다. 예를 들어 어떤 값을 구하기 위해 이전 값들을 참고해야 하는 상황에서, 같은 값이 계속 필요해진다면 이 조건을 만족한다. 만약 모든 하위 문제가 매번 새롭고 한 번만 사용된다면, 저장해두는 것 자체가 의미가 없다.

두 번째 조건은 최적 부분 구조다. 이는 큰 문제의 정답이, 그보다 작은 문제들의 정답을 조합해서 만들어질 수 있다는 뜻이다. 즉, 전체 문제의 최적해를 구하는 과정에서 중간 단계의 선택 역시 항상 최적이어야 한다. 작은 문제에서 이미 최적이 아닌 선택을 해버리면, 나중에 아무리 잘 조합해도 전체 최적해를 만들 수 없다. 이런 구조가 있어야 DP가 성립한다.

이 두 조건을 동시에 만족하는 대표적인 예가 피보나치 수열이다. 피보나치 수는 F(n) = F(n-1) + F(n-2) 형태로 정의된다. 여기서 F(n-1)과 F(n-2)는 여러 곳에서 반복해서 사용된다. 또한 F(n)의 값은 바로 이전 두 값의 합으로 결정되므로, 작은 문제의 결과가 큰 문제의 결과를 직접 구성한다. 그래서 DP가 잘 맞는다.

DP를 구현하는 방식은 크게 두 가지가 있다. 탑다운 방식과 바텀업 방식이다. 탑다운은 재귀를 사용해 큰 문제부터 풀어 내려가면서, 이미 계산한 값은 메모해두고 다시 계산하지 않는 방식이다. 흔히 메모이제이션이라고 부른다. 반면 바텀업은 가장 작은 문제부터 차례대로 값을 채워 나가면서, 최종적으로 원하는 답을 구하는 방식이다. 반복문을 사용하는 경우가 많다.

중요한 점은, DP를 쓴다는 것은 단순히 “배열 하나 더 쓰는 것”이 아니라는 것이다. 문제를 어떻게 쪼갤지, 어떤 값을 저장할지, 그 값이 다음 계산에 어떻게 사용되는지를 먼저 명확히 정의해야 한다. 이 설계가 제대로 되지 않으면 DP는 오히려 코드를 복잡하게 만들 뿐이다.

DP는 문제를 작은 문제로 나눌 수 있고, 그 작은 문제들이 반복해서 등장하며, 작은 문제의 정답이 모여 큰 문제의 정답을 만드는 구조일 때 DP를 사용하면 된다.

BFS(Breadth First Search)는 그래프를 탐색하는 방법 중 하나로, 가까운 노드부터 차례대로 넓게 탐색해 나가는 방식이다. DFS가 한 방향으로 깊게 파고드는 탐색이었다면, BFS는 현재 위치에서 같은 거리(같은 단계)에 있는 노드들을 먼저 모두 방문한 뒤 다음 단계로 넘어간다. 그래서 BFS는 “깊이”보다는 “거리”에 더 초점이 맞춰진 탐색 방법이라고 볼 수 있다.

BFS의 탐색 흐름은 비교적 직관적이다. 시작 노드에서 출발해, 그 노드와 직접 연결된 모든 노드를 먼저 방문한다. 그 다음에는 방금 방문한 노드들과 연결된 노드들을 다시 한 번 전부 확인한다. 이런 식으로 한 단계씩 범위를 넓혀가며 탐색이 진행된다. 마치 물에 돌을 던졌을 때 파동이 동심원 형태로 퍼져 나가는 모습과 비슷하다.

이러한 탐색 순서를 유지하기 위해 BFS는 큐(Queue) 자료구조를 사용한다. 먼저 발견한 노드를 먼저 처리해야 하기 때문이다. 시작 노드를 큐에 넣고, 하나를 꺼내서 그와 인접한 노드들을 다시 큐에 넣는 과정을 반복하면, 자연스럽게 “가까운 노드부터” 탐색하는 구조가 만들어진다. 이 과정에서도 DFS와 마찬가지로, 이미 방문한 노드를 다시 방문하지 않도록 방문 여부를 반드시 관리해야 한다.

BFS의 시간 복잡도는 DFS와 동일하다. 인접 리스트로 그래프를 표현했을 때, 모든 노드를 한 번씩 방문하고 모든 간선을 한 번씩 확인하므로 O(N + M)의 시간 복잡도를 가진다. 여기서 N은 노드의 개수, M은 간선의 개수다. 탐색 순서만 다를 뿐, 그래프 전체를 훑는다는 점에서는 DFS와 동일한 비용이 든다.

BFS가 특히 강점을 가지는 상황은 최단 거리와 관련된 문제다. 예를 들어 “A에서 B까지 가장 적은 단계로 도달할 수 있는가?”, “최소 몇 번의 이동으로 목적지에 도착할 수 있는가?” 같은 질문에는 BFS가 매우 적합하다. BFS는 가까운 노드부터 탐색하기 때문에, 어떤 노드를 처음 방문했을 때 그 경로가 곧 최단 경로가 된다. 이 때문에 미로 탐색, 최단 경로 문제, 레벨 단위 탐색이 필요한 문제에서 BFS가 자주 사용된다.

정리하자면, BFS는 그래프를 넓게 퍼지듯 탐색하는 알고리즘이다. 큐를 기반으로 동작하며, 시작점으로부터의 거리를 기준으로 노드를 방문한다는 점이 핵심이다. DFS가 “끝까지 파고들어 본다”는 탐색이라면, BFS는 “가까운 것부터 하나씩 확인한다”는 탐색이다. 이 차이만 명확히 이해해두면, 두 알고리즘을 언제 어떤 문제에 사용해야 할지도 자연스럽게 구분할 수 있다.

DFS(Depth First Search)는 그래프를 탐색하는 대표적인 방법 중 하나로, 이름 그대로 한 방향으로 가능한 한 깊이까지 들어가며 탐색하는 방식이다. 그래프에서 노드들이 어떻게 연결되어 있는지를 따라가며 구조를 파악해야 할 때 자주 사용된다. 이전에 다뤘던 그래프가 “연결 관계를 표현하는 자료구조”였다면, DFS는 그 연결 관계를 어떤 순서로 방문할 것인가에 대한 방법이라고 볼 수 있다.

DFS의 가장 큰 특징은 탐색 순서에 있다. 현재 위치에서 갈 수 있는 노드가 있다면, 다른 선택지를 남겨두더라도 일단 그 방향으로 계속 이동한다. 그러다 더 이상 갈 수 없는 지점에 도달하면, 그제서야 이전 노드로 되돌아와 다른 경로를 탐색한다. 이 흐름은 마치 미로에서 한 갈래 길을 끝까지 따라갔다가 막히면 되돌아오는 방식과 매우 유사하다. 그래서 DFS는 “깊게 들어갔다가 돌아온다”는 이미지로 이해하면 가장 직관적이다.

이러한 탐색 방식 때문에 DFS는 구조적으로 되돌아오는 과정이 필수적이다. 이 되돌아오는 흐름은 보통 스택 구조로 표현되며, 실제 구현에서도 스택이나 재귀 호출을 통해 자연스럽게 구현된다. 중요한 점은 이미 방문한 노드를 다시 방문하지 않도록 관리해야 한다는 것이다. 그래프는 트리와 달리 사이클이 존재할 수 있기 때문에, 방문 여부를 체크하지 않으면 같은 노드를 무한히 반복해서 탐색하는 문제가 발생할 수 있다. 따라서 DFS에서는 “방문 처리”가 알고리즘의 핵심 요소 중 하나다.

DFS의 시간 복잡도는 그래프의 표현 방식과 밀접한 관련이 있다. 인접 리스트로 그래프를 표현한 경우, DFS는 각 노드를 한 번씩 방문하고, 각 간선을 한 번씩 확인한다. 이 때문에 시간 복잡도는 O(N + M)으로 정리된다. 여기서 N은 노드의 개수, M은 간선의 개수다. 즉, 그래프의 크기가 커질수록 탐색 시간도 그에 비례해 증가하지만, 불필요한 중복 탐색 없이 전체 구조를 한 번 훑는 수준이라고 볼 수 있다. 이 점에서 DFS는 효율적인 그래프 탐색 방법 중 하나다.

DFS는 특히 “모든 경우를 끝까지 확인해야 하는 문제”에 강점을 가진다. 예를 들어 경로가 존재하는지 확인하는 문제, 특정 조건을 만족하는 경로를 찾는 문제, 사이클이 존재하는지 판별하는 문제, 혹은 선택지를 하나씩 깊게 파고들며 답을 찾는 백트래킹 문제에서 DFS는 거의 기본 도구처럼 사용된다. 한 번 선택한 경로를 끝까지 탐색한 뒤에 다음 선택지로 넘어간다는 특성이 이러한 문제들과 잘 맞아떨어지기 때문이다.

정리해보면, DFS는 그래프 탐색의 기본이 되는 알고리즘으로, “깊이 우선”이라는 명확한 탐색 철학을 가지고 있다. 한 방향으로 최대한 깊이 들어갔다가 되돌아오는 흐름, 방문 여부를 통한 중복 방지, 그리고 O(N + M)이라는 직관적인 시간 복잡도만 이해하고 있어도 DFS의 전체 구조는 충분히 이해할 수 있다. 이 개념을 확실히 잡아두면 이후에 배우게 될 BFS나 다양한 그래프 응용 문제들도 훨씬 수월하게 받아들일 수 있다.

그래프(Graph)란 무엇인가

그래프는 정점과 정점 사이의 연결 관계를 표현하는 자료구조다. 데이터 하나하나를 순서대로 나열하는 것이 아니라, 서로 어떻게 연결되어 있는지를 표현하는 데 초점이 맞춰져 있다. 그래서 그래프는 트리와 마찬가지로 비선형 자료구조에 속한다.

앞서 배운 스택이나 큐 같은 선형 자료구조는 “어떤 순서로 데이터를 넣고, 어떤 순서로 꺼낼 것인가”가 핵심이었다. 반면 그래프는 저장 순서보다는 관계와 구조 자체를 표현하는 것이 목적이다. 이 때문에 사람 관계, 지도, 네트워크, 추천 시스템처럼 “연결”이 중요한 문제에서 그래프가 자주 사용된다.

그래프를 예시로 이해해보기

사람 관계를 예로 들어보자.

• 민수와 영희는 친구다.
• 영희와 철수는 친구다.
• 철수와 지연은 친구다.

이를 그래프로 표현하면 다음과 같다.

민수 - 영희 - 철수 - 지연

여기서 사람 한 명 한 명이 노드(Node)이고, 친구 관계가 간선(Edge)이다. 영희와 민수처럼 간선으로 직접 연결된 관계를 인접 노드라고 부른다. 이처럼 그래프는 “누가 누구와 연결되어 있는가”를 직관적으로 표현할 수 있다.

그래프의 기본 용어

• 노드(Node) / 정점(Vertex): 그래프를 이루는 각각의 데이터
• 간선(Edge): 노드와 노드 사이의 연결 관계
• 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드

유방향 그래프와 무방향 그래프

그래프는 간선에 방향이 있는지에 따라 두 가지로 나뉜다.

• 유방향 그래프: 간선에 방향이 있어 한쪽 방향으로만 이동할 수 있다.
• 무방향 그래프: 간선에 방향이 없고, 양쪽으로 자유롭게 이동할 수 있다.

이번 글에서는 친구 관계처럼 상호 관계를 표현하기 쉬운 무방향 그래프만 다룬다.

그래프를 표현하는 두 가지 방법

그래프를 컴퓨터에서 표현하는 방법에는 대표적으로 인접 행렬과 인접 리스트가 있다.

인접 행렬 (Adjacency Matrix)

인접 행렬은 그래프의 연결 관계를 2차원 배열로 표현하는 방식이다.

graph = [
    [False, True,  False, False],
    [True,  False, True,  False],
    [False, True,  False, True ],
    [False, False, True,  False]
]

graph[i][j]가 True라면 i번 노드와 j번 노드가 연결되어 있다는 의미다. 이 방식의 가장 큰 장점은 두 노드가 연결되어 있는지 바로 확인할 수 있다는 점이다.

graph[1][2]  # O(1)

하지만 단점도 있다. 노드가 N개라면 모든 조합의 연결 여부를 저장해야 하므로 공간 복잡도는 O(N²)이 된다. 그래프가 커질수록 메모리 사용량이 급격히 늘어난다.

인접 리스트 (Adjacency List)

인접 리스트는 각 노드마다 연결된 노드만 따로 저장하는 방식이다.

graph = {
    0: [1],
    1: [0, 2],
    2: [1, 3],
    3: [2]
}

이 방식에서는 • 노드 N개 • 실제 연결된 간선 M개

이 방식은 실제로 존재하는 연결만 저장하기 때문에 공간 효율이 좋다. 공간 복잡도는 O(N + M) 수준이다.

다만 두 노드가 연결되어 있는지 확인하려면, 해당 노드의 리스트를 직접 확인해야 한다. 따라서 연결 여부 확인은 최악의 경우 O(M)가 걸릴 수 있다.

인접 행렬과 인접 리스트의 차이

두 표현 방식의 차이는 결국 시간과 공간의 선택 문제다.

• 인접 행렬
  • 연결 여부 확인: 빠름 (O(1))
  • 공간 사용량: 큼 (O(N²))
• 인접 리스트
  • 연결 여부 확인: 느릴 수 있음 (최악 O(M))
  • 공간 사용량: 효율적 (O(N + M))

그래프가 촘촘하게 연결된 경우에는 인접 행렬이, 그래프가 연결이 적은 경우에는 인접 리스트가 더 적합하다.

정리

1. 그래프는 연결 관계를 표현한다
2. 인접 행렬과 인접 리스트는 시간과 공간의 트레이드오프다
3. 인접 리스트의 공간 복잡도는 O(N + M)이다

그래프는 데이터를 나열하는 자료구조가 아니라, 데이터 간의 관계를 표현하는 자료구조다. 노드와 간선이라는 개념만 이해하면 구조 자체는 단순하지만, 활용 범위는 매우 넓다.

힙(Heap)이란 무엇인가

힙은 완전 이진 트리 기반의 자료구조로, 항상 특정 규칙을 만족하도록 값이 정렬되어 있다. 이 규칙 덕분에 힙은 최댓값이나 최솟값을 매우 빠르게 찾는 데 특화된 구조다. 힙은 정렬된 자료구조는 아니지만, “가장 크다” 혹은 “가장 작다”라는 기준 하나만큼은 항상 보장한다는 점이 핵심이다.

힙에는 크게 두 가지가 있다. 최대 힙(Max Heap)은 부모 노드가 항상 자식 노드보다 크거나 같고, 최소 힙(Min Heap)은 부모 노드가 항상 자식 노드보다 작거나 같다. 어떤 힙을 쓰느냐에 따라 루트 노드에는 항상 최댓값 또는 최솟값이 위치한다.

힙과 트리의 관계

힙은 아무 이진 트리가 아니라 완전 이진 트리 형태를 유지해야 한다. 즉, 노드는 항상 아래 레벨의 왼쪽부터 차례대로 채워진다. 이 조건 덕분에 힙은 트리 구조이면서도 배열로 효율적으로 표현할 수 있다.

완전 이진 트리의 성질을 그대로 사용하기 때문에, 배열에서 다음 규칙이 성립한다.

• 인덱스 i의 왼쪽 자식 → i * 2

• 인덱스 i의 오른쪽 자식 → i * 2 + 1

• 인덱스 i의 부모 → i // 2

이 구조 덕분에 힙은 포인터 없이도 트리를 다룰 수 있다.

# 최대 힙을 배열로 표현한 예시 (0번 인덱스는 사용하지 않음)
heap = [None, 10, 7, 8, 3, 5]

위 배열에서 10은 항상 최댓값이며, 배열의 맨 앞(루트)에 위치한다.

힙에서의 삽입과 삭제

힙의 가장 중요한 연산은 삽입과 삭제(보통 루트 삭제)다.

새로운 값을 힙에 삽입할 때는, 우선 트리의 가장 마지막 위치(배열의 끝)에 값을 넣는다. 이후 힙의 규칙을 깨지 않도록 부모 노드와 비교하면서 위로 올라간다. 이 과정을 heapify up이라고 한다.

반대로 값을 삭제할 때는, 보통 루트 노드를 제거한다. 루트 자리에 마지막 노드를 올린 뒤, 자식 노드들과 비교하며 아래로 내려보낸다. 이 과정을 heapify down이라고 한다.

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)

print(heapq.heappop(heap))  # 2 (최솟값)

파이썬의 heapq는 최소 힙을 기본으로 제공하며, 최댓값 힙은 값에 -를 붙이는 방식으로 구현한다.

힙의 시간 복잡도

힙의 높이는 완전 이진 트리이기 때문에 O(log N) 수준이다. 따라서 삽입과 삭제 모두 최악의 경우에도 트리의 높이만큼만 이동하면 되며, 시간 복잡도는 다음과 같다.

• 삽입: O(log N)

• 삭제(최댓값/최솟값 제거): O(log N)

• 최댓값/최솟값 조회: O(1)

특히 루트에 항상 최댓값이나 최솟값이 있기 때문에, 값을 “찾는” 비용은 거의 들지 않는다는 점이 힙의 가장 큰 장점이다.

힙은 언제 사용할까

힙은 전체를 정렬할 필요는 없지만, 항상 가장 중요한 값 하나를 빠르게 꺼내야 하는 상황에서 사용된다. 예를 들어 우선순위 큐, 작업 스케줄링, 다익스트라 알고리즘, 힙 정렬 등이 대표적인 활용 사례다.

정리하면 힙은 완전 이진 트리 기반의 자료구조이고 최댓값 또는 최솟값을 빠르게 다루기 위해 설계되었으며 삽입과 삭제는 O(log N), 조회는 O(1)로 동작한다.

트리(Tree)란 무엇인가

트리는 데이터를 계층 구조로 표현하기 위한 자료구조다. 앞에서 다룬 배열, 스택, 큐는 모두 한 줄로 이어진 선형 구조였지만, 트리는 위아래 관계가 존재하는 비선형 구조다. 현실 세계에서 가장 쉽게 떠올릴 수 있는 예시는 컴퓨터의 폴더 구조다. 하나의 최상위 폴더 아래에 여러 폴더가 있고, 그 아래로 또 다른 폴더들이 이어진다. 이런 구조를 표현하기에 트리는 매우 적합하다.

선형 구조가 “순서대로 저장하고 꺼내는 것”에 초점이 맞춰져 있다면, 트리는 “관계와 구조를 표현하는 것”에 초점이 맞춰진 자료구조라고 이해하면 된다.

트리의 기본 용어

트리는 몇 가지 기본 용어를 함께 이해해야 구조가 보인다. 트리를 구성하는 각각의 데이터 하나를 노드(Node) 라고 부른다. 트리의 가장 위에 있는 노드는 루트 노드(Root Node) 다. 루트 노드를 기준으로 아래로 내려갈수록 단계가 깊어지는데, 이 단계를 레벨(Level) 이라고 한다.

어떤 노드의 바로 위에 연결된 노드는 부모 노드, 아래에 연결된 노드는 자식 노드다. 자식 노드가 하나도 없는 노드는 리프 노드(Leaf Node) 라고 부른다. 같은 부모를 가진 노드들은 형제 노드(Sibling) 관계다. 이런 용어들은 트리를 설명할 때 거의 항상 등장한다.

이진 트리(Binary Tree)

이진 트리는 트리 중에서도 가장 기본적인 형태다. 이진 트리의 핵심 규칙은 단 하나다. 각 노드는 최대 두 개의 자식만 가질 수 있다.

자식이 0개일 수도 있고, 1개 또는 2개일 수도 있지만, 3개 이상은 허용되지 않는다. 구조가 어떻게 생겼든 이 규칙만 지키면 이진 트리다.

    o
   / \
  o   o   ← 이진 트리 (O)

    o
  / | \
 o  o  o ← 이진 트리 (X)

완전 이진 트리(Complete Binary Tree)

완전 이진 트리는 이진 트리 중에서도 노드가 채워지는 방식에 규칙이 있는 트리다. 모든 레벨은 왼쪽부터 차례대로 채워져야 하며, 마지막 레벨을 제외한 모든 레벨은 노드가 가득 차 있어야 한다.

      o
    o   o
   o o o   ← 완전 이진 트리 (O)

      o
    o   o
      o o ← 완전 이진 트리 (X)

이 규칙 덕분에 완전 이진 트리는 배열로 표현할 수 있다는 큰 장점이 있다.

완전 이진 트리를 배열로 표현하기

완전 이진 트리는 레벨 순서대로 노드를 배열에 저장하면 된다. 구현할 때는 계산을 쉽게 하기 위해 보통 0번 인덱스를 비워두고 1번부터 사용한다.

# 트리 구조
#       8
#     6   3
#   4  2  5

tree = [None, 8, 6, 3, 4, 2, 5]

이렇게 저장하면 인덱스 계산만으로 부모와 자식 관계를 바로 알 수 있다.

i = 1  # 값 8

left_child = i * 2      # 2 -> 6
right_child = i * 2 + 1 # 3 -> 3
parent = i // 2         # 0 (루트)

• 현재 인덱스 × 2 → 왼쪽 자식
• 현재 인덱스 × 2 + 1 → 오른쪽 자식
• 현재 인덱스 // 2 → 부모 노드

이 규칙 덕분에 포인터 없이도 트리 구조를 효율적으로 다룰 수 있다.

트리의 높이(Height)

트리의 높이는 루트 노드부터 가장 아래에 있는 리프 노드까지의 거리다. 루트를 레벨 0으로 두었을 때, 가장 깊은 레벨 번호가 트리의 높이가 된다.

      o   ← Level 0
    o   o ← Level 1
   o o o  ← Level 2

트리의 높이 = 2

완전 이진 트리에서 각 레벨에 들어갈 수 있는 노드 수는 규칙적이다.

• Level 0 → 1개
• Level 1 → 2개
• Level 2 → 4개
• Level k → 2^k개

따라서 높이가 h인 완전 이진 트리에서 모든 노드가 꽉 차 있다면, 전체 노드 수는 다음과 같다.

1 + 2 + 4 + ... + 2^h = 2^(h+1) - 1

반대로 노드의 개수가 N개라면, 트리의 높이는 대략 log₂N 수준이 된다. 즉, 노드 수가 크게 늘어나도 트리의 높이는 빠르게 커지지 않는다.

정리

트리는 데이터를 계층 구조로 표현하기 위한 비선형 자료구조다. 이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리이고, 완전 이진 트리는 노드가 왼쪽부터 차례대로 채워지는 규칙적인 이진 트리다. 완전 이진 트리는 배열로 표현할 수 있으며, 이 특성 덕분에 이후에 배울 다양한 자료구조의 기반이 된다.

해시는 데이터를 빠르게 찾기 위해 만들어진 자료구조이자 개념이다. 핵심 아이디어는 간단하다. 값을 그대로 저장하거나 그대로 비교하는 대신, 특정 규칙을 이용해 ‘숫자 형태의 고유한 값(해시 값)’으로 바꿔 저장하고, 그 숫자를 기반으로 데이터를 바로 찾아가는 방식이다. 이렇게 변환하는 과정을 해싱(hashing)이라고 하고, 변환에 사용되는 함수를 해시 함수(hash function)라고 부른다.

해시의 강점은 속도다. 배열처럼 인덱스로 접근할 수 있는 구조는 빠르지만, 인덱스를 미리 알지 못하면 결국 찾기 위해 전체를 훑어야 한다. 반면 해시는 데이터를 넣을 때부터 “어디에 저장할지”를 해시 함수가 결정해주기 때문에, 나중에 같은 함수를 이용해 그 자리를 바로 찾아갈 수 있다. 이 때문에 해시는 평균적으로 탐색·삽입·삭제가 모두 O(1)이라는 매우 강력한 성능을 갖는다.

예를 들어 “apple”이라는 문자열을 저장한다고 해보자. 해시 함수는 이 문자열을 입력받아 특정 규칙을 적용해 하나의 숫자를 만든다. 예를 들면 각 문자의 코드 값을 더하거나, 특정 계산을 적용해 1074 같은 숫자로 바꾼다. 그러면 해시 테이블(hash table)은 1074라는 인덱스 위치에 “apple”을 저장한다. 나중에 문자열 “apple”을 찾고 싶다면, 전체 데이터를 뒤질 필요 없이 똑같은 규칙으로 해시 값을 계산하고, 계산된 인덱스로 바로 이동하면 된다. 이것이 해시가 빠른 이유다.

물론 현실에서는 문제가 하나 있다. 서로 다른 두 값이 같은 해시 값을 갖는 경우, 즉 충돌(collision)이 발생한다는 점이다. 해시 함수가 아무리 정교해도 해시 테이블의 크기보다 데이터가 많아지면 충돌은 피할 수 없다. 이를 해결하기 위한 전략이 체이닝(chaining) 또는 오픈 어드레싱(open addressing) 방식이다. 체이닝은 같은 인덱스에 여러 값을 연결 리스트로 이어붙여 저장하는 방식이고, 오픈 어드레싱은 충돌 발생 시 다른 빈 칸을 탐색해 저장하는 방식이다. 충돌이 있더라도 적절히 해결하면 해시는 여전히 평균적으로 매우 빠른 성능을 낸다.

해시는 실제 소프트웨어 개발에서 매우 자주 등장한다. 파이썬의 dict, 자바스크립트의 Object와 Map, 자바의 HashMap 등이 모두 해시를 기반으로 만들어졌다. 데이터베이스의 인덱싱, 캐싱 시스템, 중복 탐지, 암호화, 블록체인까지 다양한 분야에서도 해시 함수가 핵심 역할을 한다. 그만큼 실전에서 가장 널리 쓰이는 자료구조 중 하나다.

해시를 이해할 때 기억해야 할 가장 중요한 포인트는 첫째, 데이터를 “해시 값”이라는 규칙 기반 숫자로 바꿔 저장한다는 것, 둘째, 이 덕분에 평균적으로 O(1)에 가까운 속도로 탐색·삽입·삭제가 가능하다는 것이다. 충돌이라는 단점은 있지만, 이를 해결하는 방식이 잘 갖춰져 있어 해시는 실제 개발 현장에서 여전히 가장 사랑받는 자료구조다.

큐는 데이터를 처리할 때 들어온 순서 그대로 다뤄야 하는 상황에서 사용하는 자료구조다. 이 구조의 가장 큰 특징은 먼저 들어온 값이 먼저 나가는 FIFO(First In, First Out) 방식이라는 점이다. 우리가 은행이나 카페에서 줄을 서는 모습과 같다. 먼저 줄을 선 사람이 먼저 서비스를 받고, 나중에 온 사람은 뒤에서 기다린다. 큐에서는 이러한 흐름을 그대로 코드로 표현한다.

큐의 기본 동작은 두 가지다. 데이터를 뒤에 추가하는 enqueue, 앞에서 꺼내는 dequeue. enqueue는 “줄 맨 뒤에 서기”에 해당하고, dequeue는 “줄 맨 앞 사람이 빠져나가는 것”이다. 이 두 연산은 큐의 양 끝에서만 이루어지기 때문에 구조가 단순하고, 삽입과 삭제가 모두 O(1)의 일정한 시간 안에 처리된다. 그래서 외부에서 데이터가 밀려오고, 내부에서는 들어온 순서대로 하나씩 처리해야 하는 환경에서 큐는 아주 유용하다.

실제로 큐는 컴퓨터 곳곳에서 쓰인다. 프린터가 출력할 문서를 하나씩 처리할 때, 먼저 들어온 문서부터 순서대로 뽑힌다. 운영체제(OS)에서는 프로세스를 공평하게 다루기 위해 큐를 사용해 작업을 대기시키고 실행 순서를 조절한다. 네트워크에서도 패킷이 도착하는 순서를 보존하기 위해 큐 구조를 사용한다. 알고리즘에서는 BFS(너비 우선 탐색)의 핵심이 바로 큐인데, 노드를 하나씩 탐색할 때 들어온 순서대로 처리해야 하므로 큐가 자연스럽게 선택된다.

물론 큐에도 한계는 있다. 스택처럼 중간값을 바로 꺼낼 수는 없다. 왜냐하면 큐는 언제나 가장 앞에 있는 값부터 꺼내도록 설계되어 있기 때문이다. 따라서 “특정 위치의 값을 빠르게 찾아야 하는 문제”에는 적합하지 않다. 그 대신, 순서를 보장하고 공정하게 처리해야 하는 상황이라면 큐만 한 구조가 없다.

정리하자면 큐는 단순하지만 여러 시스템에서 핵심적으로 사용되는 자료구조다. 들어온 순서대로 처리해야 하는 상황이 생긴다면, 큐는 가장 자연스럽고 가장 안정적으로 문제를 해결한다. 그리고 enqueue와 dequeue라는 두 동작만으로도 충분히 다양한 흐름을 다룰 수 있기 때문에, 자료구조를 배울 때 꼭 이해하고 넘어가야 하는 개념이기도 하다.

스택은 데이터를 저장하는 방식 중 하나로, 가장 마지막에 넣은 데이터를 가장 먼저 꺼내는 구조(LIFO: Last In, First Out)를 갖는다. 일상에서 가장 비슷한 예를 들자면, 책을 한 권씩 쌓아 올린 모습과 같다. 위에 올린 책이 가장 먼저 손에 잡히듯, 스택에서는 마지막에 들어온 데이터가 가장 먼저 빠져나온다. 이 단순한 규칙 덕분에 스택은 다양한 알고리즘과 시스템 동작 속에서 중요한 역할을 한다.

스택은 크게 두 연산으로 구성된다. 데이터를 추가하는 push, 데이터를 꺼내는 pop. push는 스택의 가장 위에 데이터를 올려놓는 동작이며, pop은 그 위에서 데이터를 하나 꺼내는 동작이다. 이때 pop은 스택이 비어 있으면 수행할 수 없다. 스택은 오직 한쪽 끝(“top”)에서만 삽입과 삭제가 이루어지기 때문에 구조적으로 매우 단순하고 예측 가능하다.

스택이 많이 쓰이는 이유는 이 LIFO 구조가 특정 상황에서 매우 자연스럽게 맞아떨어지기 때문이다. 예를 들어 함수 호출이 중첩되는 상황을 생각해보면 이해가 쉽다. A 함수가 B 함수를 호출하고, B 함수가 C 함수를 호출하면, 프로그램은 C → B → A 순으로 복귀한다. 가장 마지막에 호출된 함수가 가장 먼저 종료되기 때문이다. 실제로 프로그래밍 언어의 함수 호출 기록을 저장하는 공간도 ‘스택 프레임(stack frame)’이라고 부르며, 내부적으로 스택 구조로 관리된다.

또한 스택은 괄호 검증 같은 알고리즘 문제에서도 핵심적으로 등장한다. 여는 괄호 ‘(’를 만나면 push, 닫는 괄호 ‘)’를 만나면 pop을 수행하며, 스택이 정확히 비어 있는지를 확인하는 방식으로 괄호 구조의 올바름을 판단한다. 브라우저의 뒤로 가기 버튼 역시 스택 개념으로 동작한다. 사용자가 방문한 페이지를 차곡차곡 쌓아두고(pop), 뒤로 갈 때는 가장 마지막 페이지부터 되돌아가는 것이다.

스택의 시간 복잡도는 매우 효율적이다. push와 pop 모두 스택의 최상단에서만 이루어지기 때문에 O(1), 즉 상수 시간 안에 처리된다. 하지만 중간 요소를 직접 접근하지는 못한다. 무조건 top부터 꺼내야 하기 때문에 스택은 “순차적 접근만 가능한 구조”라는 한계가 있다. 이런 점 때문에 스택은 단독으로 대량의 데이터 탐색에 사용되기보다는, 흐름 제어, 중첩된 작업 처리, 임시 저장, 역순 처리(reverse) 등 특정 목적에 적합한 도구로 활용된다.

스택의 본질은 단순함이다. 구조는 매우 간단하지만, 프로그램의 흐름을 제어하거나 알고리즘의 과정을 관리하는 데 자주 등장하며, 실제 운영체제와 언어 내부에서도 필수적으로 사용된다. 스택을 확실하게 이해해두면 재귀 함수, DFS 탐색, 함수 호출, 계산기 알고리즘 같은 여러 개념을 자연스럽게 따라갈 수 있게 된다.

병합 정렬은 배열을 효율적으로 정렬하기 위해 사용되는 대표적인 분할 정복(divide and conquer) 알고리즘이다. 큰 문제를 한 번에 해결하려 하지 않고, 작은 문제로 계속 쪼갠 뒤 정렬하고 다시 합치는 방식으로 동작한다. 병합 정렬이 강력한 이유는 이 구조 덕분에 어떤 입력이 들어와도 시간 복잡도가 일정하게 유지된다는 점이다.

정렬 과정은 크게 두 단계로 나뉜다. 먼저 분할 단계에서는 배열을 길이가 1이 될 때까지 반으로 계속 쪼갠다. 예를 들어 [8, 3, 5, 1]이라는 배열이 있다면, 이를 [8, 3]과 [5, 1]로 나누고, 다시 [8]·[3], [5]·[1]처럼 계속 절반으로 나눈다. 길이가 1인 배열은 이미 정렬된 상태이므로 더 이상 쪼갤 필요가 없다.

그다음은 병합 단계다. 이 단계에서는 쪼개진 배열들을 두 개씩 비교하며 정렬된 형태로 합친다. 예를 들어 [8]과 [3]을 합칠 때는 두 값을 비교해 [3, 8]이 되고, [5]와 [1]은 [1, 5]가 된다. 이렇게 정렬된 두 배열을 다시 병합하면 최종적으로 [1, 3, 5, 8]이라는 정렬된 결과가 완성된다. 핵심은 “각 부분 배열이 이미 정렬되어 있으므로 병합 과정에서 앞 요소끼리만 비교하면 된다”는 점이다. 이 때문에 병합 정렬의 병합 단계는 매우 효율적으로 동작한다.

병합 정렬을 이해할 때 가장 중요한 포인트는 항상 배열을 반으로 나눈 뒤 합치는 과정이 같은 패턴으로 반복된다는 것이다. 이 구조는 배열이 어떤 상태로 들어오든 변하지 않는다. 완전히 정렬된 배열이든, 완전히 뒤죽박죽된 배열이든, 절반으로 나누는 횟수는 똑같고 병합하는 과정도 동일하게 반복된다. 이러한 특징 때문에 병합 정렬의 시간 복잡도는 입력 상황에 관계없이 항상 O(n log n)이다.

여기서 log n이 등장하는 이유는 분할 단계 때문이다. 배열을 반씩 나누다 보면, 길이가 n이면 log₂n 번 나누면 길이 1이 된다. 분할 단계는 log n 만큼 발생한다. 그리고 병합할 때는 매 단계에서 전체 요소 n개를 모두 한 번씩 비교하거나 복사하게 된다. 따라서 전체 시간 복잡도는 n(log n)이 된다. 정렬 알고리즘에서 n log n은 매우 빠른 축에 속하며, 버블 정렬이나 삽입 정렬처럼 n²이 필요한 알고리즘보다 훨씬 효율적이다.

병합 정렬은 공간을 더 사용하는 편이라는 단점도 있다. 병합 과정에서 두 배열을 새로운 배열에 담아 합치는 과정이 필요하기 때문에, 추가적인 메모리 공간이 필요하고 공간 복잡도는 O(n)이 된다. 하지만 이 비용을 감수하더라도, 안정적이고 일정한 속도로 빠른 정렬이 필요할 때 병합 정렬은 매우 강력한 선택이다.

병합 정렬은 구조가 명확하고 시간 복잡도가 일정하다는 장점 덕분에, 실제 많은 프로그래밍 언어의 기본 정렬 알고리즘 내부에서도 사용된다(예: Python의 Timsort는 병합 정렬과 삽입 정렬을 조합한 방식이다). 즉, 단순히 알고리즘을 배우기 위한 개념을 넘어, 실전에서도 널리 활용되는 정렬 방식이다.

정렬 알고리즘을 처음 공부할 때 가장 자주 등장하는 두 가지 방식이 있다. 바로 선택 정렬과 삽입 정렬이다. 둘 다 구조가 단순하고 구현이 쉬워서 입문 단계에서 자주 사용되지만, 내부에서 어떻게 동작하는지 조금만 이해해두면 정렬 알고리즘의 기본적인 사고방식이 자연스럽게 잡힌다.

선택 정렬은 이름 그대로 “선택하는 정렬”이다. 매 단계마다 남아 있는 값 중 가장 작은 값을 선택해서 앞으로 가져오는 방식으로 작동한다. 예를 들어, 배열이 [7, 5, 3, 1]이라고 하면, 먼저 전체에서 가장 작은 값 1을 찾고, 이를 맨 앞과 교환한다. 그다음엔 두 번째 위치부터 끝까지 중에서 가장 작은 값을 선택해 자리를 바꾼다. 이런 식으로 각 위치마다 ‘제 자리에 올 값 하나’를 선택해 나가는 구조이기 때문에, 전체 비교 횟수는 항상 일정하게 많다. 첫 번째 위치를 채우기 위해 n개를 비교하고, 두 번째 위치를 채우기 위해 n-1개를 비교하며, 이런 과정이 끝까지 반복된다. 총 비교 횟수는 n(n-1)/2가 되고, 시간 복잡도는 O(n²)으로 표현한다. 배열의 상태와 상관없이 항상 전체를 훑어 최소값을 찾아야 하기 때문에, 최선·최악·평균 모두 O(n²)이다. 구조는 단순하지만 효율성은 떨어지는 정렬 방식이다.

삽입 정렬은 선택 정렬과는 사고방식이 다르다. 새로운 데이터를 받아들일 때 우리가 자연스럽게 정렬하는 방식과 매우 닮아 있다. 예를 들어 손에 든 카드를 정렬한다고 생각해보자. 새로운 카드를 뽑으면 기존에 들고 있는 카드들을 왼쪽부터 훑어가며 알맞은 위치에 끼워 넣는다. 삽입 정렬도 똑같다. 배열에서 두 번째 요소부터 시작해, 앞쪽 부분이 이미 정렬되어 있다고 가정한 상태에서 현재 요소를 알맞은 위치에 끼워 넣는 방식으로 진행된다. 값이 제자리를 찾을 때까지 앞 요소들과 비교하며 왼쪽으로 이동하고, 위치를 찾으면 삽입하고 다음 요소로 넘어간다. 배열이 이미 어느 정도 정렬되어 있다면 이동할 횟수가 적어 매우 빠르게 끝난다.

이 특성 때문에 삽입 정렬의 시간 복잡도는 상황에 따라 달라진다. 최악의 경우(배열이 완전히 역순일 때)는 매 번 왼쪽 끝까지 이동해야 하므로 O(n²)의 시간 복잡도를 가진다. 하지만 최선의 경우(이미 정렬된 배열)는 비교만 한 번 하고 바로 넘어가므로 O(n)에 가까운 성능이 나온다. 즉, 선택 정렬은 모든 경우가 O(n²)이지만, 삽입 정렬은 데이터 상태에 따라 성능이 크게 달라진다는 차이가 있다.

두 알고리즘 모두 안정 정렬 여부를 따져보는 것도 중요하다. 선택 정렬은 최소값을 선택해 뒤와 교환하는 구조라 같은 값을 가진 요소들의 상대적 순서가 깨질 수 있어 불안정 정렬이다. 반면 삽입 정렬은 왼쪽으로 이동하며 자신보다 큰 값만 밀어내는 방식이라 동일한 값을 유지한 채 위치를 찾기 때문에 안정 정렬이다.

정리하자면, 선택 정렬은 “남은 값 중 최소값을 찾아 앞으로 보내는 방식”이고, 삽입 정렬은 “앞부분을 정렬된 상태로 유지하며 새로운 값을 적절한 위치에 끼워 넣는 방식”이다. 선택 정렬은 정렬 상태와 상관없이 항상 O(n²)이라는 단순한 구조를 가지고 있고, 삽입 정렬은 데이터가 정렬되어 있을수록 빠르게 끝난다는 장점을 가진다. 두 알고리즘 모두 실무에서 직접 활용되는 경우는 거의 없지만, 정렬의 기본 사고를 배우고 알고리즘의 시간 복잡도를 이해하는 데 매우 중요한 기반이 된다.

버블 정렬은 알고리즘을 처음 공부할 때 가장 먼저 접하는 정렬 방식이다. 두 인접한 요소를 비교하고, 순서가 잘못되어 있으면 서로 교환하는 방식으로 작동한다. 이 과정을 반복하면 가장 큰 값이 배열의 오른쪽 끝으로 이동하게 되는데, 거품이 수면 위로 떠오르는 모습과 닮았다고 해서 ‘버블 정렬’이라는 이름이 붙었다. 버블 정렬의 핵심은 배열을 한 번 끝까지 훑을 때마다 오른쪽 끝에 ‘정렬된 값 하나’가 확정된다는 점이다. 요소가 n개라면 전체를 정렬하기 위해 필요한 반복 횟수는 n-1번이다. 마지막 하나는 자동으로 제자리를 찾기 때문이다.

작동 방식은 단순하다. 처음 훑을 때는 전체 요소를 앞에서부터 비교하여 가장 큰 값을 오른쪽 끝으로 보낸다. 다음 반복에서는 이미 오른쪽 끝이 정렬되어 있으니 그 전까지만 비교하면 된다. 이런 식으로 비교해야 하는 구간이 점점 줄어들며 정렬이 진행된다. 버블 정렬이 기본적이지만 비효율적이라고 평가되는 이유가 바로 여기에 있다. 비교와 교환을 계속 반복하기 때문에 배열이 길어질수록 작업량이 빠르게 증가한다.

시간 복잡도를 보면 더 명확하다. 전체를 훑는 과정이 최대 n-1번 반복되고, 각 반복 안에서는 남은 요소들끼리 다시 비교한다. 첫 번째에서는 n-1번, 두 번째에서는 n-2번… 이런 식으로 줄어들기 때문에 전체 비교 횟수는 (n-1) + (n-2) + … + 1이 된다. 등차수열의 합을 적용하면 총 비교 횟수는 n(n-1)/2가 되고, 이는 결국 O(n²)의 시간 복잡도를 의미한다. 입력값이 두 배로 늘어나면 비교 횟수는 네 배로 뛰는 셈이다. 이런 이유로 버블 정렬은 실제 서비스나 대규모 데이터 처리 환경에서는 거의 사용되지 않는다.

그렇다고 해서 버블 정렬이 쓸모없는 알고리즘은 아니다. 알고리즘의 기본 원리를 이해하기에 좋은 구조를 갖고 있고, ‘두 값을 비교하고 교환한다’는 직관적인 작동 방식 덕분에 구현이 매우 쉽다. 또한 안정 정렬이기 때문에 동일한 값을 가진 요소들의 상대적 순서를 유지한다. 교육적 목적이나 작은 규모의 데이터에서는 여전히 충분히 활용 가치가 있다.

버블 정렬을 이해할 때 중요한 포인트는 두 가지다. 첫째, 한 번 쭉 훑을 때마다 가장 큰 값이 오른쪽으로 이동하며 정렬해야 하는 구간이 계속 줄어든다는 점. 둘째, 이러한 구조 때문에 시간 복잡도가 O(n²)로 입력값 증가에 매우 취약하다는 점이다. 이 흐름만 잡고 있으면 버블 정렬의 작동 원리와 한계가 자연스럽게 보인다.

재귀 함수(recursion)는 어떤 문제를 해결할 때 그 문제와 동일한 구조를 가진 더 작은 문제로 쪼갠 뒤, 그 작은 문제를 다시 자기 자신에게 맡기는 방식이다. 이 개념을 처음 들으면 어렵게 느껴지지만, 사실 상자 속에 상자가 계속 들어 있는 구조처럼, 큰 문제 안에 작은 문제가 반복적으로 등장하는 상황을 떠올리면 금방 이해된다. 예를 들어 팩토리얼 n!을 계산할 때 n! = n × (n-1)! 이라는 규칙을 이용하면, 더 이상 쪼갤 수 없는 순간인 1!에 도달할 때까지 같은 형태의 문제를 반복하게 되는데 이것이 재귀의 가장 대표적인 형태다. 실제 코드로 표현하면 다음과 같이 매우 간단하다.

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

이처럼 재귀는 트리 탐색, 그래프 탐색, 하노이 탑, 분할정복 알고리즘, 조합·순열 생성처럼 문제를 작은 조각으로 나누는 과정이 명확할 때 효과적이다. 하지만 장점만 있는 것은 아니다. 재귀는 호출될 때마다 스택 프레임을 새로 쌓기 때문에 메모리 사용량이 증가하고, 재귀 호출 깊이가 커지면 파이썬의 경우 기본 제한을 넘어서 RecursionError가 발생할 수도 있다. 또한 종료 조건을 잘못 설정하면 함수가 끝없이 호출되므로 항상 base case를 가장 먼저 점검해야 한다.

시간 복잡도 측면에서 보면, 재귀 함수의 비용은 “얼마나 많은 재귀가 호출되는지”와 “각 호출에서 어떤 작업을 수행하는지”에 의해 결정된다. 예를 들어 factorial처럼 한 번 호출할 때마다 딱 한 번만 자기 자신을 다시 호출하는 구조는 깊이가 n이므로 O(N) 시간이 든다. 하지만 하노이 탑처럼 매 번 재귀 호출이 두 번씩 발생하는 구조는 T(n) = 2T(n-1) + 1 형태가 되고, 이는 결국 O(2^N)까지 치솟는다. 반대로 이진 탐색을 재귀로 구현하면 매 호출마다 탐색 범위가 절반씩 줄어들어 O(logN) 시간이 걸리는 방식이 된다. 즉, 재귀는 겉보기에는 단순해 보이지만, 문제가 분기되는 구조인지, 단일 경로인지, 분할정복인지에 따라 성능이 크게 달라지기 때문에 재귀 호출 패턴을 항상 주의 깊게 살펴야 한다.

정리하면 재귀 함수는 “큰 문제를 더 작은 문제로 쪼개고, 그 작은 문제를 자기 자신이 다시 해결한다”는 구조를 가진 도구이며, 트리나 분할정복처럼 구조적으로 반복되는 문제를 해결할 때 코드가 매우 자연스럽고 간결해진다. 하지만 스택 사용량 증가, 깊이 제한, 종료 조건 실수 등 주의해야 할 점도 있으므로 장단점을 모두 이해한 상태에서 사용하는 것이 좋다.

이진 탐색은 정렬된 데이터에서 원하는 값을 빠르게 찾기 위해 사용되는 대표적인 탐색 알고리즘이다. 업다운 게임을 떠올리면 동작 원리를 쉽게 이해할 수 있다. 숫자가 1부터 100까지 있다고 가정하고, 제한된 횟수 안에 정답을 맞혀야 한다면 가장 먼저 시도해야 할 숫자는 가운데 값인 50이다. 정답이 50보다 크면 51100 구간만 남고, 반대로 작으면 149 구간만 남는다. 이렇게 한 번 시도할 때마다 탐색해야 할 범위가 절반으로 줄어드는 방식이 바로 이진 탐색의 핵심이다.

이 방식이 얼마나 효율적인지는 순차 탐색과 비교해 보면 분명해진다. 순차 탐색은 배열의 앞에서부터 하나씩 순서대로 확인하며 찾는 가장 단순한 방식이다. 예를 들어 1부터 16까지 정렬된 숫자 배열에서 14를 찾는다고 하면, 순차 탐색은 1부터 차례대로 비교해 14에 도달하는 순간에야 탐색이 끝난다. 실제로 이 경우 14번 비교해야 하고, 찾는 값이 마지막에 있다면 16번까지 비교해야 한다. 따라서 순차 탐색의 시간 복잡도는 최악의 경우 O(N)이다.

반면 이진 탐색을 같은 배열에 적용해 보면 탐색 과정이 완전히 다르다. 처음에는 배열의 중앙값인 8을 확인한다. 8은 찾으려는 14보다 작기 때문에 이후 탐색 범위는 916으로 좁아진다. 그 다음에는 다시 그 범위의 가운데 값인 12를 확인하고, 다시 탐색 범위를 1316으로 줄인다. 마지막으로 13번째 인덱스에서 값 14를 확인하면서 탐색이 종료된다. 이 과정에서 필요한 비교 횟수는 단 3번이다. 범위가 절반씩 줄어들기 때문에 배열의 길이가 커질수록 효율성 차이는 더욱 극적으로 벌어진다.

이진 탐색의 시간 복잡도가 O(logN)인 이유도 여기에 있다. 첫 번째 탐색 후 남는 요소는 N/2, 두 번째는 N/4, 세 번째는 N/8이 되고, k번째 탐색 후에는 N/2^k 개가 남는다. 이 값이 1이 되는 시점이 탐색 종료 시점인데, 이를 수식으로 표현하면 N/2^k = 1이 되고, 이를 정리하면 k = log₂N이 된다. 빅오 표기법에서는 밑의 상수는 중요하지 않기 때문에 O(logN)으로 표기한다. 복잡해 보이지만 “탐색 범위가 매번 절반으로 줄어든다”는 점이 중요하다.

이 방식의 장점은 데이터가 많을수록 더 강력하게 드러난다. 예를 들어 100만 개의 정렬된 데이터가 있다고 가정하면, 순차 탐색은 최악의 경우 100만 번 모두 확인해야 한다. 반면 이진 탐색은 log₂1,000,000 ≈ 20 정도의 연산만으로 원하는 값을 찾는다. 100만 vs 20, 이 차이가 얼마나 큰지 단번에 느껴질 것이다. 이런 이유로 정렬된 배열에서의 탐색 문제는 거의 항상 이진 탐색이 기본 전략이 된다.

프로그래밍에서는 데이터를 어떻게 저장하고 다루느냐에 따라 선택해야 할 자료구조가 달라진다. 특히 배열과 링크드 리스트는 기본 구조는 비슷해 보이지만 내부 동작 방식은 크게 다르다.

이 글에서는 어레이(Array)와 링크드 리스트(Linked List)의 차이를 직관적으로 이해할 수 있도록, 간단한 예시와 함께 핵심 개념을 정리해본다.

어레이: 연속된 공간에 데이터를 저장하는 구조

어레이는 정해진 크기의 연속된 메모리 공간에 데이터를 저장한다. 각 요소는 인덱스로 접근할 수 있고, 접근 속도는 항상 O(1)이다.

예를 들어, 길이가 5인 배열이 있다면 내부적으로는 이렇게 붙어 있는 상태다.

[0][1][2][3][4]

이 덕분에 인덱스로 접근하는 연산은 매우 빠르다. CPU가 연속된 메모리를 잘 캐싱하기 때문에 실제 성능도 좋다.

하지만 이런 ‘연속된 공간’ 덕분에 발생하는 단점도 있다.

❗ 중간에 삽입/삭제가 어렵다

배열 중간에 새로운 원소를 넣기 위해서는, 뒤에 있는 데이터를 모두 한 칸씩 이동시켜야 한다.

예를 들어 [A, B, C, D] 사이에 새로운 값 X를 넣는다면,

[A, B, C, D]
 → C, D를 뒤로 민다 → [A, B, X, C, D]

이 과정에서 최악의 경우 전체 배열을 이동해야 한다. → O(N)

❗ 공간이 가득 차면 새로운 배열을 통째로 만들어야 한다

배열은 크기가 고정되어 있기 때문에, 만약 더 많은 데이터를 넣어야 한다면 아예 더 큰 배열을 새로 만들고 기존 데이터를 복사해야 한다.

링크드 리스트: 포인터로 이어 붙인 유연한 구조

링크드 리스트는 데이터를 연속된 공간에 두지 않는다. 각 요소(Node)는 다음 노드를 가리키는 포인터(Link)를 가지고 있다.

[Node1] → [Node2] → [Node3] → [Node4]

❗ 삽입/삭제가 쉽다

중간에 새로운 노드를 넣고 싶다면 포인터만 바꿔주면 된다.

[Node1] → [Node2] 
               ↓
           [NewNode] 
               ↓
          [Node3]

이 작업은 포인터만 수정하면 되므로 O(1)에 처리할 수 있다. 삭제도 동일하게, 앞뒤 노드의 포인터를 바꿔주면 된다.

❗ 특정 원소 접근은 느리다

링크드 리스트는 인덱스가 없기 때문에, 특정 노드를 찾으려면 앞에서부터 하나씩 따라가야 한다.

Head → 1 → 2 → 3 → …  

따라서 접근은 O(N)이다. 또한 메모리가 연속적이지 않아 CPU 캐시 효율도 낮다.

어레이 vs 링크드 리스트 — 어떻게 선택하면 좋을까?

다음 표는 두 자료구조의 핵심 차이를 정리한 것이다.

🔎 어떤 상황에서 어떤 구조를 쓰면 좋을까?

• 조회가 많다 → Array

• 중간 삽입/삭제가 많다 → LinkedList

• 메모리 연속성 혹은 캐시 효율이 중요하다 → Array

• 데이터 크기가 유동적으로 늘어난다 → LinkedList

점근 표기법은 간단히 말해 “입력값이 커질 때 알고리즘의 실행 시간이 어떤 함수 형태로 증가하는가”를 나타내는 방법이다. 수학적으로는 함수의 증가 양상을 비교하는 개념에서 비롯되었지만, 프로그래밍에서는 알고리즘의 성장률을 표현하는 수단으로 쓰인다. 우리가 지금까지 “이 알고리즘은 N번 반복한다”, “이건 N²번 연산이 필요하다”라고 말했던 것이 바로 점근 표기법을 사용한 분석이다.

점근 표기법에는 대표적으로 빅오(Big-O) 표기법과 빅오메가(Big-Ω) 표기법이 있다. 빅오 표기법은 최악의 경우(worst case)를 기준으로, 알고리즘이 수행해야 하는 최대 연산량을 나타낸다. 반면 빅오메가 표기법은 최선의 경우(best case)를 기준으로, 가장 빠르게 실행될 때의 연산량을 표현한다. 예를 들어 “이 알고리즘은 O(N)의 시간 복잡도를 가진다”라고 하면, 입력 크기가 N일 때 최악의 경우에 N에 비례하는 시간이 걸린다는 뜻이다. 반대로 “Ω(1)”이라면, 최선의 경우에는 한 번의 연산만으로 답을 얻을 수 있다는 의미다.

예를 들어 배열 안에서 특정 숫자가 존재하는지 찾는 문제를 생각해보자.

def is_number_exist(number, array):
    for element in array:
        if number == element:
            return True
    return False

print(is_number_exist(3, [3, 5, 6, 1, 2, 4])) # True
print(is_number_exist(7, [3, 5, 6, 1, 2, 4])) # False

이 함수는 배열을 앞에서부터 하나씩 순회하며 찾고자 하는 숫자와 같은지 비교한다. 만약 찾는 숫자가 배열의 첫 번째 원소라면, 한 번의 비교만으로 True를 반환하고 함수가 종료된다. 이때는 최선의 경우에 해당하므로 Ω(1)의 시간 복잡도를 가진다.

하지만 찾는 숫자가 배열의 맨 끝에 있거나, 존재하지 않는 경우라면 어떨까? 이 경우에는 배열의 모든 원소를 확인해야 하므로, 배열의 길이가 N이라면 N번의 비교 연산이 필요하다. 즉, 최악의 경우에는 O(N)의 시간 복잡도를 가진다.

이처럼 알고리즘의 실행 시간은 입력값의 구성이나 순서에 따라 달라질 수 있다. 어떤 경우에는 빠르게 끝날 수도 있지만, 다른 경우에는 오래 걸릴 수도 있다. 따라서 알고리즘을 분석할 때는 보통 최악의 상황을 기준으로 성능을 평가한다.

그 이유는 명확하다. 대부분의 입력이 최선의 경우일 가능성은 매우 낮고, 실제 프로그램이 다양한 상황에서 안정적으로 동작하려면 최악의 상황에서도 감당 가능한 수준의 성능을 보장해야 하기 때문이다. 그래서 알고리즘 분석에서는 빅오 표기법(Big-O)이 가장 널리 사용된다.

다시 말해, 빅오 표기법은 “이 알고리즘이 얼마나 빠른가?”가 아니라, “입력이 커질수록 얼마나 느려질 수 있는가?”를 보여주는 지표다.

정리하자면, 점근 표기법은 알고리즘의 효율성을 수학적으로 표현하는 방법이며, 빅오(Big-O)는 최악의 경우, 빅오메가(Big-Ω)는 최선의 경우를 나타낸다. 그리고 실무나 코딩 테스트에서는 대부분의 상황을 대비하기 위해 빅오 표기법을 사용한다. 결국 우리가 고민해야 할 것은 “이 알고리즘은 입력이 커질 때 어디까지 버틸 수 있는가”이며, 점근 표기법은 그 답을 가장 명확하게 보여준다.

우리는 보통 공간을 적게 사용하는 알고리즘을 효율적이라고 생각하지만, 모든 경우에 그렇지는 않다. 실제로는 시간과 공간은 서로 트레이드오프 관계를 가진다. 속도를 높이기 위해 데이터를 더 많이 저장해야 하는 경우도 있고, 반대로 메모리를 절약하기 위해 계산을 여러 번 반복해야 하는 경우도 있다. 따라서 공간 복잡도는 독립적인 지표라기보다는, 시간 복잡도와 함께 고려해야 하는 균형의 문제라고 볼 수 있다.

예를 들어 문자열에서 가장 많이 등장한 알파벳(최빈값)을 찾는 문제를 생각해보자.

첫 번째 방법은 알파벳 배열을 미리 만들어두고, 각 알파벳마다 문자열 전체를 돌면서 몇 번 등장했는지를 세는 방식이다.

def find_max_occurred_alphabet(string):
    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", 
                      "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
    max_occurrence = 0
    max_alphabet = alphabet_array[0]

    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:
            if char == alphabet:
                occurrence += 1

        if occurrence > max_occurrence:
            max_alphabet = alphabet
            max_occurrence = occurrence

    return max_alphabet

이 함수는 alphabet_array라는 배열을 선언해 26개의 공간을 사용하고, max_occurrence, max_alphabet, occurrence 같은 변수를 추가로 사용한다. 총 29개의 공간이 필요하지만, 문자열의 길이가 아무리 커져도 이 크기는 변하지 않는다. 즉, 입력 크기 N과 관계없이 일정한 공간을 사용하는 상수 공간, 다시 말해 O(1)의 공간 복잡도를 가진다.

이제 두 번째 방법을 보자. 이번에는 알파벳 빈도수를 저장하는 배열을 활용한다.

def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')
        alphabet_occurrence_array[arr_index] += 1

    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

    return chr(max_alphabet_index + ord('a'))

이 함수는 [0] * 26으로 26개의 공간을 확보하고, arr_index, max_occurrence, max_alphabet_index 등의 변수를 사용한다. 전체적으로 약 30개의 공간이 필요하며, 역시 입력 길이 N과는 무관한 상수 크기이므로 O(1)의 공간 복잡도를 가진다.

이쯤 되면 “29개를 쓰는 첫 번째 방법이 더 효율적이지 않을까?”라는 생각이 들 수도 있다. 그러나 공간 복잡도에서 중요한 것은 절대적인 숫자가 아니라 입력 크기 증가에 따른 변화율이다. 29와 30은 모두 상수이기 때문에 의미 있는 차이가 없다.

따라서 이 두 알고리즘은 공간 복잡도 면에서는 사실상 동일하다고 볼 수 있다. 대신 효율성을 판단할 때는 시간 복잡도를 함께 고려해야 한다. 첫 번째 방법은 모든 알파벳에 대해 문자열 전체를 반복 탐색하므로 약 26×N번의 연산이 필요하고, 두 번째 방법은 문자열을 한 번만 순회하므로 N번의 연산으로 충분하다. 즉, 두 번째 방법이 훨씬 빠르다.

이 예시에서 알 수 있듯이, 대부분의 알고리즘은 공간보다 시간에 의해 효율성이 결정된다. 물론 예외도 있다. 만약 어떤 알고리즘이 입력 크기에 따라 N², N³ 수준의 공간을 사용한다면 메모리 사용량이 급격히 증가해 프로그램이 느려지거나 실행조차 불가능할 수 있다. 이런 경우에는 공간 복잡도가 중요한 판단 기준이 된다.

정리하자면, 공간 복잡도는 입력값의 크기와 메모리 사용량의 관계를 나타내며, 상수 크기의 차이는 중요하지 않다. 대신 입력이 커질 때 메모리 사용량이 얼마나 증가하는지를 보는 것이 핵심이다. 효율적인 알고리즘은 필요한 만큼만 공간을 사용하면서도 빠르게 동작하는 코드이다. 결국 공간 복잡도는 프로그램이 얼마나 가볍고 단순하게 작동하는지를 보여주는 또 하나의 지표라고 할 수 있다.

예를 들어 반 친구 중에서 가장 키가 큰 사람을 찾는다고 생각해보자. 한 명씩 살펴보며 현재까지의 최대값을 갱신하는 방식은 전체 학생 수(N)만큼의 비교가 필요하다. 즉, 입력값 N이 커질수록 실행 횟수도 비례해 늘어나므로 시간 복잡도는 O(N)이다. 반면 모든 학생을 서로 비교하는 방식이라면, 한 사람당 다른 모든 사람과 비교해야 하므로 N×N, 즉 O(N²)의 시간이 걸린다. 이 두 방식은 모두 같은 문제를 해결하지만, N이 커질수록 실행 시간의 차이는 급격히 벌어진다. 이것이 바로 시간 복잡도의 의미다.

시간 복잡도는 보통 Big-O 표기법(Big-O Notation) 으로 표현한다. Big-O는 알고리즘의 실행 시간이 입력 크기에 따라 얼마나 증가하는지를 보여주는 상한선이다. 입력 크기가 커져도 실행 시간이 거의 변하지 않으면 O(1), 입력 크기에 비례하면 O(N), 로그 형태로 느리게 증가하면 O(log N), 정렬 알고리즘처럼 N log N 형태로 증가하면 O(N log N), 중첩 반복문처럼 제곱으로 증가하면 O(N²)이라고 표현한다. 만약 모든 경우를 재귀적으로 탐색하는 알고리즘이라면 O(2ⁿ)이나 O(N!)처럼 훨씬 가파르게 증가한다.

코드로 간단히 살펴보면 다음과 같다.

# O(N) - 한 번 순회
for num in array:
    print(num)

# O(N²) - 중첩 순회
for a in array:
    for b in array:
        print(a, b)

첫 번째 코드는 입력 크기 N에 비례해서 실행되므로 O(N)이고, 두 번째 코드는 N×N번 실행되므로 O(N²)이다. 반복문이 한 단계 중첩될 때마다 차수가 하나씩 늘어난다고 보면 된다.

시간 복잡도를 계산할 때는 보통 상수를 생략하고, 입력이 커질수록 가장 빠르게 증가하는 항만 남긴다. 예를 들어 2N² + N은 O(N²)로, 3N + 5는 O(N)으로 단순화한다. 왜냐하면 입력이 커질수록 상수항과 낮은 차수의 영향은 거의 사라지기 때문이다. 결국 우리가 알고 싶은 건 “입력 크기가 커질 때 전체 실행 시간이 얼마나 빨리 커지느냐”다.

예를 들어 배열에서 최댓값을 찾는 함수를 생각해보자. 첫 번째 방법은 모든 원소를 서로 비교한다.

def find_max_num(array):
    for num in array:
        is_max = True
        for compare in array:
            if num < compare:
                is_max = False
        if is_max:
            return num

이 함수는 모든 원소가 다른 모든 원소와 비교되므로 O(N²)이다. 반면, 한 번만 순회하면서 현재까지의 최댓값을 갱신하는 방법은 훨씬 효율적이다.

def find_max_num(array):
    max_num = array[0]
    for num in array:
        if num > max_num:
            max_num = num
    return max_num

이 코드는 입력 크기만큼 한 번 순회하므로 O(N)이다. 입력값이 커질수록 첫 번째 방법은 훨씬 느려진다.

시간 복잡도를 이해한다는 건 단순히 O(N²), O(N)을 외우는 게 아니다. 입력이 커질 때 실행 횟수가 어떤 패턴으로 늘어나는지를 감각적으로 파악하는 것이다. 좋은 알고리즘은 입력이 두 배가 되어도 실행 시간이 두 배 정도로만 늘어나지만, 비효율적인 알고리즘은 입력이 조금만 커져도 시간이 폭발적으로 늘어난다.

정리하자면, 시간 복잡도는 입력 크기 대비 연산량의 증가율을 의미한다. 중첩된 반복문은 차수를 높이고, 상수나 낮은 차수는 무시한다. 효율적인 코드는 일반적으로 O(N)이나 O(N log N) 수준을 목표로 하며, 입력이 커져도 급격히 느려지지 않는다. 결국 시간 복잡도를 이해하는 것은 단순히 코드를 빠르게 만드는 기술이 아니라, 입력이 커질수록 알고리즘이 얼마나 안정적으로 작동하는지를 판단하는 사고방식이다.

그가 근무하던 연구기관 CWI (Centrum Wiskunde & Informatica) 에서는 이전에 ABC 언어라는 프로젝트를 진행하고 있었다. 이 언어는 교육용으로 설계되어 직관적이었지만, 실제 운영체제와 상호작용하기 어렵다는 한계를 지니고 있었다. 귀도는 ABC의 장점을 계승하면서, 보다 실용적이고 확장성 있는 언어를 만들기로 했다. 그렇게 1989년 크리스마스 휴가 기간 동안 시작된 개인 프로젝트가 바로 Python이다.

흥미롭게도, 파이썬이라는 이름은 ‘뱀’에서 온 것이 아니다. 귀도는 영국의 코미디 그룹 ‘Monty Python’s Flying Circus’ 의 팬이었고, 딱딱하지 않고 위트 있는 이름을 원했다. 그래서 언어 이름을 ‘Python’으로 정했다고 한다. 이 일화는 파이썬이 단순한 기술 프로젝트가 아니라, ‘인간적인 감각’을 담고 태어난 언어였음을 보여준다.

단순함을 위한 설계, 그리고 첫 번째 릴리스

1991년, 파이썬의 첫 공식 버전인 Python 0.9.1이 공개되었다. 이 초기 버전에는 이미 오늘날 우리가 익숙하게 사용하는 여러 기능이 포함되어 있었다. 클래스, 상속, 예외 처리, 리스트와 딕셔너리 같은 기본 자료구조가 모두 구현되어 있었고, 무엇보다 코드의 구조를 ‘중괄호’ 대신 들여쓰기(Indentation) 로 표현했다. 이 단순하면서도 강력한 문법 구조는 파이썬의 가장 큰 특징이 되었다.

이후 파이썬은 오픈소스 커뮤니티를 중심으로 빠르게 발전했다. 귀도는 언어를 누구나 사용할 수 있도록 공개했고, 세계 각국의 개발자들이 직접 개선에 참여했다. 덕분에 파이썬은 초보자뿐 아니라 연구자, 과학자, 엔지니어들 사이에서도 빠르게 퍼져 나갔다.

2000년대 – 생태계의 성장과 확장

2000년에는 Python 2.0이 발표되었다. 이 버전은 리스트 내포(List Comprehension), 가비지 컬렉션, 유니코드 지원 등 당시로서는 혁신적인 기능들을 도입했다. 그 결과 파이썬은 더 이상 실험적 언어가 아니라, 실무에서도 충분히 사용할 수 있는 언어로 자리 잡았다.

이 시기 파이썬의 가장 큰 성장 동력은 커뮤니티였다. 언어 자체가 단순했기 때문에, 누구나 패키지를 만들고 공유할 수 있었다. 다양한 분야의 오픈소스 라이브러리가 쏟아지면서, 파이썬은 점점 더 “무엇이든 할 수 있는 언어”로 변해갔다.

2008년에는 Python 3.0이 등장했다. 이전 버전과 호환되지 않는 대규모 변경이 이루어졌기 때문에 한동안 혼란이 있었지만, 이 업데이트는 언어의 장기적인 발전을 위한 중요한 전환점이 되었다. 문자열 처리 방식이 개선되고, 언어 전반이 현대적 구조로 재정비되었다.

전 세계로의 확산

2000년대 후반부터 파이썬은 본격적으로 대중화되었다.

웹 프레임워크 Django와 Flask가 등장하면서, 파이썬은 빠르고 직관적인 웹 개발 언어로 자리 잡았다. 이후 과학·공학 분야에서는 NumPy, SciPy, Pandas 같은 라이브러리가 등장하면서 데이터 분석의 표준 언어로 부상했다.

특히 데이터 사이언스(Data Science) 와 인공지능(AI) 분야의 부상은 파이썬의 인기를 폭발적으로 끌어올렸다. TensorFlow, PyTorch 같은 라이브러리는 파이썬을 기반으로 하고 있으며, 머신러닝 모델을 만들고 실험하는 과정이 훨씬 단순해졌다. 이러한 변화 덕분에 파이썬은 과학 연구실뿐 아니라 산업 전반에서 핵심 도구로 자리 잡았다.

현재 파이썬은 구글(Google), 페이스북(Facebook), 인스타그램(Instagram), 넷플릭스(Netflix), 드롭박스(Dropbox) 등 세계적인 기업에서 주요 언어로 사용되고 있다. 기업들이 파이썬을 선택한 이유는 단순하다. 코드가 간결하고, 생산성이 높으며, 생태계가 풍부하기 때문이다.

한계와 개선

물론 파이썬이 완벽한 언어는 아니다.

인터프리터 기반 언어이기 때문에 실행 속도가 느리다는 단점이 있다. 또, 2.x에서 3.x로 넘어가는 과정에서 호환성 문제가 발생해 혼란이 있었다. 하지만 이러한 문제는 지속적인 커뮤니티의 노력으로 점차 해결되었다. PyPy 같은 JIT(Just-In-Time) 컴파일러가 속도를 보완하고, 타입 힌트(Type Hint)나 비동기 처리(asyncio) 같은 현대적 기능도 꾸준히 추가되고 있다.

무엇보다 주목할 점은, 파이썬의 발전이 단일 기업이 아닌 전 세계 개발자 커뮤니티의 자발적인 협력을 통해 이루어졌다는 것이다. 이는 파이썬이 단순한 프로그래밍 언어를 넘어, 하나의 문화이자 협업 생태계로 자리 잡았다는 의미다.

범용 언어, 파이썬

오늘날 파이썬은 교육, 데이터 분석, 웹 개발, 인공지능, 자동화 등 거의 모든 분야에서 사용되는 범용 언어(general-purpose language) 가 되었다. 그 성공의 비결은 화려한 기술적 혁신보다, “사람이 읽기 쉽고 쓰기 쉬운 코드”라는 단순한 철학에 있다.

프로그래밍 언어의 역사는 결국 인간과 기계의 대화 방식이 진화한 역사라고 할 수 있다. 그 가운데 파이썬은 “인간 친화적인 코드”라는 방향으로 그 진화를 이끌었다.

우리가 매일 사용하는 컴퓨터는 단순히 전원을 켜고 프로그램을 실행하는 도구처럼 보이지만, 그 속에서는 수많은 복잡한 과정이 유기적으로 맞물려 돌아간다. 이 글에서는 컴퓨터가 실제로 어떻게 동작하는지, 그리고 운영체제와 커널, 드라이버가 어떤 역할을 하는지를 간단히 정리해본다.

컴퓨터는 CPU, 메모리, 저장장치, 입출력 장치 등으로 이루어져 있다. 이 중 CPU는 명령어를 해석하고 실행하는 핵심 두뇌 역할을 한다. CPU는 오직 기계어(Machine Code), 즉 0과 1로 이루어진 명령만 이해할 수 있다. 하지만 사람이 직접 이진수를 다루기는 비효율적이기 때문에, 이를 사람이 읽을 수 있는 형태로 표현한 것이 어셈블리어(Assembly)다.

예를 들어, 다음과 같은 명령이 있다고 하자.

MOV AX, 1

이 명령은 CPU에게 “AX 레지스터에 숫자 1을 저장하라”는 의미다. 실제로는 이 명령이 0과 1의 조합으로 변환되어 CPU로 전달된다. 즉, 어셈블리어는 기계어 명령을 사람이 읽기 쉽게 바꾼 형태라고 볼 수 있다.

이후 개발자들은 더 높은 생산성을 위해 고급 프로그래밍 언어(High-level Language)를 만들었다. 파이썬, 자바스크립트, C와 같은 언어들이 그 예다. 이런 언어들은 사람이 이해하기 쉬운 문장 형태로 작성되며, 내부적으로는 컴파일러(Compiler)나 인터프리터(Interpreter)를 통해 기계어로 변환된다.

즉, 프로그래밍 언어의 발전 방향은 “추상화(Abstraction)”였다. 한 줄의 코드가 여러 개의 기계 명령을 수행하게 만드는 것이다.

print("Hello World")

1. 파이썬 인터프리터가 print()를 해석함
2. 내부적으로 C 언어의 I/O 라이브러리 호출
3. C 라이브러리가 시스템 콜(System Call)을 통해 커널에 요청
4. 커널이 디바이스 드라이버에게 “화면에 이 문자열을 출력하라”고 명령
5. 드라이버가 디스플레이 하드웨어를 제어해서 실제로 “Hello World”를 보여줌

이 간단한 코드 한 줄은 사실상 메모리에 문자열을 저장하고, 출력 버퍼를 열고, 디스플레이 장치로 데이터를 전송하는 여러 복잡한 과정을 포함한다. 이처럼 추상화란 복잡한 일을 단순한 표현으로 감싸는 것이다.

한편, 로봇이나 센서 같은 임베디드 시스템에서는 CPU 성능이나 메모리가 제한되어 있기 때문에, 여전히 C나 어셈블리 같은 저수준(또는 저수준에 가까운) 언어가 많이 사용된다. 기계어를 직접 다루는 경우는 거의 없지만, 하드웨어를 세밀하게 제어할 필요가 있기 때문이다.

모든 컴퓨터는 결국 숫자만을 다룬다. 문자나 이미지조차도 숫자로 변환되어 저장된다. 예를 들어 “A”라는 문자는 아스키(ASCII) 코드로 65에 해당한다. “이 숫자는 이 문자를 의미한다”는 약속이 바로 문자 인코딩 체계(Encoding)다. 유니코드는 이를 전 세계 언어로 확장한 형태다.

이제 운영체제의 역할로 넘어가보자. 운영체제(Operating System)는 하드웨어를 효율적으로 관리하고, 여러 프로그램이 동시에 실행될 수 있도록 도와주는 시스템이다. 리눅스(Linux), 유닉스(Unix), 윈도우즈(Windows)가 여기에 속한다. 운영체제의 핵심에는 커널(Kernel)이 있다.

커널은 운영체제의 중심이며, CPU, 메모리, 디스크 같은 자원을 효율적으로 분배하고 보호한다. 하지만 커널이 모든 하드웨어의 작동 방식을 직접 알 수는 없다. 그래서 하드웨어와 소통하기 위해 드라이버(Driver)를 사용한다.

예를 들어 음악을 재생하면 커널은 “스피커로 소리 내!”라는 명령을 오디오 드라이버에 전달하고, 드라이버가 실제 스피커 하드웨어에 신호를 보내 소리를 낸다. 즉, 커널은 하드웨어를 직접 제어하지 않고 드라이버를 통해 제어한다. 프로그램이 하드웨어를 제어하기까지의 전체 흐름은 다음과 같다.

[사용자]
   ↓
[응용 프로그램 (예: Chrome, VSCode)]
   ↓
[시스템 호출 (System Call)]
   ↓
[커널 (Kernel)]
   ↓
[드라이버 (Driver)]
   ↓
[하드웨어 (CPU, 메모리, 디스크 등)]

사용자가 응용 프로그램에 명령을 내리면, 프로그램은 시스템 호출(System Call)을 통해 커널에게 요청을 보낸다. 커널은 요청을 해석하고, 적절한 드라이버를 호출하여 하드웨어에 명령을 내린다. 이렇게 커널은 모든 프로그램과 하드웨어 사이에서 중재자로 작동한다.

결국, 우리가 한 줄의 코드를 실행하는 순간 그 뒤에서는 기계어, 어셈블리, 컴파일러, 커널, 드라이버, 하드웨어가 복잡하게 맞물려 움직이고 있다. 프로그래밍을 이해한다는 건 단순히 문법을 아는 것이 아니라, 그 코드가 어떤 과정을 거쳐 실제 기계에서 실행되는지를 이해하는 것이다.