알고리즘 & 자료구조
코딩 테스트와 기술 면접 완벽 대비
이 시리즈에서 배우는 것
- ✅ 자료구조: 배열, 리스트, 스택, 큐, 트리, 그래프, 해시테이블
- ✅ 정렬: 버블, 선택, 삽입, 병합, 퀵 정렬 + 시간복잡도 분석
- ✅ 탐색: 이진 탐색, DFS, BFS, 백트래킹
- ✅ DP: 동적 프로그래밍 패턴과 실전 문제
- ✅ 그리디: 탐욕 알고리즘, 투 포인터, 슬라이딩 윈도우
📚 자료구조 기초
코딩 테스트 필수 자료구조 완벽 정리
-
배열과 연결 리스트: 메모리 구조, 연산별 시간 복잡도, 코딩 테스트 활용
배열과 연결 리스트가 메모리에 놓이는 방식 때문에 인덱스 접근, 중간 삽입·삭제의 비용이 어떻게 달라지는지 설명하고, 투 포인터·슬라이딩 윈도우로 배열 회전, 중복 제거, k번째 큰 수 같은 문제를 Python과 C++로 풉니다.
-
스택과 큐: LIFO·FIFO 구현과 괄호 검사·BFS 같은 코딩 테스트 활용
스택(LIFO)과 큐(FIFO)를 Python list·deque와 C++ STL로 구현해 보고, 괄호 검사, 스택 두 개로 큐 만들기, 다음 큰 수, BFS 문제를 풀면서 list.pop(0)이 느린 이유와 C++ pop()이 값을 반환하지 않는 이유도 짚습니다.
-
해시 테이블: O(1) 탐색 원리, 충돌 처리, 코딩 테스트 활용 패턴
해시 함수와 체이닝·개방 주소법 충돌 처리, 부하율 관리가 평균 O(1) 탐색을 만드는 원리를 설명하고, Python dict·Counter·defaultdict로 Two Sum, 완주하지 못한 선수, 베스트앨범, 그룹 애너그램 문제를 풉니다.
-
트리 자료구조: 이진 트리, 이진 탐색 트리(BST), 전위·중위·후위 순회
루트·자식·높이 같은 트리 용어부터 전위·중위·후위·레벨 순회, 이진 탐색 트리의 삽입과 검색까지 Python으로 구현하고, 트리 높이, 대칭 트리, 최소 공통 조상(LCA) 문제를 재귀로 푸는 방법을 보여 줍니다.
-
그래프 자료구조: 인접 리스트와 인접 행렬, 그래프 탐색 기초
인접 리스트와 인접 행렬의 메모리·탐색 비용 차이를 비교하고, BFS·DFS로 연결 요소 개수, 사이클 감지, 위상 정렬을 구현합니다. 친구 추천, 작업 의존성 해결, 미로 최단 경로 같은 실제 적용 예도 함께 다룹니다.
🔄 정렬 알고리즘
버블, 선택, 삽입, 병합, 퀵 정렬 마스터
-
기초 정렬 알고리즘: 버블·선택·삽입 정렬의 동작과 O(n²)인 이유
버블·선택·삽입 정렬을 Python과 C++로 구현하며 세 알고리즘이 모두 O(n²)인 이유와 안정성 차이를 비교하고, 거의 정렬된 데이터나 작은 배열에서 삽입 정렬이 지금도 실제로 쓰이는 이유를 설명합니다.
-
고급 정렬: 퀵·병합·힙 정렬이 O(n log n)인 이유와 선택 기준
퀵·병합·힙 정렬이 O(n log n)이 되는 분할 방식을 Python과 C++ 구현으로 설명하고, 퀵 정렬 최악 O(n²)을 피하는 피벗 선택, 병합 정렬의 추가 메모리, 안정성 요구에 따라 알고리즘을 고르는 기준을 비교합니다.
-
정렬 문제 풀이: 커스텀 비교 함수, 안정 정렬, 코딩 테스트 정렬 패턴
코딩 테스트 정렬 문제 풀이, 커스텀 key, 퀵·머지·힙·카운팅 정렬의 내부 동작과 프로덕션 정렬 패턴까지 정리합니다. 코딩 테스트에서 정렬은 문제 해결의 첫 단계인 경우가 많습니다. 후보를 점수·시간 순으로 줄이거나, 그리디·이진 탐색 전에 순서를 맞출 때 sort와 key만으로 조건을 표현하는 경우가 많습니다.
🔍 탐색 알고리즘
이진 탐색, DFS, BFS, 백트래킹
-
이진 탐색: 경계 조건, lower/upper bound, 결정 문제로 바꾸는 파라메트릭 서치
정렬된 배열에서 절반씩 범위를 줄이는 이진 탐색을 반복·재귀로 구현하고, lower bound와 upper bound로 원소 개수를 세는 법, 나무 자르기처럼 답을 직접 찾는 대신 결정 문제로 바꿔 푸는 파라메트릭 서치를 설명합니다.
-
BFS와 DFS: 큐·재귀로 구현하는 그래프 탐색과 최단 거리·연결 요소 문제
BFS는 큐로, DFS는 재귀와 스택으로 구현하면서 BFS로 가중치 없는 그래프의 최단 거리를 구하는 방법과 DFS로 연결 요소를 세는 방법을 미로 탈출·섬의 개수 문제로 익힙니다. Python 재귀 한도 문제도 다룹니다.
-
백트래킹: 가지치기로 모든 경우의 수를 줄이는 방법과 N-Queen·순열·조합
백트래킹 알고리즘의 핵심 패턴(선택-재귀-되돌리기)을 순열·조합·부분집합·N-Queen·스도쿠 예제로 정리합니다. 되돌리기 누락, 가지치기 누락, 중복 결과 같은 자주 겪는 실수와 해결법도 함께 다룹니다.
💡 동적 프로그래밍
DP 패턴과 실전 문제 풀이
-
동적 프로그래밍(DP): 메모이제이션과 타뷸레이션, 점화식 세우는 법
피보나치 수열로 중복 계산 문제를 확인한 뒤, 메모이제이션(Top-Down)과 타뷸레이션(Bottom-Up)으로 같은 문제를 풀어 보고 1차원·2차원 DP와 배낭 문제에서 상태 정의, 점화식, 초기값을 세우는 순서를 설명합니다.
-
DP 패턴 정리: 1차원·2차원 DP, 배낭 문제, LIS 점화식 세우는 법
계단 오르기 같은 1차원 DP, 격자 경로와 LCS 같은 2차원 DP, 0-1 배낭과 무한 배낭, LIS의 O(n²)·O(n log n) 풀이까지 자주 나오는 DP 유형을 점화식과 Python 코드로 비교합니다.
-
DP 실전 문제 풀이: 1로 만들기·편집 거리·동전·LIS·배낭으로 점화식 연습
1로 만들기, 편집 거리, 동전 문제, LIS, 배낭 문제를 Bottom-Up과 Top-Down으로 직접 풀면서 상태 정의와 점화식 세우는 연습을 하고, 동전 문제에서 최소 개수뿐 아니라 사용한 동전까지 역추적하는 방법도 보여 줍니다.
🎯 그리디 & 고급 기법
그리디, 투 포인터, 슬라이딩 윈도우
-
그리디 알고리즘: 매 순간 최선을 선택하는 이유와 한계
그리디 알고리즘의 정당성 증명과 반례 찾기, 활동 선택·배낭 문제·최소 신장 트리 등 필수 유형을 실전 예제로 정리. 교환 논법(Exchange Argument)부터 프로그래머스·백준 문제까지 단계별로 학습.
-
투 포인터: O(n²) 탐색을 O(n)으로 줄이는 조건과 대표 문제
양 끝에서 좁혀 오는 방식과 같은 방향으로 함께 움직이는 방식, 두 가지 투 포인터 패턴으로 세 수의 합, 컨테이너 물 담기, 부분 배열 합 문제를 풀며 이중 루프를 O(n)으로 줄이는 조건을 설명합니다.
-
슬라이딩 윈도우로 부분 배열 문제 최적화하기
슬라이딩 윈도우는 연속 구간을 O(n)으로 다루는 기법입니다. 고정·가변 예제, 같은 방향 다중 포인터, 모노토닉 덱, 상각 분석, 관측·스트림 실무 패턴을 정리합니다. 연속 부분 배열이나 부분 문자열의 합·조건을 매번 처음부터 다시 계산하면 시간 초과가 나기 쉽습니다. 이 글에서는 윈도우를 한 칸씩 밀며 갱신하는 방식으로 복잡도를 줄이는 흐름을 단계적으로 익힐 수 있습니다.
학습 팁
직접 구현하기
코드를 보고 이해하는 것과 직접 작성하는 것은 다릅니다. 반드시 손으로 코딩하세요.
시간복잡도 분석
알고리즘의 효율성을 Big-O 표기법으로 분석하는 습관을 들이세요.
반복 학습
한 번에 이해되지 않아도 괜찮습니다. 여러 번 반복해서 익히세요.
문제 풀이
백준, 프로그래머스, LeetCode에서 유사 문제를 풀어보세요.