자료구조·알고리즘

알고리즘은 주어진 입력에서 원하는 결과를 만드는 절차이고, 자료구조는 그 절차가 다룰 값을 담아 두는 방식입니다. 같은 문제라도 값을 어떻게 담고 어떤 순서로 처리하느냐에 따라 프로그램이 1초 만에 끝나기도 하고 하루가 걸리기도 합니다. 이 교재는 그 차이가 어디서 생기는지를 작은 입력으로 손으로 따라가 보고, 코드를 실행해 확인하고, 왜 맞는지를 설명하는 방식으로 다룹니다.

Python을 한 번도 써 보지 않았어도 시작할 수 있도록 1장에서 설치와 실행, 오류 읽는 법부터 다룹니다. 예제는 Python 3.14와 3.15에서 실행해 확인했고 표준 라이브러리만 씁니다. 각 코드 블록은 필요한 함수와 import를 모두 담고 있어서, 앞 글의 파일을 가져오지 않고도 블록 하나만 복사해 실행할 수 있습니다. 실행 결과가 컴퓨터마다 달라지는 시간 측정 같은 예는 본문에서 그 점을 따로 밝혀 두었습니다.

글마다 있는 '더 깊이' 절은 더 빠른 방법이나 실제 라이브러리의 구현, 이론적인 배경을 궁금해하는 독자를 위한 내용입니다. 처음 읽을 때는 건너뛰어도 본문을 따라가는 데 문제가 없습니다. 각 글을 마친 뒤에는 연습 문제를 먼저 손으로 풀어 보고 해설과 비교해 보세요. 입력 하나를 바꾸면 결과가 어떻게 달라질지 먼저 예상한 다음 실행해 보는 것이 가장 좋은 연습입니다.

이 교재는 대학 강의의 주제 구성을 바탕으로 예제와 코드, 그림을 새로 만들었으며 원본 자료의 그림이나 본문을 옮기지 않았습니다.

---

학습 경로

핵심 과정은 1장부터 11장까지와 13장입니다. 12장은 핵심 과정을 마친 뒤 필요할 때 골라 읽는 선택 심화입니다.

1단계 · 준비와 분석의 도구(1–2장)에서는 Python으로 코드를 실행하고 상태를 추적하는 방법을 익힌 뒤, 문제의 입력과 출력을 정확히 정하는 법, 불변조건으로 알고리즘이 맞는 이유를 보이는 법, O·Ω·Θ로 비용을 비교하는 법을 배웁니다. 이 세 가지 도구는 뒤의 모든 장에서 되풀이해 씁니다.

2단계 · 자료 표현·탐색·정렬(3–6장)에서는 리스트와 딕셔너리가 어떤 작업을 빠르게 하는지에서 시작해 순차 탐색과 이진 탐색, 버블·선택·삽입 정렬을 만들고, 정렬이 맞는지 검사하는 방법을 익힙니다. 이어서 재귀와 분할 정복으로 병합 정렬과 퀵 정렬을, 힙으로 우선순위 큐와 힙 정렬을 만듭니다.

3단계 · 그래프와 경로(7–8장)에서는 그래프를 인접 목록과 인접 행렬로 담고, 스택으로 깊이 우선 탐색을, 큐로 너비 우선 탐색을 만듭니다. 그다음 간선에 비용이 붙은 그래프에서 Dijkstra 알고리즘으로 최단 경로를, Warshall과 Floyd–Warshall 알고리즘으로 모든 정점 쌍의 도달 가능성과 최단 거리를 구합니다.

4단계 · 동적 계획법·문자열·수치 자료(9–11장)에서는 동전 문제와 피보나치 수, LCS로 상태와 점화식을 세우는 동적 계획법을 익히고, 롤링 해시와 KMP 알고리즘으로 문자열 탐색을 다룹니다. 11장에서는 다항식과 행렬을 리스트로 담아 계산합니다.

종합(13장)에서는 지도 문제 하나에 BFS와 Dijkstra 알고리즘을 함께 적용하고 결과를 검사한 뒤, 문제를 보고 알고리즘을 고르는 질문들과 이 교재 다음에 공부할 거리를 정리합니다.

선택 심화(12장)는 Shell 정렬, 기수 정렬, 메모리보다 큰 자료의 외부 정렬과 세 파일 polyphase 병합, 그래프의 단절점과 이중 연결 성분을 다룹니다. 각 글이 4~7장의 내용을 바탕으로 하므로 그 장들을 읽은 뒤에 보는 것이 좋습니다.

---

장별 목차

다 읽은 뒤에는 알고리즘의 이름을 얼마나 외웠는지보다, 작은 입력을 주었을 때 상태가 어떻게 바뀌는지 손으로 따라갈 수 있는지, 그 알고리즘이 왜 맞고 언제 끝나는지 설명할 수 있는지, 입력이 커질 때 비용이 어떻게 늘어나는지 말할 수 있는지를 점검해 보세요.