TIL 2026-03-13

3/13 - 학습 정리 (챕터 3-8, 3-9)

생성일: 2026년 3월 13일 오후 5:18

챕터 3-8 그래프 개념 및 탐색

학습 목표

• 그래프의 구성 요소(노드/간선/가중치)와 특징을 이해했다.
• 인접 행렬과 인접 리스트의 구현 방식, 장단점, 성능 차이를 비교했다.
• DFS/BFS의 동작 원리와 구현 방식(재귀/스택, 큐)을 정리했다.

핵심 개념 요약

• 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 비선형 자료구조다.
• 방향성: 방향 그래프 / 무방향 그래프
• 가중치: 간선에 비용/거리 등의 값이 부여될 수 있다.
• 순환 여부: 사이클 존재 여부에 따라 문제 풀이 접근이 달라진다.

표현 방식 비교

표현	장점	단점
인접 행렬	간선 존재 확인이 빠름 O(1)	메모리 O(V^2)로 큼
인접 리스트	메모리 효율 좋음 O(V+E)	간선 존재 확인은 느릴 수 있음
추천 상황	정점 수 작고 밀집 그래프	희소 그래프/일반 코테

탐색 알고리즘 요약

• DFS: 깊게 우선 탐색. 재귀 또는 스택으로 구현.
• BFS: 가까운 레벨부터 탐색. 큐(Queue)로 구현.

// DFS (재귀)
void dfs(int u){
  visited[u] = true;
  for(int v : graph[u]) if(!visited[v]) dfs(v);
}

// BFS
queue<int> q; q.push(start); visited[start]=true;
while(!q.empty()){
  int u=q.front(); q.pop();
  for(int v: graph[u]) if(!visited[v]){ visited[v]=true; q.push(v);} 
}

복잡도 감각

알고리즘	복잡도	비고
DFS	O(V + E)	인접 리스트 기준
BFS	O(V + E)	최단 거리(무가중치) 문제에 자주 사용
인접 행렬 탐색	O(V^2)	정점이 많을수록 비효율 가능

오늘 복기

• 문제에서 그래프를 보면 먼저 “표현 방식”을 결정하는 것이 구현 난이도를 크게 좌우한다는 점을 느꼈다.
• 탐색은 DFS/BFS 중 무엇이 맞는지보다, 방문 처리와 중복 방문 방지가 더 핵심이라는 점을 확인했다.

다음 액션

• 인접 리스트 템플릿으로 DFS/BFS 기본 문제 1개씩 풀이
• 인접 행렬/리스트 변환 연습으로 표현 방식 전환 감각 익히기

챕터 3-9 백트래킹

핵심 개념

• 백트래킹은 완전탐색 중 유망하지 않은 분기를 조기에 제거(pruning)해 탐색량을 줄이는 기법이다.
• 상태공간트리에서 부분 해답을 확장하다가 조건 위반 시 즉시 되돌아온다(backtrack).
• 유망 함수(promising function)는 현재 경로가 해답으로 이어질 가능성을 판정한다.
• 대표 문제: N-Queen, 부분집합 합, 스도쿠, 그래프 색칠(CSP).

동작 템플릿

void dfs(State cur){
  if (종료조건) { 정답 처리; return; }
  for (후보 c : 후보집합){
    if (!promising(cur, c)) continue; // 가지치기
    선택 적용
    dfs(다음 상태);
    선택 복구; // backtrack
  }
}

시간복잡도 감각

• 최악에는 여전히 지수적일 수 있지만, 유망 함수 품질이 좋을수록 체감 성능이 크게 개선된다.
• 핵심은 탐색 자체보다 “언제 버릴지”를 빠르게 결정하는 데 있다.

오늘 복기

• 백트래킹을 단순 DFS가 아니라 “제약 기반 탐색 최적화”로 이해했다.
• 후보 생성보다 가지치기 조건을 먼저 설계해야 성능이 올라간다는 점을 확인했다.

다음 액션

• 부분집합 합 문제를 pruning 유/무 2버전으로 구현해 실행 횟수 비교
• N-Queen 충돌 판정(열/대각선)을 함수로 분리해 템플릿화