알고리즘Algorithms
컴퓨터 시스템 가운데, 자료 구조 · 알고리즘 설계 기법 · 복잡도 분석과 그 바탕 수학을 묶은 것으로, 문제를 유한한 계산 절차로 푸는 방법과 그 비용을 다룬다. 기계 학습 알고리즘은 AI 영역 머신러닝이 맡는다.
1요약
- 알고리즘은 자료 구조 · 설계 기법 · 문제별 알고리즘 · 복잡도 평가 · 수학 기초의 다섯 갈래와 IT 법칙으로 이뤄지고, 그 위에서 운영체제 스케줄링 · 데이터 인덱스 · 네트워크 라우팅이 이 절차를 가져다 쓴다.
- 같은 일을 해도 절차에 따라 비용이 갈린다 — 100만 건에서 O(n²) 비교는 1조 번, O(n log n) 은 약 2,000만 번이라 기계를 수만 배 빠르게 바꾸는 것보다 절차를 바꾸는 쪽이 크다(직접 계산 · 그림 5).
- 「프로그램이 느리다」는 입력을 2배로 늘렸을 때 시간이 몇 배가 되는가로 가른다 — 2배면 데이터 양 탓, 4배면 이중 반복 같은 절차 탓, 거의 그대로면 디스크 · 네트워크 같은 고정 비용 탓이다.
2등장 배경
초기 컴퓨터에서도 같은 표를 정렬하는 방법에 따라 비교 횟수가 n² 과 n log n 으로 갈렸고, 입력이 커질수록 그 차이가 기계 속도 차이를 넘어섰다. 그래서 «무엇을 계산하나»와 함께 «몇 번 계산하나»가 따로 연구됐다.
Bellman 은 1954년 부분 문제의 답을 저장해 다시 쓰는 동적 계획법을 정리했고(Bellman 1954), Dijkstra 는 1959년 세 쪽 논문에서 모든 점을 잇는 가장 짧은 나무와 두 점 사이 가장 짧은 길을 푸는 절차를 냈다(Dijkstra 1959). Knuth 는 1968년 TAOCP Volume 1 에서 스택 · 큐 · 연결 리스트 · 트리를 분석 방법과 한 틀로 묶었다(Knuth TAOCP).
지금은 NIST 가 용어 사전(DADS)으로 정의를 공개하고, 해시 테이블 · 정렬은 언어 표준 라이브러리에 들어 있다(Java SE 21 HashMap). 그래서 실무의 일은 새 절차를 만드는 것보다 알맞은 자료 구조와 절차를 고르고 그 비용을 재는 것이 됐다.
3쉽게 이해하기 — 책 100만 권 도서관의 사서
시립 도서관 사서 윤 씨는 책 100만 권을 맡는다. 반납 수레에서는 맨 위에 놓인 책부터 꽂고, 대출 예약은 온 순서대로 줄을 세운다. 청구기호 순으로 꽂힌 서가에서는 가운데를 펼쳐 반씩 버리며 20번 만에 책을 찾고, 색인 카드함은 제목으로 서랍을 바로 연다. 열람실까지는 복도 지도에서 가장 짧은 길을 고르고, 하루 걸음 수를 메모해 어느 일이 오래 걸리는지 본다.
그림 1 · 사서가 책을 놓는 방식(자료 구조)과 찾는 순서(알고리즘)를 함께 고르고, 걸음 수(복잡도)로 그 선택을 잰다.
그림 2 · 같은 «한 권 찾기»라도 책을 어떻게 놓았느냐가 쓸 수 있는 찾는 방법과 걸음 수를 정하고, 빠른 놓기에는 대가가 따른다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 사서 윤 씨 | 알고리즘 | 입력을 받아 유한한 단계 뒤 답을 내는 계산 절차다 |
| 반납 수레 | 스택 | 마지막에 넣은 항목을 먼저 꺼낸다(LIFO) · 함수 호출 기록에 쓴다 |
| 예약 줄 | 큐 | 먼저 넣은 항목을 먼저 꺼낸다(FIFO) · 작업 대기열 · BFS 에 쓴다 |
| 청구기호 서가 | 정렬 · 이진 탐색 | 순서를 맞춰 두면 반씩 줄여 log2 n 번 안에 찾는다 |
| 색인 카드함 | 해시 테이블 | 키를 해시 함수로 버킷 번호로 바꿔 평균 상수 시간에 찾는다 |
| 복도 지도 | 그래프 · 최단 경로 | 정점과 간선으로 연결을 적고 비용 합이 가장 작은 경로를 고른다 |
| 걸음 수 메모 | 시간 복잡도(Big-O) | 입력 크기 n 이 커질 때 연산 수가 늘어나는 차수를 잰다 |
⚠ 비유가 맞지 않는 곳: 사서는 지치면 느려지지만 컴퓨터의 한 연산 비용은 거의 같아서 걸음 수만 세면 되고, 반대로 캐시 · 디스크처럼 «한 걸음»의 값이 수천 배 다른 곳이 있어 같은 차수라도 실제 시간은 갈린다.
4구조 — 여섯 갈래와 아래 토픽
갈래끼리는 쌓임 관계를 이룬다. 수학 기초가 셈의 근거를 주고, 자료 구조가 데이터를 놓으며, 설계 기법이 절차의 뼈대를 정하고, 문제별 알고리즘이 그 위에서 정렬 · 경로 같은 일을 푼다. 복잡도 평가는 넷 모두를 같은 잣대(입력 크기 n 에 대한 증가 차수)로 잰다(NIST DADS big-O).
그림 3 · 문제별 알고리즘은 설계 기법 · 자료 구조 · 수학 기초 위에 서고, 복잡도 평가가 넷 모두를 같은 잣대로 잰다.
| 갈래 | 푸는 문제 | 아래 토픽 | 재는 값 |
|---|---|---|---|
| 자료 구조 | 데이터를 어디에 어떤 순서로 두나 | 스택 · 큐 · 연결 리스트 · 트리 · 그래프 · 해시 테이블 | 넣기 · 빼기 · 찾기 한 번의 비용 |
| 정렬 · 탐색 | 순서 맞추기 · 원소 찾기 · 다 둘러보기 | 정렬 · 그래프 탐색(BFS · DFS) | 비교 · 방문 횟수 |
| 그래프 최적화 | 가장 짧은 길 · 가장 싼 연결 | Graph의 Vertex 최단거리 · MST · 최소비용 · 휴리스틱알고리즘A* | 경로 · 연결 비용 합 |
| 그래픽 처리 | 화면에서 가려진 선 · 면 지우기 | 은선제거 · 은면제거 | 화소 · 다각형 비교 수 |
| 설계 기법 | 큰 문제를 어떻게 쪼개고 고르나 | 분할 정복 · 동적 계획법 · 그리디 · 몬테카를로 | 최적해 보장 여부 · 부분 문제 수 |
| 복잡도 · 평가 | 얼마나 드나 · 어느 쪽이 낫나 | 시간 복잡도(Big-O) · 알고리즘평가방법 | n 에 대한 증가 차수 · 메모리 |
| 수학 기초 | 셈과 판단의 근거 | 확률 · 베이즈규칙 · 베이즈곡선 · 논리회로 · Lagrange의 보간식 · 비선형방정식 | 확률 · 오차 · 수렴 횟수 |
| IT 법칙 · 지능 모델 | 기술 성장 경험 법칙 · 옛 규칙 기반 지능 | 무어/길더/메칼프법칙 · 파레토법칙 · 요로돈법칙 · 가우스법칙 · 퍼지이론 · 신경망회로 · Production Rule | 성장 배수 · 규칙 수 |
관련 기술과의 경계는 «절차를 만드는 곳»과 «쓰는 곳»으로 가른다. CPU 스케줄링은 운영체제, B-Tree · 인덱스는 데이터, 암호 알고리즘은 보안, 경로 계산 규약은 네트워크, 학습 알고리즘은 AI 가 맡고, 알고리즘은 그 밑의 큐 · 트리 · 그래프 · 최단 경로 절차와 비용 분석을 맡는다.
🔑 자료 구조는 «무엇을 빨리 할 수 있나»를 정하고 알고리즘은 «그것으로 무엇을 하나»를 정한다 — 그래서 둘은 따로 고를 수 없고, 복잡도는 둘을 묶은 결과를 잰다.
5동작 — 여섯 정점 지도의 최단 경로 한 건
S 에서 T 까지 가장 싼 길을 찾는 사례로, 자료 구조(그래프 · 우선순위 큐) · 설계 기법(그리디) · 문제별 알고리즘(다익스트라) · 복잡도가 한 번에 일한다. 정점 6 · 간선 9 와 가중치는 설명용 가정 값이다.
- 그래프를 인접 리스트로 저장한다 — 간선 S–A 4 · S–B 2 · B–A 1 · A–C 5 · B–C 8 · B–D 10 · C–D 2 · C–T 6 · D–T 3(가중치 모두 0 이상 · NIST DADS Dijkstra).
- 거리 표를 S = 0, 나머지 = ∞ 로 두고 우선순위 큐(힙)에 (0, S) 를 넣는다.
- 큐에서 거리가 가장 작은 S(0) 를 꺼내 확정하고 이웃을 고친다 — A = 4 · B = 2.
- B(2) 를 꺼내 확정한다 — A 는 2 + 1 = 3 으로 줄고(4 → 3), C = 10 · D = 12 가 들어간다.
- A(3) 를 꺼내 확정한다 — C 가 3 + 5 = 8 로 준다(10 → 8).
- C(8) 를 꺼내 확정한다 — D 가 8 + 2 = 10 으로 줄고(12 → 10), T = 14 가 들어간다.
- D(10) 를 꺼내 T 를 13 으로 고치고(14 → 13), 마지막으로 T(13) 를 꺼내 끝낸다 — 경로 S → B → A → C → D → T, 비용 13 · 꺼낸 횟수 6(정점마다 한 번).
그림 4 · 매번 거리가 가장 작은 정점만 확정하는 그리디 선택으로, 정점 6개를 한 번씩만 꺼내고 S 에서 T 까지 비용 13 경로를 얻는다.
그림 5 · 입력이 100만 건이면 증가 차수 하나가 연산 수를 1조 번과 2,000만 번으로 가르고, 입력을 2배로 늘린 시간 비가 그 차수를 알려 준다.
🔑 그리디가 최적인 것은 절차의 힘이 아니라 전제의 힘이다 — 다익스트라는 가중치가 0 이상일 때만 «꺼낸 정점의 거리는 다시 줄지 않는다»가 성립하고, 음수 간선이 있으면 모든 경우를 다시 셈하는 동적 계획법 쪽(벨만-포드)으로 가야 한다.
6비교 — 알고리즘과 운영체제 · 시스템 아키텍처 · 머신러닝 알고리즘의 경계
| 기준 | 알고리즘 | 운영체제 | 시스템 아키텍처 | 머신러닝 › 알고리즘 |
|---|---|---|---|---|
| 맡는 일 | 계산 절차의 설계와 그 비용 분석 | 절차를 CPU · 메모리 배분에 적용 | 절차의 비용을 서버 대수 · 용량으로 환산 | 데이터로 모델 파라미터를 맞추는 학습 절차 |
| 다루는 단위 | 입력 크기 n · 연산 수 | 프로세스 · 페이지 · 시간 할당량 | 요청 수 · 노드 수 | 학습 데이터 · 파라미터 · 손실 |
| 대표 하위 토픽 | 정렬 · 동적 계획법 · 해시 테이블 | CPU스케줄링 · 교착상태 · 요구페이징 | 시스템용량산정 · 성능튜닝 | 선형 회귀 · 결정 트리 · SVM |
| 묻는 질문 | 답을 얻기까지 몇 번 계산하는가 | 누구에게 먼저 자원을 주는가 | 몇 대면 이 부하를 견디는가 | 맞춘 모델이 새 입력에도 맞는가 |
| 결과를 재는 잣대 | 증가 차수 Big-O(NIST DADS big-O) | 대기 시간 · 반환 시간 | 응답 시간 · 가용률 | 검증 데이터의 오차 · 정확도 |
분석출력이 입력에서 하나로 정해지고 비용을 연산 수로 재는 질문이면 알고리즘을, 데이터로 맞춘 모델이 보지 않은 입력에서 얼마나 맞는지를 재는 질문이면 AI 영역 머신러닝을 보며, 절차를 자원 배분 · 서버 구성에 적용하는 판단은 운영체제 · 시스템 아키텍처가 맡는다. 근거는 표의 「결과를 재는 잣대」 행 — 앞은 n 에 대한 증가 차수(NIST DADS big-O), 뒤는 검증 데이터의 오차다.
7실무 진단 — 느림 · 틀림의 원인 가르기
분석먼저 입력 크기를 두 번 바꿔 시간 비로 증가 차수를 확인하고, 차수가 기대와 맞는데도 느리면 자료 구조의 상수 비용을, 결과가 틀리면 알고리즘의 전제를 본다. Big-O 는 n 이 충분히 클 때의 상한이므로(NIST DADS big-O) 측정은 실제 운영 크기에 가까운 n 두 개로 한다.
| # | 증상 | 의심 원인 | 맡는 쪽 | 확인 명령 · 자료 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | 데이터가 2배가 되자 시간이 4배 | 모든 쌍을 비교하는 이중 반복 | 복잡도 · 평가 | python -m timeit -s "<n 건 준비>" "<함수>" 를 n · 2n 으로 두 번 | 비 ≈ 4 면 2차 · ≈ 2 면 1차 · 「best of 5」 최솟값으로 비교(Python timeit) |
| 2 | 찾기 한 번이 데이터 크기만큼 느림 | 정렬 안 된 목록의 선형 탐색 | 자료 구조 | 찾기 1회 시간을 n 별로 측정 | n 에 비례하면 해시 테이블(평균 상수) 또는 정렬 + 이진 탐색으로 바꿈(그림 2) |
| 3 | 해시 표가 어느 순간 멈칫함 | 재해시(표 전체 재구성) | 자료 구조 | 항목 수 ÷ 버킷 수 | 항목 수가 0.75 × 용량을 넘으면 버킷 약 2배로 재구성 → 예상 크기로 초기 용량 지정(Java SE 21 HashMap) |
| 4 | 최단 경로가 실제보다 비쌈 | 음수 가중치에 다익스트라 | 그래프 최적화 | 간선 가중치의 최솟값 검사 | 최솟값 < 0 이면 전제 위반(NIST DADS Dijkstra) → 벨만-포드 |
| 5 | 분할 정복 재귀가 RecursionError | 한쪽으로 치우친 분할로 깊이가 n 에 비례 | 설계 기법 | sys.getrecursionlimit() 와 최대 재귀 깊이 비교 | 깊이가 한도에 닿으면 균형 분할 · 반복문으로(Python sys) |
8시험 대비
www.q-net.or.kr시험에서는 알고리즘의 정의 · 조건 · 분류를 묻는 정의 · 특징형, 설계 기법이나 대표 알고리즘의 단계를 쓰게 하는 동작 · 절차 설명형이 나올 수 있다. 정의 · 특징형이면 «다섯 성질 → 갈래 지도 → 설계 기법 비교 → 평가» 순서로 쓰고, 동작 · 절차 설명형이면 작은 그래프 · 배열 하나에 값을 넣어 단계마다 바뀐 값을 그린다.
- 개요 — 정의(NIST DADS · 계산 가능한 단계의 집합) · 다섯 성질(유한성 · 명확성 · 입력 · 출력 · 효과성 · Knuth TAOCP)
- 분류 — 그림 3 갈래 지도(자료 구조 · 설계 기법 · 문제별 알고리즘 · 복잡도 · 수학 기초)
- 설계 기법 비교 — 표(분할 정복 · 동적 계획법 · 그리디 · 최적해 보장 여부 · 대표 예)
- 절차 예 — 그림 4 다익스트라 단계(거리 표 갱신 · 가중치 0 이상 전제)
- 평가 — 그림 5 증가 차수 비교(log n · n · n log n · n²) · 시간 · 공간 복잡도
- 선택 기준 · 고려 사항 — 입력 크기 · 정확도 요구(휴리스틱 A* · 몬테카를로 근사) · 자료 구조의 대가
꼭 쓸 키워드
유한성명확성시간 복잡도Big-O분할 정복동적 계획법그리디최적 부분 구조다익스트라해시 테이블
다른 답안과 차이를 내는 한 가지는 Big-O 를 «상수 c 와 시작점 k 가 있는 상한»으로 정식 정의(NIST DADS big-O)하고, 그림 5 처럼 같은 n 에서 연산 수와 2배 시간 비를 숫자로 보이는 것이다.
9오해와 사실
- 오해O(n log n) 알고리즘은 어떤 입력에서도 O(n²) 보다 빠르다.사실Big-O 는 n ≥ k 부터 c 배로 위를 누르는 상한이라(NIST DADS big-O) 상수 c 가 큰 쪽은 작은 n 에서 질 수 있고, 차이는 n 이 커질 때 벌어진다(그림 5).
- 오해그리디는 늘 최적해를 준다.사실그리디는 그때그때 가장 좋은 선택을 하는 방법일 뿐이고(NIST DADS greedy), 다익스트라도 가중치 0 이상이라는 전제가 있을 때만 최적이다.
- 오해해시 테이블 찾기는 언제나 한 번이다.사실평균은 상수지만 충돌이 몰리면 한 버킷 안을 훑고, 항목이 0.75 × 용량을 넘으면 표 전체를 다시 짓는다(Java SE 21 HashMap).
10핵심 정리
| 갈래 | 핵심 연산 | 대표 비용 | 쓰는 곳 |
|---|---|---|---|
| 자료 구조 | 넣기 · 꺼내기 · 키로 찾기 | 스택 · 큐 O(1) · 해시 평균 O(1) · 균형 트리 O(log n) | 운영체제 호출 스택 · 데이터 인덱스 |
| 정렬 · 탐색 | 비교 · 교환 · 방문 | 비교 정렬 O(n log n) · 이진 탐색 O(log n) · BFS · DFS O(V + E) | 데이터 질의 처리 |
| 그래프 최적화 | 간선 완화 · 최소 간선 고르기 | 다익스트라 O(V²) · 피보나치 힙이면 O(E + V log V)(NIST DADS) | 네트워크 경로 계산 |
| 설계 기법 | 쪼개기 · 저장해 다시 쓰기 · 즉시 고르기 | 동적 계획법 = 부분 문제 수 × 한 번 비용 | 운영 계획 · 자원 배분 |
| 복잡도 · 평가 | 증가 차수 비교 · 상수 무시 | 입력 2배 → 시간 비 1 · 2 · 4 | 용량 계획 · 성능 시험 |
| 수학 기초 | 확률 계산 · 논리식 · 보간 | 오차 · 수렴 횟수 | AI(베이즈) · 컴퓨터 구조(논리회로) |
| IT 법칙 · 지능 모델 | 성장 배수 · 규칙 추론 | 해당 없음(경험 법칙) | IT 경영 · AI 기호주의 |
11참고 문헌
- 먼저 볼 문헌
- ★ Dictionary of Algorithms and Data Structures - algorithm (Paul E. Black ed.) — 알고리즘 · 자료 구조 용어의 공공 정의를 찾을 때
- ★ Dictionary of Algorithms and Data Structures - big-O notation — Big-O 의 정식 정의(상수 c · k)를 확인할 때
- ★ Dictionary of Algorithms and Data Structures - Dijkstra's algorithm — 최단 경로 알고리즘의 전제(가중치 0 이상)와 복잡도를 볼 때
- ★ The Art of Computer Programming (Volume 1 Fundamental Algorithms Third Edition 1997 · Volume 3 Sorting and Searching Second Edition 1998) — 알고리즘의 다섯 성질과 정렬 · 탐색의 고전 분석을 찾을 때
- 본문 근거
- Dictionary of Algorithms and Data Structures - dynamic programming — NIST · 2022-04 ·
xlinux.nist.gov/dads/HTML/dynamicprog.html· 확인 2026-11-09 - Dictionary of Algorithms and Data Structures - greedy algorithm — NIST · 2005-02 ·
xlinux.nist.gov/dads/HTML/greedyalgo.html· 확인 2026-11-09 - A Note on Two Problems in Connexion with Graphs (E. W. Dijkstra · Numerische Mathematik 1 · 269-271) — Springer · EuDML 기록 · 1959-12 ·
eudml.org/doc/131436· 확인 2026-11-09 - The theory of dynamic programming (R. Bellman · Bulletin of the AMS 60(6) · 503-515) — American Mathematical Society · 1954-11 ·
www.ams.org/journals/bull/1954-60-06/S0002-9904-1954-09848-8/· 확인 2026-11-09 - Class HashMap (Java SE 21 API Specification) — Oracle · 2026-11 ·
docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/HashMap.html· 확인 2026-11-09 - timeit - Measure execution time of small code snippets (Python 3.15 documentation) — Python Software Foundation · 2026-11 ·
docs.python.org/3/library/timeit.html· 확인 2026-11-09 - sys - System-specific parameters and functions (Python 3.15 documentation) — Python Software Foundation · 2026-11 ·
docs.python.org/3/library/sys.html· 확인 2026-11-09