자료구조와 알고리즘은 왜 필요한가
자료구조는 데이터를 담고 관계를 표현하는 방식이다. 알고리즘은 그 데이터를 원하는 결과로 바꾸는 절차다. 둘은 따로 떨어져 있지 않다. 같은 데이터를 다루더라도 어떤 구조에 담느냐에 따라 코드가 단순해지기도 하고, 느려지기도 한다.
예를 들어 회원 목록에서 특정 이메일을 가진 사용자를 찾는다고 하자. 회원이 100명이라면 배열을 처음부터 끝까지 훑어도 큰 문제가 없다. 하지만 회원이 1,000만 명이라면 매 요청마다 전체 배열을 확인하는 방식은 위험하다. 이메일을 키로 하는 해시맵에 담아두면 훨씬 빠르게 찾을 수 있다.
자료구조와 알고리즘은 코딩 테스트만을 위한 지식이 아니다. 실무에서는 다음과 같은 질문을 하기 위해 필요하다.
이 데이터는 자주 추가되는가, 자주 검색되는가?
순서가 중요한가, 빠른 조회가 중요한가?
전체를 매번 다시 계산해도 되는가, 중간 결과를 저장해야 하는가?
입력이 커졌을 때 지금 코드가 버틸 수 있는가?
좋은 개발자는 먼저 문제의 성격을 본다. 그리고 그 성격에 맞는 데이터 표현과 처리 방법을 고른다.
AI 생성 이미지
기본 자료구조는 접근 패턴으로 이해한다
자료구조를 외울 때 "배열은 무엇이고 연결 리스트는 무엇이다"처럼 정의만 외우면 오래 남지 않는다. 더 중요한 기준은 접근 패턴이다. 데이터를 어떤 방식으로 읽고, 추가하고, 삭제하는지가 선택의 기준이 된다.
배열: 순서가 있고 인덱스로 접근할 때
배열은 데이터를 순서대로 담는 구조다. users[0], users[1]처럼 위치를 알고 있으면 빠르게 접근할 수 있다. 목록 화면, 정렬된 결과, 페이지 단위 데이터처럼 순서가 중요한 경우에 자주 사용된다.
배열의 강점은 단순함이다. 대부분의 언어에서 기본으로 제공하고, 반복문으로 순회하기 쉽다.
const names = ["Kim", "Lee", "Park"];
console.log(names[1]); // Lee하지만 중간에 값을 자주 삽입하거나 삭제해야 한다면 비용이 커질 수 있다. 배열의 앞부분에 새 값을 넣으면 뒤에 있는 요소들을 한 칸씩 밀어야 하기 때문이다. 데이터가 작을 때는 괜찮지만, 큰 배열에서 이런 작업이 반복되면 성능 문제가 된다.
연결 리스트: 중간 삽입과 삭제가 중요할 때
연결 리스트는 각 요소가 다음 요소의 위치를 가리키는 구조다. 배열처럼 메모리상에 연속해서 놓일 필요가 없다. 특정 노드와 그 앞뒤 관계를 이미 알고 있다면 값을 추가하거나 제거하는 작업이 비교적 쉽다. 양방향 연결 리스트라면 이전 노드와 다음 노드를 모두 따라갈 수 있어 이런 변경이 더 자연스럽다.
다만 원하는 위치를 바로 찾기는 어렵다. 배열처럼 "100번째 요소"로 한 번에 이동할 수 없고, 처음부터 링크를 따라가야 한다. 그래서 연결 리스트는 단순 조회보다 삽입과 삭제가 자주 일어나는 구조를 설명할 때 유용하다.
실무에서 직접 연결 리스트를 구현하는 일은 많지 않다. 그러나 이 개념은 중요하다. 운영체제의 작업 목록, 캐시 내부 구조, 큐 구현 방식 등을 이해할 때 연결 구조가 자주 등장하기 때문이다.
스택: 가장 최근의 것을 먼저 처리할 때
스택은 나중에 들어온 데이터가 먼저 나가는 구조다. 흔히 LIFO, 즉 Last In First Out이라고 부른다. 접시를 쌓아두고 위에서부터 꺼내는 모습과 비슷하다.
스택은 "되돌아가기"와 잘 맞는다. 브라우저의 뒤로 가기, 에디터의 undo, 함수 호출 관리, 괄호 검사에 사용된다.
stack = []
stack.append("page1")
stack.append("page2")
print(stack.pop()) # page2스택을 떠올려야 하는 순간은 최근 상태부터 역순으로 처리해야 할 때다.
큐: 먼저 들어온 것을 먼저 처리할 때
큐는 먼저 들어온 데이터가 먼저 나가는 구조다. FIFO, 즉 First In First Out이라고 부른다. 대기열과 같다.
API 서버에서 작업 요청을 순서대로 처리하거나, 메시지 큐에서 이벤트를 하나씩 소비하거나, 프린터 작업을 순서대로 처리할 때 큐의 사고방식이 필요하다.
from collections import deque
queue = deque()
queue.append("job1")
queue.append("job2")
print(queue.popleft()) # job1큐는 한꺼번에 처리하기 어려운 일을 줄 세워 안정적으로 처리할 때 유용하다. 실무에서는 배치 처리, 이메일 발송, 이미지 변환 작업 등에서 자주 등장한다.
해시맵: 키로 빠르게 찾을 때
해시맵은 키와 값을 함께 저장하는 구조다. JavaScript의 객체나 Map, Python의 dict, Java의 HashMap이 대표적이다.
const userById = new Map();
userById.set("u1", { name: "Kim" });
console.log(userById.get("u1"));해시맵의 장점은 빠른 조회다. 사용자 ID로 사용자 정보를 찾거나, 상품 ID로 가격을 찾거나, 문자열이 몇 번 등장했는지 세는 문제에 적합하다. 보통은 키를 기준으로 평균적으로 빠르게 값을 찾을 수 있다고 이해하면 된다.
다만 해시맵은 정렬된 순서나 범위 탐색을 표현하는 데 적합하지 않다. 일부 언어나 구현은 입력한 순서를 보존하지만, 그것이 "점수순", "날짜순", "키의 크기순" 같은 정렬을 자동으로 해결해준다는 뜻은 아니다. 또한 키를 어떻게 만들 것인지가 중요하다. 예를 들어 캐시를 만들 때 userId만 키로 쓰면 언어 설정이나 권한 조건이 다른 결과를 잘못 재사용할 수 있다. 빠른 조회보다 먼저 올바른 키 설계가 필요하다.
트리, 힙, 그래프는 관계를 표현한다
배열, 스택, 큐, 해시맵이 기본적인 저장과 접근에 초점을 둔다면, 트리와 그래프는 데이터 사이의 관계를 표현한다.
트리: 계층 구조를 표현할 때
트리는 하나의 루트에서 여러 자식으로 뻗어 나가는 구조다. 파일 시스템, 조직도, 댓글과 대댓글, 상품 카테고리, HTML DOM 구조가 트리로 표현된다.
트리에서 중요한 질문은 "부모와 자식 관계가 무엇인가"이다. 예를 들어 쇼핑몰 카테고리에서 전자제품 > 노트북 > 게이밍 노트북이라는 관계가 있다면, 특정 카테고리 아래의 모든 상품을 찾거나 상위 카테고리를 따라 올라가는 작업이 필요하다.
데이터베이스 인덱스도 트리 구조와 관련이 깊다. 많은 데이터베이스 인덱스는 B-Tree나 B+Tree 계열 구조를 사용해 원하는 값에 가까운 위치를 빠르게 찾는다. 인덱스가 있으면 데이터베이스는 모든 행을 처음부터 끝까지 훑지 않고, 트리를 따라가며 검색 범위를 줄일 수 있다. 그래서 자료구조를 알면 "인덱스를 추가하면 왜 빨라지는가"를 더 잘 이해할 수 있다.
힙: 우선순위가 높은 것부터 처리할 때
힙은 가장 크거나 가장 작은 값을 빠르게 꺼내기 위한 자료구조다. 보통 우선순위 큐를 구현할 때 사용한다.
예를 들어 다음 작업 중 가장 급한 작업부터 처리해야 한다면 단순 큐로는 부족하다.
결제 실패 복구 작업
일반 로그 정리 작업
관리자 긴급 요청
오래 대기한 사용자 요청
이때 각 작업에 우선순위를 부여하고, 우선순위가 높은 작업부터 꺼내 처리할 수 있다. 운영체제의 스케줄링, 서버 작업 큐, 상위 N개 추천 결과 추출 같은 문제에서 힙의 사고방식이 쓰인다.
그래프: 복잡한 연결 관계를 표현할 때
그래프는 노드와 간선으로 관계를 표현한다. 트리도 그래프의 한 종류지만, 그래프는 더 자유로운 연결을 허용한다. 친구 관계, 팔로우 관계, 지도 경로, 서비스 간 의존성, 패키지 의존성은 모두 그래프로 볼 수 있다.
그래프 문제에서 중요한 질문은 다음과 같다.
A에서 B까지 갈 수 있는가?
가장 짧은 경로는 무엇인가?
순환이 있는가?
어떤 노드가 가장 많은 영향을 주는가?
예를 들어 마이크로서비스 환경에서 A 서비스가 B를 호출하고, B가 C를 호출하고, C가 다시 A에 의존한다면 장애가 순환적으로 퍼질 수 있다. 그래프 관점으로 보면 단순한 호출 목록이 아니라 의존 관계의 위험을 볼 수 있다.
Big-O는 입력이 커질 때의 위험을 읽는 언어다
시간 복잡도는 입력 크기가 커질 때 실행 시간이 어떻게 증가하는지 표현한다. 공간 복잡도는 메모리 사용량이 어떻게 증가하는지 표현한다. Big-O 표기법은 정확한 초 단위 시간을 말하는 도구가 아니다. 증가 추세를 읽기 위한 약속이다.
자주 만나는 복잡도는 다음과 같다.
O(1): 입력 크기와 관계없이 거의 일정한 시간O(log n): 입력이 커져도 비교적 천천히 증가O(n): 입력 크기에 비례해 증가O(n log n): 효율적인 정렬에서 자주 등장O(n²): 이중 반복문에서 자주 등장하며 입력이 커지면 위험O(2ⁿ): 모든 조합을 탐색할 때 자주 등장하며 작은 입력에서도 급격히 느려짐
예를 들어 사용자 목록에서 각 사용자마다 다시 전체 사용자 목록을 훑는 코드는 O(n²)가 될 수 있다.
for (const user of users) {
for (const other of users) {
// 두 사용자의 관계 확인
}
}사용자가 1,000명이면 약 100만 번 비교하지만, 100,000명이면 100억 번 비교가 된다. 코드가 짧다고 안전한 것은 아니다. 입력 크기와 반복 구조를 함께 봐야 한다.
공간 복잡도도 중요하다. 빠르게 만들기 위해 중간 결과를 해시맵에 저장하면 시간은 줄어들 수 있지만 메모리를 더 쓴다. 반대로 메모리를 아끼려고 매번 다시 계산하면 시간이 늘어난다. 실무에서는 시간과 메모리 사이의 균형을 판단해야 한다.
좋은 질문은 "이 코드의 Big-O가 무엇인가"에서 끝나지 않는다. 더 중요한 질문은 "우리 서비스의 입력 크기에서 문제가 되는가"이다. 관리자 도구에서 하루 한 번 1,000건을 처리하는 코드와, 모든 사용자 요청마다 100만 건을 훑는 코드는 다르게 판단해야 한다.
알고리즘은 문제 유형을 알아보는 도구다
알고리즘을 공부할 때 모든 기법을 외우려 하면 금방 지친다. 실무에서 더 중요한 것은 문제의 형태를 알아보는 것이다.
정렬: 순서가 판단 기준일 때
정렬은 데이터를 기준에 맞게 나열하는 작업이다. 가격 낮은 순, 최신순, 점수 높은 순처럼 대부분의 서비스 화면에 등장한다.
정렬이 필요한 문제인지 알아보는 신호는 "가장 큰 값", "가장 작은 값", "순위", "구간", "최근" 같은 표현이다. 다만 전체 정렬이 항상 필요한 것은 아니다. 상위 10개만 필요하다면 모든 데이터를 끝까지 정렬하기보다 힙을 사용해 필요한 개수만 유지하는 편이 나을 수 있다.
탐색: 원하는 값을 찾거나 가능한 경로를 확인할 때
탐색은 원하는 값을 찾는 과정이다. 배열을 처음부터 확인하는 선형 탐색, 정렬된 데이터에서 절반씩 범위를 줄이는 이진 탐색, 그래프에서 너비나 깊이를 따라가는 탐색이 있다.
이진 탐색을 떠올려야 하는 조건은 "데이터가 정렬되어 있고, 기준보다 큰지 작은지 판단할 수 있다"는 점이다. 조금 더 넓게 보면, 어떤 기준을 넘는 순간 가능과 불가능이 한쪽 방향으로 나뉘는 문제에도 이진 탐색을 적용할 수 있다. 예를 들어 특정 날짜 이후의 로그 시작 위치를 찾거나, 가능한 최소 서버 수를 찾는 문제에서 활용할 수 있다.
그래프 탐색은 연결 관계가 있을 때 필요하다. 친구 추천, 경로 찾기, 권한 상속, 의존성 분석처럼 "이어져 있는가"가 핵심인 문제다.
재귀: 같은 구조가 반복될 때
재귀는 함수가 자기 자신을 호출하는 방식이다. 폴더 안에 폴더가 있고 그 안에 또 폴더가 있는 구조처럼 같은 형태가 반복될 때 자연스럽다.
재귀를 사용할 때는 반드시 종료 조건이 있어야 한다. 종료 조건이 없으면 함수 호출이 끝나지 않아 스택이 넘칠 수 있다.
def count_files(folder):
total = 0
for item in folder.items:
if item.is_file:
total += 1
else:
total += count_files(item)
return total재귀는 코드를 간결하게 만들지만, 입력 깊이가 매우 깊다면 반복문이나 명시적인 스택으로 바꾸는 것도 고려해야 한다.
동적 계획법: 반복되는 계산을 저장할 때
동적 계획법은 큰 문제를 작은 문제로 나누고, 이미 계산한 결과를 저장해 다시 사용한다. 핵심은 "같은 계산이 반복되는가"이다.
예를 들어 추천 점수를 계산할 때 같은 사용자와 상품 조합의 중간 점수를 여러 번 계산한다면 캐시에 저장해 재사용할 수 있다. 코딩 테스트에서는 피보나치 수열 예제가 자주 나오지만, 실무에서는 중복 계산을 줄이는 캐싱 전략과도 연결된다.
동적 계획법을 떠올릴 신호는 다음과 같다.
작은 문제의 결과가 큰 문제에 사용된다.
같은 입력에 대한 계산이 여러 번 반복된다.
모든 경우를 탐색하면 느리지만, 중간 결과를 저장하면 줄일 수 있다.
그리디: 지금의 최선이 전체 최선으로 이어질 때
그리디 알고리즘은 매 순간 가장 좋아 보이는 선택을 하는 방식이다. 회의실 배정, 일부 동전 체계에서의 최소 동전 개수, 작업 스케줄링 같은 문제에서 자주 등장한다.
하지만 그리디는 항상 맞지 않는다. 지금 가장 좋아 보이는 선택이 나중에 더 나쁜 결과를 만들 수 있기 때문이다. 따라서 그리디를 적용하려면 "지역적인 최선 선택이 전체 최선으로 이어진다"는 근거가 필요하다.
실무에서는 우선순위 기반 작업 처리, 캐시에서 오래 사용하지 않은 항목 제거, 비용이 낮은 서버부터 배정하는 전략 등에서 그리디한 판단이 쓰인다. 단, 이런 전략은 실제 지표로 검증해야 한다.
실무 문제로 연결해서 생각하기
자료구조와 알고리즘은 서비스 곳곳에 숨어 있다.
검색 기능을 만든다면 문자열 탐색, 인덱스, 정렬, 랭킹 알고리즘을 만나게 된다. 단순히 데이터베이스에서 LIKE 검색을 할 수도 있지만, 데이터가 커지면 전문 검색 엔진이나 인덱싱 전략이 필요해진다.
추천 기능은 점수 계산과 정렬의 문제다. 사용자 행동, 상품 특성, 최근성, 인기도 같은 값을 조합하고 상위 결과를 빠르게 골라야 한다. 모든 상품을 매번 다시 계산하면 느리기 때문에 캐싱, 배치 계산, 우선순위 큐가 함께 사용될 수 있다.
캐싱은 해시맵 사고방식과 가깝다. 특정 키에 대한 결과를 저장해두고 다시 사용한다. 이때 어려운 부분은 저장 자체가 아니라 키 설계, 만료 시간, 데이터 변경 시점이다. 잘못된 캐시는 빠르지만 틀린 결과를 돌려준다.
스케줄링은 큐와 힙의 문제다. 먼저 들어온 작업부터 처리할지, 우선순위가 높은 작업부터 처리할지, 오래 기다린 작업을 어떻게 보호할지 결정해야 한다. 이 결정은 사용자 경험과 시스템 안정성에 영향을 준다.
배치 처리는 시간 복잡도와 공간 복잡도가 직접 드러나는 영역이다. 하루치 로그 10만 건을 처리할 때는 괜찮던 코드가 1억 건에서 멈출 수 있다. 전체 데이터를 한 번에 메모리에 올릴지, 작은 단위로 나누어 처리할지, 중간 결과를 저장할지 판단해야 한다.
선택 기준을 먼저 세운다
자료구조와 알고리즘을 잘 쓰는 방법은 어려운 기법을 많이 아는 것이 아니다. 문제의 성격을 정확히 보는 것이다.
다음 질문으로 시작하면 된다.
데이터의 크기는 얼마나 커질 수 있는가?
가장 자주 하는 작업은 조회인가, 삽입인가, 삭제인가, 정렬인가?
순서가 중요한가, 빠른 검색이 중요한가?
중복 계산이 있는가?
모든 요청마다 실행되는 코드인가, 가끔 실행되는 관리 작업인가?
메모리를 더 써서 시간을 줄일 수 있는가?
작은 서비스에서는 단순한 배열과 반복문으로 충분할 때가 많다. 그러나 데이터가 커지고 요청이 늘어나면 같은 코드가 병목이 된다. 이때 자료구조와 알고리즘 지식은 코드를 더 복잡하게 만드는 지식이 아니라, 필요한 만큼만 복잡하게 만드는 기준이 된다.
결국 핵심은 하나다. 데이터를 어떻게 저장하고 어떻게 찾을지 결정하는 순간, 프로그램의 정확성과 성능이 함께 결정된다. 자료구조와 알고리즘은 그 결정을 감으로 하지 않게 해주는 개발자의 기본 도구다.
이 노트는 보도·비평·교육·연구 목적으로 작성되었습니다. 저작권 문의가 있으시면 에서 알려주세요.