자료구조와 알고리즘은 어떻게 연결될까?

자료구조(Data Structure)와 알고리즘(Algorithm)은 대학 컴퓨터공학 커리큘럼에서도, 코딩 테스트 준비에서도 늘 같이 등장한다. 근데 막상 공부하다 보면 이 둘이 어떻게 연결되는지 감이 잘 안 오는 경우가 있다. 따로따로 공부하다 보면 더 그렇다.

간단하게 정리하면 이렇다. 자료구조는 데이터를 담는 그릇이고, 알고리즘은 그 그릇으로 무엇을 어떻게 할지를 결정하는 방법이다. 그릇 없이는 방법도 없고, 방법 없이는 그릇이 무용지물이다.

배열(Array)과 정렬 알고리즘의 관계

배열은 가장 기본적인 자료구조다. 데이터를 번호가 매겨진 칸에 순서대로 저장한다. 이 배열에 저장된 데이터를 어떤 순서로 나열할지가 정렬 알고리즘이다.

버블 정렬은 배열에서 인접한 두 원소를 비교해서 순서가 바뀌면 교환하는 방식을 반복한다. 선택 정렬은 배열에서 최솟값을 찾아 앞으로 이동시키는 방식이다. 퀵 정렬은 기준값(pivot)을 설정하고 기준보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 나누며 재귀적으로 정렬한다.

이 모든 알고리즘은 배열이라는 자료구조를 전제로 한다. 배열이 없으면 비교하고 교환할 공간 자체가 없다. 반대로 배열만 알고 이 알고리즘들을 모르면, 데이터가 1,000만 개일 때 효율적으로 정렬하는 방법을 선택할 수 없다.

스택(Stack)과 DFS 알고리즘의 관계

스택은 마지막에 넣은 데이터를 먼저 꺼내는 구조(LIFO, Last In First Out)다. 뷔페 접시처럼 쌓아두고 위에서부터 꺼낸다.

DFS(Depth First Search, 깊이 우선 탐색)는 그래프나 트리를 탐색할 때 한 방향으로 최대한 깊이 들어간 뒤 돌아오는 방식이다. 이 DFS를 구현할 때 스택을 사용한다. 탐색한 경로를 스택에 쌓아두고, 더 이상 갈 곳이 없으면 스택에서 꺼내 이전 위치로 돌아온다.

미로를 탈출하는 알고리즘을 생각하면 이해가 쉽다. 막힌 길을 만나면 왔던 길을 되짚어(스택에서 꺼내) 다른 방향을 탐색한다. 스택이라는 자료구조가 DFS 알고리즘을 가능하게 만드는 것이다.

큐(Queue)와 BFS 알고리즘의 관계

큐는 먼저 넣은 데이터를 먼저 꺼내는 구조(FIFO, First In First Out)다. 은행 대기줄과 같다.

BFS(Breadth First Search, 너비 우선 탐색)는 출발점에서 가까운 노드들을 먼저 탐색하고 점점 멀어지는 방식이다. SNS에서 친구의 친구를 찾거나, 지도에서 최단 경로를 찾을 때 BFS를 사용한다.

BFS 구현에는 큐를 사용한다. 탐색할 노드를 큐에 넣고, 큐 앞에서부터 꺼내 탐색한다. 큐의 선입선출 특성이 BFS의 "가까운 것부터 탐색" 특성을 만들어낸다.

DFS는 스택, BFS는 큐 — 이 연결 관계를 이해하면 코딩 테스트에서 어떤 탐색 방법을 선택해야 할지 판단이 훨씬 빨라진다.

트리(Tree)와 이진 탐색의 관계

트리는 계층 구조로 데이터를 표현하는 자료구조다. 폴더 구조, 조직도, 가계도가 모두 트리 구조다.

이진 탐색 트리(BST, Binary Search Tree)는 각 노드가 최대 두 개의 자식을 가지며, 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 규칙을 갖는다. 이 구조 덕분에 이진 탐색 알고리즘을 적용하면 O(log n)의 빠른 속도로 데이터를 찾을 수 있다.

데이터베이스 인덱스가 왜 빠른지를 이해하는 것도 이 맥락이다. B-tree(B트리)라는 자료구조를 인덱스에 사용함으로써 수백만 건 데이터에서도 빠른 검색이 가능하다.

해시(Hash)와 O(1) 검색의 관계

해시 테이블은 키(Key)와 값(Value)을 쌍으로 저장하는 자료구조다. 해시 함수를 통해 키를 특정 위치에 매핑함으로써, 배열처럼 인덱스로 바로 접근하는 방식이다.

이진 탐색이 정렬된 데이터에서 O(log n)을 달성한다면, 해시 테이블은 평균 O(1)이다. 10명 중 1명을 찾든, 100만 명 중 1명을 찾든 속도가 같다는 의미다.

Python의 딕셔너리(dict), Java의 HashMap, JavaScript의 Object가 모두 해시 테이블 기반이다. 이 도구들을 쓸 때 내부에서 해시 함수가 동작하고 있다는 걸 알면 언제 쓸지, 왜 충돌이 발생하는지 이해하게 된다.

정리하면, 자료구조와 알고리즘은 서로를 전제로 존재한다. 자료구조는 알고리즘을 구현할 기반이고, 알고리즘은 자료구조의 특성을 활용해 문제를 푸는 방법이다. 이 연결 관계를 이해하는 것이 단순히 외우는 것보다 훨씬 강력한 지식이 된다.

자주 묻는 질문

Q. 자료구조와 알고리즘 중 어떤 것을 먼저 공부해야 하나요?

A. 자료구조를 먼저 공부해야 합니다. 알고리즘은 자료구조를 기반으로 동작하기 때문에, 자료구조 개념 없이는 알고리즘의 구현 방식을 이해하기 어렵습니다.

Q. 자료구조와 알고리즘을 공부한 후 코딩 테스트 준비는 어느 정도 걸리나요?

A. 개인 차가 크지만, 주요 자료구조(배열, 스택, 큐, 트리, 해시)와 알고리즘(정렬, DFS/BFS, DP)을 익히고 문제 풀이를 병행하면 3~6개월 내에 기업 코딩 테스트에 도전할 수 있는 수준이 됩니다.

Q. 자료구조별 시간 복잡도를 어떻게 외워야 하나요?

A. 외우기보다 이해하는 것이 중요합니다. 배열은 인덱스로 접근하니 O(1), 탐색은 전체를 봐야 하니 O(n), 이진 탐색 트리는 반씩 줄이니 O(log n) — 원리를 이해하면 복잡도가 자연스럽게 유도됩니다.

Q. 실무에서 자료구조와 알고리즘을 직접 구현하는 경우가 있나요?

A. 정렬이나 탐색을 직접 구현하는 경우는 드뭅니다. 하지만 데이터 파이프라인 설계, 캐시 전략 선택, 검색 기능 최적화 등에서 자료구조·알고리즘 지식이 의사결정의 기반이 됩니다.

Q. 해시 충돌이 발생하면 어떻게 되나요?

A. 서로 다른 키가 같은 해시값을 가리키는 경우를 충돌이라고 합니다. 체이닝(같은 위치에 연결 리스트로 추가)이나 개방 주소법(다음 빈 공간을 찾아 저장) 방식으로 해결합니다. 충돌이 많아지면 O(1) 성능이 저하되므로, 좋은 해시 함수 설계가 중요합니다.