1.0 자료구조와 알고리즘 — 모든 코드에는 비용 모델이 있다

자료구조와 알고리즘은 코딩 테스트를 위한 문제 풀이 목록이 아니다. 서비스가 감당할 입력의 크기, 자주 수행할 연산, 허용할 지연과 메모리를 코드의 구조로 번역하는 언어다. 이 인트로는 이미 배열과 해시 맵을 사용하는 경력 개발자가 왜 그 비용을 다시 살펴봐야 하는지 설명하고, 문제·데이터·제약에서 선택 근거를 만드는 챕터 1의 학습 경로를 안내한다.

학습 목표

• 동작하는 코드에도 입력 크기와 연산 패턴에 따른 비용 모델이 필요한 이유를 설명한다.
• 문제, 데이터, 연산, 제약을 자료구조와 알고리즘의 선택 기준으로 바꾼다.
• 점근 분석과 벤치마크의 역할을 구분하고, 어느 단계에서 무엇을 확인해야 하는지 판단한다.
• 실무 문제를 만났을 때 챕터 1의 각 문서에서 답해야 할 질문을 세운다.

출발점: 정답인 코드가 운영에서는 오답이 된다

한 팀이 이벤트 목록에서 중복 사용자를 제거한 뒤 가입 순서대로 보여 주는 API를 만들었다. 테스트 데이터는 수백 건이고 응답도 빠르다. 몇 달 뒤 제휴 채널이 붙으면서 한 요청에 들어오는 이벤트가 수십만 건으로 늘었고, 일부 고객의 응답 시간과 메모리 사용량이 함께 치솟기 시작했다. 코드는 여전히 정확한 결과를 반환하며 테스트도 모두 통과한다.

리뷰에서는 익숙한 처방들이 나온다.

제안	아직 답하지 않은 질문
"중첩 반복문을 해시 맵으로 바꾸자"	키 하나당 메모리 비용을 감당할 수 있는가? 원래 순서를 보존해야 하는가?
"먼저 정렬하면 중복 제거가 쉽다"	입력 순서를 바꿔도 되는가? 정렬 시간과 복사 공간은 허용되는가?
"데이터베이스에서 DISTINCT로 처리하자"	계산을 어느 계층으로 옮길 뿐인지, 전송량과 DB 부하는 어떻게 달라지는가?
"벤치마크에서 가장 빠른 구현을 쓰자"	측정한 데이터 크기와 중복률이 운영 입력을 대표하는가?

네 방법 모두 어떤 조건에서는 옳다. 문제는 자료구조나 알고리즘의 이름이 아니라 선택의 전제가 비어 있다는 데 있다. 입력이 메모리에 모두 들어오는가, 결과 순서가 의미를 갖는가, 조회와 삽입 중 무엇이 지배적인가, 평균 처리량과 p99 지연 중 무엇을 지켜야 하는가에 따라 답이 달라진다.

이것이 모든 코드에 비용 모델(cost model)이 필요한 이유다. 비용 모델은 실행 시간을 소수점까지 예언하는 공식이 아니다. 입력과 연산이 변할 때 CPU 시간, 메모리, 지연이 어느 방향과 규모로 변할지 설명하는 가설이다. 이 가설이 있어야 병목이 생기기 전에 위험한 후보를 거르고, 문제가 생긴 뒤에는 무엇을 측정해야 하는지 정할 수 있다.

정확성에는 제약 안에서 끝난다는 조건이 포함된다

알고리즘의 전통적인 정확성은 모든 유효한 입력에 올바른 결과를 내는지를 묻는다. 운영 환경에서는 한 조건이 더 붙는다. 주어진 시간과 공간의 한계 안에서 결과를 내야 한다. 결과가 맞더라도 요청 제한 시간을 넘기거나 프로세스의 메모리를 고갈시키면 시스템 관점에서는 사용할 수 없는 해법이다.

따라서 구현을 평가할 때는 적어도 네 비용을 함께 본다.

비용	묻는 질문
시간	입력이 커질 때 수행할 연산 수는 어떻게 증가하는가? 개별 요청의 꼬리 지연은 어디서 생기는가?
공간	입력과 함께 메모리가 얼마나 증가하는가? 임시 복사본과 객체 오버헤드까지 포함했는가?
데이터 이동	연속 메모리를 순회하는가, 포인터를 따라 흩어진 위치를 읽는가? 네트워크나 저장소로 계산을 옮기면 무엇을 전송하는가?
복잡성	더 빠른 구현이 불변식, 오류 가능성, 유지보수 비용을 얼마나 늘리는가? 그 비용이 실제 요구사항으로 정당화되는가?

Big-O는 이 가운데 입력 크기에 따른 성장률을 압축해 보여 준다. 매우 큰 입력에서 불가능한 후보를 빠르게 제거하는 데 강력하지만, 상수 인자, 캐시 지역성, 데이터 분포, 런타임 최적화는 말해 주지 않는다. 반대로 벤치마크는 특정 환경의 실제 시간을 보여 주지만, 측정하지 않은 입력 크기와 분포까지 보장하지 않는다.

둘은 경쟁 관계가 아니다. 분석은 위험한 성장률을 먼저 거르고, 측정은 살아남은 후보의 현실 비용을 검증한다. 분석 없이 측정하면 지금의 작은 입력에만 빠른 코드를 고를 수 있고, 측정 없이 분석하면 같은 복잡도의 구현들이 실제 기계에서 크게 갈리는 이유를 놓친다.

선택은 문제·데이터·연산·제약에서 시작한다

자료구조를 고르는 질문을 "배열과 해시 맵 중 무엇이 더 빠른가?"로 시작하면 답할 수 없다. 빠르다는 말에는 대상 연산과 조건이 빠져 있기 때문이다. 다음 순서로 선택 근거를 만든다.

1. 문제와 결과의 계약을 고정한다

먼저 무엇을 계산해야 하는지와 바뀌면 안 되는 성질을 적는다. 중복 제거 사례라면 "사용자 ID가 같은 이벤트는 하나만 남긴다"만으로 부족하다. 첫 이벤트를 남기는지 마지막 이벤트를 남기는지, 원래 순서를 보존하는지, 전체 결과가 필요한지 스트림으로 내보낼 수 있는지가 알고리즘의 자유도를 결정한다.

이 단계에서 계약을 명확히 하면 불필요하게 어려운 문제를 풀지 않게 된다. 순서 보존이 필요 없다면 정렬이 후보가 될 수 있고, 최근 일정 구간만 중복을 검사하면 전체 이력을 메모리에 유지할 필요가 없다.

2. 데이터의 모양을 확인한다

같은 크기 n도 분포에 따라 비용이 달라진다. 데이터가 이미 거의 정렬되어 있는가, 중복률은 얼마인가, 키가 균일한가 특정 값에 몰리는가, 그래프가 희소한가 밀집한가를 확인한다. 평균적인 입력만 보지 말고 허용할 최대 크기와 공격적·병적인 입력도 정의한다.

자료구조는 데이터를 담는 그릇이 아니라 데이터의 모양에 대한 가정을 코드로 굳힌 표현이다. 해시 테이블은 키가 적절히 분산된다는 가정을, 균형 트리는 순서를 유지하면서 높이를 제한한다는 불변식을, 인접 리스트는 실제 간선이 가능한 모든 간선보다 훨씬 적다는 가정을 활용한다.

3. 연산의 비중을 센다

조회, 삽입, 삭제, 순회, 최솟값 추출 가운데 무엇이 얼마나 자주 일어나는지 적는다. 연결 리스트의 "중간 삽입 O(1)"은 삽입 위치를 이미 알고 있을 때의 말이다. 매번 위치를 찾기 위해 처음부터 순회한다면 전체 경로는 O(n)이다. 자료구조 표의 한 칸이 아니라 요청 하나가 거치는 연산의 합을 계산해야 한다.

읽기가 압도적인 정적 데이터와 삽입·삭제가 계속되는 데이터는 같은 표현을 요구하지 않는다. 한 번 비싸게 전처리한 뒤 많은 조회를 싸게 만드는 편이 나을 수도 있고, 업데이트 비용을 낮추기 위해 조회 비용을 받아들일 수도 있다.

4. 자원과 실패의 제약을 붙인다

입력 상한, 메모리 한도, 응답 시간, 정확성 요구, 구현 복잡성의 예산을 명시한다. 정확한 답이 필요한지 근사가 가능한지, 전체 처리량이 중요한지 단일 요청의 p99가 중요한지도 선택을 바꾼다. 동적 배열의 추가가 amortized O(1)이어도 재할당이 일어난 한 번의 요청은 길게 멈출 수 있다. 평균 비용과 최악·꼬리 비용을 구분해야 하는 이유다.

5. 예측을 적고 실제 조건에서 검증한다

후보마다 시간·공간 복잡도와 예상 병목을 먼저 적는다. 그다음 운영과 비슷한 크기, 분포, 연산 비율로 측정한다. 결과가 예측과 다르면 숫자만 채택하지 말고 어느 가정이 틀렸는지 조사한다. 런타임의 자료구조 구현, 캐시 효과, 할당과 GC, 벤치마크 자체의 오류가 간극을 만들 수 있다.

이 순서를 짧게 줄이면 다음과 같다.

계약을 고정하고 → 데이터의 모양과 연산 비중을 확인하고 → 자원 제약으로 후보를 거르고 → 예측한 뒤 측정한다.

자료구조와 알고리즘은 하나의 설계다

자료구조는 알고리즘이 수행할 연산의 비용을 결정하고, 알고리즘은 어떤 자료구조의 불변식과 연산을 필요로 한다. 둘을 따로 고르면 선택 근거가 끊어진다.

예를 들어 다익스트라 알고리즘은 아직 확정하지 않은 정점 중 잠정 거리가 가장 작은 정점을 반복해서 꺼낸다. 이 연산을 매번 배열 전체를 훑어 수행할 수도 있고, 최소 힙으로 수행할 수도 있다. 알고리즘의 아이디어는 같아도 그래프의 크기와 표현, 우선순위 큐의 구현에 따라 전체 비용이 달라진다. 반대로 최소 힙이 "빠른 자료구조"라서 쓰는 것이 아니라, 문제에 최솟값 추출이 반복된다는 연산 구조가 있기 때문에 쓰는 것이다.

실무 문제를 표준 문제로 바꾸는 모델링도 같은 선택의 일부다.

실무에서 보이는 문제	드러내야 할 구조	이어지는 선택
빌드 순서와 순환 의존	패키지를 정점, 선행 조건을 간선으로 본다	DAG라면 위상 정렬, 순환이 있으면 오류로 보고한다
캐시에서 가장 오래된 항목 제거	접근 순서 갱신과 키 조회가 반복된다	해시 맵과 순서 구조를 결합한다
두 버전의 차이 계산	같은 부분 문제가 반복되는 편집 경로다	동적 계획법 또는 문제 구조를 활용한 변형을 검토한다
작업 마감 시간을 최대한 많이 만족	선택 뒤 남는 문제의 구조가 유지된다	그리디 선택이 안전한지 교환 논증으로 확인한다

중요한 능력은 알고리즘을 처음부터 발명하는 것이 아니다. 눈앞의 도메인 용어를 걷어 내고 이미 알려진 구조로 환원한 뒤, 그 알고리즘이 성립하는 전제와 무너지는 조건을 확인하는 것이다.

이 챕터에서 세울 네 가지 판단 모델

앞의 선택 절차는 네 문서로 나뉜다.

1.1 복잡도 분석과 벤치마크

입력이 커질 때 비용은 어떻게 변하며, 그 예측을 어떻게 믿을 수 있게 측정하는가?

점근 표기가 보장하는 것과 버리는 것을 구분하고, 최악·평균·amortized 비용을 나눠 본다. JIT 워밍업, 최적화 제거, GC 노이즈, 데이터 분포 같은 벤치마크 함정을 다루며 "O(n)이니 빠르다"와 "한 번 재 보니 빠르다" 사이에 재사용 가능한 근거를 세운다.

1.2 메모리에서 보는 자료구조

같은 복잡도의 연산이 실제 기계에서 왜 다르게 나타나는가?

배열, 연결 리스트, 해시 테이블, 트리, 힙을 메모리에 놓이는 모양과 접근 경로로 다시 본다. 연속 배치와 포인터 추적, 리사이징과 충돌, 언어 런타임별 구현 차이를 통해 자료구조 이름이 아니라 실제 표현을 근거로 선택한다.

1.3 알고리즘 설계 패러다임

새 문제에서 어떤 풀이 구조를 먼저 시도해야 하는가?

부분 문제의 독립성, 중복, 국소 선택의 안전성, 가지치기 가능성이라는 신호에서 분할 정복, 동적 계획법, 그리디, 백트래킹을 선택한다. 각 패러다임이 성립하는 조건과 실패하는 반례를 함께 살펴본다.

1.4 그래프 모델링과 알고리즘

실무의 관계와 의존성을 어떻게 표준 문제로 환원하는가?

무엇을 정점과 간선으로 삼을지 결정하고, 그래프의 밀도에 맞는 표현을 고른다. 도달성, 순환, 처리 순서, 최소 비용 문제를 BFS·DFS·위상 정렬·최단 경로로 연결한다. 이 문서에서 앞선 세 모델이 하나로 합쳐진다.

네 문서는 독립된 지식 목록이 아니다. 1.1의 분석과 측정이 모든 선택의 검증법이 되고, 1.2의 메모리 표현이 1.4의 그래프와 우선순위 큐 비용을 결정한다. 1.3에서 세운 그리디의 성립 조건은 1.4의 다익스트라가 음수 간선에서 무너지는 이유를 설명한다.

이 챕터를 읽는 방법

각 문서에서 구현을 따라가기 전에 다음 기록을 남긴다.

1. 먼저 입력과 연산을 적는다. n이 무엇인지, 어떤 연산이 몇 번 수행되는지 정하지 않은 복잡도는 판단에 쓸 수 없다.
2. 전제를 문장으로 쓴다. 키 분포, 정렬 상태, 그래프 밀도, 가중치의 부호처럼 알고리즘이 기대는 조건을 드러낸다.
3. 측정 전에 방향을 예측한다. 어느 후보가 어떤 구간에서 유리할지와 경계가 생기는 이유를 먼저 적는다.
4. 평균만 보지 않는다. 최악 입력, 재할당 순간, 충돌, 재귀 깊이처럼 추상화가 흔들리는 경계 조건을 확인한다.
5. 더 단순한 선택을 기준선으로 둔다. 복잡한 자료구조와 알고리즘은 실제 제약에서 이득이 확인될 때 채택한다.

챕터 1의 실습에서는 동적 배열, 연결 리스트, 해시 맵, 이진 힙을 직접 구현한다. 목표는 표준 라이브러리를 대체하는 데 있지 않다. 재할당, 포인터 추적, 충돌, 힙 복구 같은 숨은 비용을 계측하고, 복잡도 예측과 실측이 갈린 이유를 자기 언어로 설명하는 데 있다.

정리

• 자료구조와 알고리즘은 정답을 만드는 기법을 넘어, 입력 크기·연산 패턴·자원 제약을 구현 선택으로 번역하는 비용 모델이다.
• 점근 분석은 성장률이 위험한 후보를 거르고, 벤치마크는 실제 데이터와 환경에서 살아남은 후보를 비교한다. 어느 하나가 다른 하나를 대신하지 않는다.
• 선택은 자료구조 이름이 아니라 결과의 계약, 데이터의 모양, 연산 비중, 시간·공간·정확성 제약에서 시작한다.
• 자료구조와 알고리즘은 분리된 목록이 아니다. 문제를 표준 구조로 환원하고 필요한 연산을 찾은 뒤, 그 연산을 뒷받침하는 표현을 함께 설계한다.
• 챕터 1은 성장률과 측정, 메모리 배치, 설계 패러다임, 그래프 환원을 연결해 선택을 설명하고 검증하는 능력을 만든다.

확인 문제

1. 이벤트 중복 제거 구현에서 해시 테이블 방식이 중첩 반복문보다 점근적으로 유리하다는 사실만으로 채택을 결정할 수 없는 이유를 설명하라. 결정을 위해 추가로 확인할 조건을 세 가지 이상 제시하라.

정답과 해설

점근 복잡도는 입력 증가에 따른 연산 수의 성장률을 비교하지만, 메모리 한도, 순서 보존 계약, 키 분포와 해시 비용, 실제 입력 크기, 꼬리 지연은 결정하지 않는다. 예를 들어 첫 이벤트와 마지막 이벤트 중 무엇을 보존할지, 입력 순서를 유지해야 하는지, 최대 입력과 중복률이 얼마인지, 키와 값의 객체 오버헤드를 포함한 해시 테이블이 메모리에 들어오는지, 리사이징 순간의 p99를 허용하는지를 확인해야 한다. 분석으로 큰 입력에서 중첩 반복문을 후보에서 거른 뒤, 살아남은 해시·정렬·스트리밍 후보를 실제 분포로 측정한다.

2. 팀원이 "연결 리스트는 중간 삽입이 O(1)이므로 배열보다 낫다"고 주장한다. 이 문장을 비용 모델로 바꾸기 위해 어떤 질문을 해야 하는가?

정답과 해설

O(1)은 삽입할 노드의 위치를 이미 알고 있고 링크 변경만 세는 조건부 비용이다. 실제 요청이 삽입 위치를 찾기 위해 리스트를 처음부터 순회한다면 전체 경로는 O(n)이다. 위치를 어떻게 찾는지, 삽입과 순회의 비중은 얼마인지, 데이터 크기는 얼마인지, 노드가 메모리에 흩어져 생기는 포인터 추적 비용과 객체 오버헤드를 감당할 수 있는지를 물어야 한다. 배열의 이동 비용과 연결 리스트의 탐색·메모리 접근 비용을 실제 연산 비율로 합산한 뒤 측정해야 한다.

3. 두 구현이 모두 O(n log n)이고 작은 테스트에서는 A가 더 빠르다. 운영 입력이 백 배로 커질 예정일 때 어떤 순서로 판단해야 하는가?

정답과 해설

먼저 두 표기에서 n과 지배 연산이 같은지, 최악·평균 중 무엇을 비교했는지 확인한다. 다음으로 메모리 사용량, 입력의 정렬·중복 분포, 할당과 데이터 이동처럼 Big-O가 버린 비용을 가설로 적는다. 운영과 비슷한 크기와 분포를 여러 단계로 늘려 가며 워밍업·반복·환경 통제를 갖춘 벤치마크를 수행하고, 처리량뿐 아니라 메모리와 꼬리 지연도 관찰한다. 작은 테스트의 한 점을 외삽하지 않고 입력 크기에 따른 곡선과 교차점을 확인한 뒤 요구사항을 만족하는 더 단순한 구현을 선택한다.

참고 자료

• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms 4th ed. (2022) — 점근 분석, 기본 자료구조, 설계 패러다임, 그래프 알고리즘의 표준 모델을 확인한다.
• Jon Bentley, Programming Pearls 2nd ed. (1999) — 문제를 정확히 정의하고 표현·알고리즘·측정을 함께 설계하는 실무적 문제 해결 관점을 참고한다.
• Peter J. Denning, The Locality Principle (2005) — 계산 비용이 연산 수뿐 아니라 데이터 접근의 지역성에 좌우되는 이유를 이해하는 배경 자료다.
• Brendan Gregg, Systems Performance 2nd ed. (2020), 12장 Benchmarking — 가설, 실험 설계, 워크로드 대표성을 포함한 벤치마크 방법론을 참고한다.