알고리즘 · 자료구조
자료구조와 그래프 탐색의 연산 계약
먼저 자주 수행할 연산과 필요한 시간 복잡도 보장을 정의한 뒤, 스택·큐·배열·리스트·트리·힙·해시 테이블과 탐색 방식을 선택합니다.
이럴 때 필요해요
겉보기에는 똑같은 동작을 하는 코드라도 내부 자료구조 선택에 따라 대규모 데이터에서 O(1)과 O(n)의 큰 성능 차이가 나기 때문에 필요합니다.
어떻게 동작하나요?
1. 스택(Stack)과 큐(Queue): 스택은 나중에 넣은 것을 먼저 꺼내는 후입선출(LIFO), 큐는 먼저 넣은 것을 먼저 꺼내는 선입선출(FIFO)이라는 '처리 순서 약속(추상 자료형)'입니다. 스택은 자바스크립트 배열 끝에서 push와 pop만 쓰면 간단히 O(1)로 동작하지만, 큐를 배열의 맨 앞 요소를 빼는 shift()로 구현하면 뺄 때마다 뒤쪽 요소를 전부 한 칸씩 당기는 O(n) 비용이 듭니다. 따라서 큐에 데이터가 많을 때는 앞쪽 인덱스를 가리키는 포인터(head)를 두거나 연결 리스트·원형 버퍼로 구현해야 O(1)을 지킬 수 있습니다.
2. 배열(Array)과 연결 리스트(Linked List): 고전적인 연속 배열은 인덱스로 원하는 위치를 즉시 계산해 조회가 O(1)이지만, 중간에 값을 끼워 넣거나 지우려면 뒤쪽 요소를 밀고 당기는 O(n) 이동이 필요합니다. 반대로 연결 리스트는 원하는 위치까지 포인터를 따라 찾아가는 탐색에 O(n)이 걸리지만, 이미 해당 노드의 참조를 알고 있다면 앞뒤 링크만 고치는 작업은 O(1)입니다. 참고로 자바스크립트의 Array는 C 언어의 고정 크기 연속 메모리 배열과 달리 크기가 동적으로 변하고 빈 슬롯(희소 배열)도 허용하는 객체라는 점을 구분해 두어야 합니다.
3. 이진 트리(Binary Tree)와 힙(Heap): 이진 트리는 자식 노드가 최대 2개인 구조입니다. 여기서 마지막 층 전까지 꽉 차고 마지막 층은 왼쪽부터 빈틈없이 채워진 모양 조건을 완전 이진 트리라고 하고, 왼쪽 자식은 현재 노드보다 작고 오른쪽 자식은 크다는 값의 순서 조건을 이진 탐색 트리(BST)라고 합니다. 한편 우선순위 큐를 만들 때 쓰는 이진 힙(Binary Heap)은 완전 이진 트리 모양을 유지하면서 '부모가 자식보다 항상 우선순위가 높다'는 조건만 만족하여 최솟값·최댓값 루트 조회를 O(1), 삽입과 루트 삭제를 O(log n)에 처리합니다. (전체 정렬이나 임의 검색 용도는 아닙니다)
4. 해시 테이블(Hash Table): 키를 해시 함수에 넣어 버킷 위치를 바로 찾아가는 자료구조로, 키들이 고르게 흩어지고 부하율(Load Factor)이 적당히 유지되면 조회·삽입·삭제가 기대(평균) O(1)에 동작합니다. 하지만 여러 키가 한 버킷에 몰리는 해시 충돌이 심해지면 결국 버킷 안의 항목들을 일일이 비교해야 해서 최악의 경우 O(n)까지 느려질 수 있습니다. 버킷 배열을 두 배로 늘리는 리사이징 비용(상환 O(1))과 긴 문자열 키의 해시 계산 비용도 함께 고려해야 합니다.
5. 그래프 탐색(DFS와 BFS): 정점(V)과 간선(E)으로 이루어진 그래프를 재귀 없이 반복문으로 돌 때, 깊이 우선 탐색(DFS)은 명시적 스택을 쓰고 너비 우선 탐색(BFS)은 큐를 써서 다음 방문 후보를 관리합니다. 사이클이 있는 그래프에서 무한 루프를 막으려면 방문 집합(visited)이 필수이며, 특히 BFS는 큐에서 꺼낼 때가 아니라 큐에 넣을 때 방문 표시를 해야 중복 삽입을 막고 인접 리스트 기준 O(V + E) 시간 안에 시작점으로부터의 최단 간선 거리를 찾을 수 있습니다.
6. 제한된 flat 구현 연습: 중첩 배열을 지정한 깊이(depth)만큼만 펼치는 flat 함수를 직접 구현할 때는 먼저 '일반 배열과 0 이상의 정수 depth(기본값 1)만 다루고 원본 배열은 변경하지 않는다'고 입력 계약을 명확히 세웁니다. 배열을 순회하며 !(i in array)로 빈 슬롯(Hole)은 건너뛰고, 현재 원소가 배열이면서 남은 depth > 0일 때만 depth - 1로 재귀 평탄화한 값들을 결과에 이어 붙이면 깔끔하게 동작합니다.
코드 예제
동작을 설명하는 읽기 전용 예제입니다.
// 일반 배열과 비음수 정수 depth만 지원하는 설명용 구현
function flatten(array, depth = 1) {
const result = [];
for (let i = 0; i < array.length; i++) {
if (!(i in array)) continue;
const item = array[i];
if (Array.isArray(item) && depth > 0) {
for (const value of flatten(item, depth - 1)) result.push(value);
} else result.push(item);
}
return result;
}
// flatten([1, , [2, [3]]], 1) → [1, 2, [3]]남은 깊이(depth)가 0보다 클 때만 내부 배열을 한 단계씩 펼치고, 순회 도중 희소 배열의 빈 슬롯(!(i in array))은 건너뛰는 학습용 구현입니다. 아주 깊은 중첩에서의 콜 스택 한도나 네이티브 명세의 모든 특수 옵션(species 등)은 지원 범위 밖으로 구분합니다.
자주 헷갈리는 포인트
- 연결 리스트 중간에 값을 넣을 때 그 위치까지 찾아가는 탐색 비용 O(n)을 빼먹고 무조건 O(1)이라고 설명하면 안 됩니다.
- 해시 테이블의 기대(평균) O(1) 성능과 어떤 최악의 충돌 입력에서도 보장되는 최악 O(1)을 같은 것으로 혼동하면 안 됩니다.
내 말로 설명해 보기
'가장 작은 값을 반복해서 빠르게 꺼내는 작업'과 '특정 키 이름으로 값을 바로 찾는 작업'에는 왜 각각 이진 힙과 해시 테이블이라는 서로 다른 자료구조가 적합할까요?
함께 읽으면 좋은 개념
관련 면접 질문 7개
스택(Stack)과 큐(Queue)는 어떤 순서로 데이터를 처리하며 구현 시 무엇을 주의해야 하나요?
스택은 마지막에 넣은 값을 먼저 꺼내는 후입선출(LIFO) 추상 자료형이고, 큐는 먼저 넣은 값을 먼저 꺼내는 선입선출(FIFO) 추상 자료형입니다. 스택은 함수 호출 복귀와 DFS에, 큐는 작업 대기열과 BFS에 잘 맞습니다. 다만 배열, 연결 리스트, 원형 버퍼 중 어떤 자료구조로 내부를 구현하느냐에 따라 실제 연산 비용이 달라지므로 추상적인 처리 순서와 구체적인 시간 복잡도를 구분해 설명해야 합니다.
꼬리질문과 참고자료 →재귀를 쓰지 않고 반복문으로 DFS와 BFS를 구현할 때 핵심 차이점은 무엇인가요?
반복문으로 구현할 때 가장 큰 차이는 탐색 후보를 관리하는 자료구조로 DFS는 명시적 스택(Stack)을, BFS는 큐(Queue)를 사용한다는 점입니다. 시작 정점을 넣고 하나씩 꺼내 인접 정점을 확장하면서 방문 집합(visited)으로 사이클과 중복 탐색을 막으며, 특히 BFS는 큐에 넣는 시점에 방문 표시를 해 중복 삽입을 방지합니다. 인접 리스트에서 각 정점과 간선을 상수 번씩만 처리하면 두 방식 모두 시간 복잡도는 O(V + E)입니다.
꼬리질문과 참고자료 →Array.prototype.flat의 제한된 학습용 버전을 직접 구현한다면 어떤 가정을 세우고 어떻게 작성하나요?
먼저 '일반 배열 입력과 0 이상의 정수 depth(기본값 1)만 지원하고 원본을 바꾸지 않는 새 배열을 반환한다'고 입력 가정과 경계를 명확히 밝힙니다. 그다음 배열을 순서대로 순회하며 !(i in array)로 빈 슬롯(Hole)은 건너뛰고, 현재 값이 Array.isArray이면서 남은 depth가 양수이면 depth - 1로 재귀 평탄화한 결과를 이어 붙이고 아니면 그대로 추가합니다. 네이티브 flat의 Infinity 변환, 유사 배열, species 처리까지는 범위 밖임을 함께 덧붙입니다.
꼬리질문과 참고자료 →