DSA 의존성 그래프: 배열에서 DP까지의 논리적 로드맵

Source: Dev.to

The Problem

우리는 데이터 구조와 알고리즘(DSA)을 마트 장바구니처럼 “오늘은 힙, 내일은 그래프” 식으로 접근하곤 합니다. 하지만 컴퓨터 과학 주제들은 서로 의존관계가 있습니다. 배열(저장 방식)과 트리(시각화)를 먼저 이해하지 않으면 힙을 이해할 수 없습니다.

저는 7단계 로드맵을 만들어 단계별로 사고 모델을 구축했습니다. 이 순서는 새로운 주제가 이전 단계에서 익힌 도구들을 활용하도록 설계되었습니다.

Phase 1: Basic Linear Structures & Their Patterns

Goal: 복잡한 노드에 들어가기 전에 순차 데이터와 인덱스 조작을 마스터한다.

• Time & Space Complexity (Big‑O): 모든 코드의 측정 기준.
• Arrays: 메모리 모델(정적 vs 동적).
• Searching & Sorting Algorithms: Two Pointers의 필수 전제조건.
• Recursion (Pattern): 기본 – 베이스 케이스 vs 재귀 케이스.
• Two Pointers (Pattern): 가장 흔한 배열 최적화 기법.
• Binary Search (Algorithm): O(log N) 논리.
• Sliding Window (Pattern): 부분 배열 및 부분 문자열.
• Prefix Sum (Pattern): 1D·2D 구간 쿼리.
• Intervals (Pattern): 구간 병합 및 삽입.
• Matrix Traversal (Pattern): 2D 그리드 순회 기본.

Phase 2: The Power of Lookup (Hashing)

Goal: 공간을 희생해 속도를 얻는다.

• Hash Table / Hash Map: O(1) 조회의 왕.
• Strings: 불변성 및 조작 기법.

Phase 3: Pointers & Recursion

Goal: 인덱스에서 레퍼런스로 이동한다.

• Linked List: 단일 및 이중 연결 리스트.
• Recursion (Advanced): 다중 재귀 호출(메모이제이션 준비).
• Stack & Queue: LIFO·FIFO 메커니즘.
• Monotonic Stack (Pattern): “다음 큰 원소” 찾기.
• Fast & Slow Pointers (Pattern): 사이클 탐지.

Phase 4: Non‑Linear Structures (Hierarchical)

Goal: 부모‑자식 관계를 이해한다.

• Trees: 높이, 깊이, 지름 특성.
• Binary Trees: 면접에서 표준 구조.
• Tree Traversals: 전위, 중위, 후위, 레벨 순회.
• Binary Search Tree (BST): 정렬된 계층형 데이터.
• Heaps / Priority Queue: 우선순위에 따라 정렬.
• Top K Elements (Pattern): 힙을 효율적으로 활용.
• Divide and Conquer (Pattern): 트리에 적용되는 병합 정렬 논리.

Phase 5: Advanced Search & Backtracking

Goal: 모든 가능성을 탐색한다.

• Backtracking (Pattern): 퍼즐 해결(스도쿠, N‑Queens).
• Tries: 자동완성을 위한 접두사 트리.

Phase 6: Connectivity (Graphs)

Goal: 다대다 관계를 모델링한다.

• Graphs: 인접 행렬 vs 인접 리스트.
• Matrix Traversal (Advanced): 그리드를 그래프로 취급.
• Graph Traversals: BFS(가중치 없는 그래프 최단 경로)·DFS.
• Union‑Find: 불연속 집합 합병(DSU).
• Shortest Path: 다익스트라 알고리즘.

Phase 7: Optimisation (The Hardest Part)

Goal: 겹치는 부분 문제를 해결한다.

• Bit Manipulation: 이진 논리.
• Dynamic Programming (DP):
  • 파이프라인: Recursion → Memoisation → Tabulation → Space Optimisation.

Why This Order?

• Recursion Split: 기본 재귀는 정렬에 필요하고, 고급 재귀는 트리와 DP에 필요하다.
• Matrix Split: 매트릭스를 순회하는 방법(Phase 1)을 알아야 BFS를 적용할 수 있다(Phase 6).
• Patterns First: “Two Pointers”는 배열 뒤에 오는 것이 자연스럽다, 왜냐하면 실제 문제에서 배열이 그렇게 사용되기 때문이다.

이 로드맵을 저장하고 잡음에 휘둘리지 마세요! 🚀