[파이썬 알고리즘 인터뷰] 12장 - 그래프

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

• 그래프
  • 객체의 일부 쌍(pair)들이 '연관되어' 있는 객체 집합 구조
• 오일러 경로
  • 한붓 그리기
  • 모든 간선을 한 번만 방문하는 유한 그래프
• NP-complete (Non-deterministic Polynomial time) problem
  비결정론적 다항시간
  
  • 해밀턴 경로
    - 각 정점을 한 번씩만 방문하는 무향/유향 그래프 경로
    - 오일러 경로는 간선 기준, 해밀턴 경로는 정점 기준
  • 해밀턴 순환
    - 해밀턴 경로이면서 원래 출발점으로 돌아오는 경로
  • 외판원 문제 (TSP, Traveling Salesman Problem)
    - 해밀턴 순환 중 최단 경로
  • 비교

해밀턴 경로	한 번만 방문하는 경로
해밀턴 순환	한 번만 방문하여 출발지로 돌아오는 경로
외판원 문제	한 번만 방문하여 출발지로 돌아오는 경로 중 가장 짧은 경로

 

• 그래프 순회
  • 그래프 탐색, 그래프의 각 정점을 방문하는 과정
  • 크게 2가지 알고리즘
    1. 깊이 우선 탐색 (DFS, Depth-First Search)
    2. 너비 우선 탐색 (BFS, Breadth-First Search)
  • 코딩 테스트시 대부분의 그래프 탐색은 DFS
  • 그래프 표현 방법 2가지
    1. 인접 행렬 (Adjacency Matrix)
    2. 인접 리스트 (Adjacency List)
• DFS
  1. 백트래킹으로 효율을 높일 수 있음
  2.  스택
     • 모든 인접 간선을 추출하여 도착점들을 스택에 삽입
     • 역순으로 방문 (가장 마지막 삽입 노드부터 반복)
  3. 재귀
     • 방문했던 정점(discovered)을 활용하여 중복 탐색 방지
     • 사전적 순서로 방문
• BFS
  • 주로 큐로 구현 (데크로 최적화)
  • 최단 경로 문제에 활용
  • 재귀로 구현 불가
• 백트래킹
  • 해결책에 대한 후보를 구축하여 가능성 없는 후보를 즉시 포기하는 알고리즘
  • 제약 충족 문제(Constraint Satisfaction Problem)에 유용
  • 주로 재귀로 구현
  • 시행착오를 덜 거쳐 도착하거나, 최악의 경우 모든 경우를 거쳐 브루트 포스와 유사해짐
  • 트리의 가지치기(Pruning)
    - 트리에서 불필요한 부분을 일찍 포기하여 탐색을 최적화
• 제약 충족 문제
  • 수많은 제약 조건(Constraints)을 충족하는 상태(States)를 찾아내는 수학 문제
  • 휴리스틱 + 조합 탐색 개념 결합으로 문제 풀이
  • 스도쿠
    - 제약 조건 : 1~9 숫자를 한 번만 넣음
    - 상태 : 정답
  • 십자말 풀이, 8퀸 문제, 4색 문제 / 배낭 문제, 문자열 파싱, 조합 최적화 문제 등