코딩 테스트 공부 로드맵 정리

 

순서	단원명 (Topic)	중요도	핵심 키워드
0	시간복잡도 & 기본기	★★★★★	Big-O, 입출력 속도, 재귀함수 이해
1	기본 자료구조 (선형)	★★★★★	배열, 연결리스트, 스택(Stack), 큐(Queue)
2	완전탐색 & 정렬	★★★★☆	Brute Force, 구현, 버블/병합/퀵 정렬
3	탐색 (DFS/BFS)	★★★★★	그래프 탐색, 미로 찾기, 네트워크
4	탐색 효율화 (비선형)	★★★★☆	해시(Hash), 이진 탐색, 투 포인터
5	탐욕법 (Greedy)	★★★☆☆	최적 부분 구조, 회의실 배정
6	동적계획법 (DP)	★★★★☆	메모이제이션, 점화식, 배낭 문제
7	고급 그래프	★★☆☆☆	다익스트라(Dijkstra), MST, 위상 정렬

 

---

Step 0. 시간복잡도 & 언어 기본 (Base)

• 왜 가장 먼저인가?
  • 코딩테스트의 채점 기준은 "정답인가?"와 "빠른가?" 두 가지입니다.
  • 내가 짠 코드가 O(N^2)인지 O(N \og N)인지 모르면, 문제를 맞고도 시간 초과로 탈락합니다. 이 기준을 먼저 세워야 공부 방향이 잡힙니다.
• 팩트체크: 기업 코테는 보통 1초(약 1억 번 연산) 제한을 둡니다.

 

Step 1. 기본 자료구조: 스택/큐 (Linear Data Structure)

• 왜 탐색보다 먼저인가?
  • 뒤에 나올 DFS(깊이 우선 탐색)는 '스택(Stack)' 구조를, BFS(너비 우선 탐색)는 '큐(Queue)' 구조를 기반으로 동작합니다.
  • 데이터를 어떻게 넣고 빼는지(FIFO/LIFO)를 모르면 탐색 알고리즘을 아예 구현할 수 없습니다.
• 배열로 스택/큐를 직접 만들어보며 포인터(인덱스) 이동 원리를 익히는 것이 베스트입니다.

 

Step 2. 완전탐색 & 정렬 (Brute Force & Sorting)

• 왜 효율화보다 먼저인가?
  • "모든 경우의 수를 다 뒤져보는 것"이 문제 해결의 시작입니다.
  • 일단 답을 구하는 방법(구현력)을 먼저 익히고, 그 다음에 시간을 줄이는 방법을 배워야 합니다.
  • 정렬(Sorting)은 뒤에 나올 '이진 탐색'과 '그리디'의 전제 조건입니다. 데이터가 정렬되어 있지 않으면 고급 기법을 사용할 수 없습니다.

 

Step 3. 그래프 탐색: DFS / BFS (Essential)

• 왜 여기서 배우나?
  • Step 1에서 배운 스택/큐와 Step 2에서 배운 '모든 경우 찾기'를 결합하는 단계입니다.
  • 삼성, 카카오 등 주요 기업 기출 빈도 1위입니다. 코테의 '허리' 역할을 하는 가장 중요한 단원입니다.

 

Step 4. 효율화: 해시 & 이진 탐색 (Optimization)

• 왜 DFS/BFS 이후인가?
  • 완전탐색(Step 2, 3)으로 풀면 시간 초과가 나는 문제들이 등장합니다. 이때 O(N)을 O(1)로 줄여주는 해시(Hash)나, O(log N)으로 줄여주는 이진 탐색이 필요합니다.
  • 즉, "답은 구할 수 있는데 너무 느릴 때" 사용하는 무기들입니다.

 

Step 5. 탐욕법 (Greedy)

• 왜 후반부인가?
  • "지금 당장 좋은 것만 선택해도 답이 된다"는 것을 증명해야 합니다.
  • 정렬(Step 2)과 우선순위 큐(자료구조)가 기본적으로 깔려 있어야 구현 가능합니다. 논리적 사고력이 요구되는 구간입니다.

 

Step 6. 동적계획법 (DP)

• 왜 가장 어려운 구간인가?
  • 큰 문제를 작은 문제로 쪼개는 방식인데, 이는 재귀(Recursion)와 DFS에 대한 완벽한 이해가 없으면 점화식을 세울 수 없습니다.
  • 앞서 배운 탐색 기법들의 비효율적인 중복 계산을 막기 위한 '메모이제이션' 기법이 핵심이므로, 탐색의 한계를 느낀 뒤에 배워야 이해가 빠릅니다.

 

Step 7. 고급 그래프 (Shortest Path)

• 왜 마지막인가?
  • 다익스트라(Dijkstra) 알고리즘은 'BFS'의 탐색 원리에 '그리디'한 선택, 그리고 '힙(Heap)' 자료구조가 모두 합쳐진 종합 예술입니다.
  • 앞 단계의 지식이 하나라도 빠지면 코드를 이해하기 어렵습니다.