[2024 동계 모각코] 8주차 계획
8주차 계획
개요
8주차(2. 19 ~ 2. 25)의 계획입니다.
- 27장 그래프의 표현과 정의
- 내용
- 28장 그래프의 깊이 우선 탐색
- 서론
- 문제: DICTIONARY
- 문제: WORDCHAIN
- 문제: GALLERY
- 문제: MEETINGROOM
- 29장 그래프의 너비 우선 탐색
- 서론
- 문제: SORTGAME
- 문제: CHILDRENDAY
- 문제: HANOI4B
- *
개요
8주차(2.19 ~ 2.25)의 학습 계획을 정리합니다.
이번 주에는 그래프의 표현 방식과 DFS/BFS 탐색 기법을 집중적으로 학습하며, 이를 활용한 다양한 문제를 해결합니다.
27장 그래프의 표현과 정의
내용
그래프의 정의와 종류와, 표현 방법(인접 리스트 vs 인접 행렬)에 대해 배웠습니다.
28장 그래프의 깊이 우선 탐색
서론
DFS에 대해 알고, 이것을 어디에 사용할 수 있는지 알아봅시다.
그 후 DFS에서 edge를 구별해 위상 정렬의 정당성 증명이나, Graph의 cycle 여부나, cut vertex(절단점) 찾기,
문제: DICTIONARY
알파벳의 사전적 순서를 다시 재정의 하는 문제입니다.
위상 정렬(Topological Sort)을 구현하는 문제이고, 이를 잘 수행하는 알고리즘인 칸 알고리즘(Kahn’s algorithm)을 이용해 풀었습니다.
문제: WORDCHAIN
오일러 경로(Euler trail) 문제를 풀어봅시다.
문제: GALLERY
최소 지배 집합(Minimum Dominating Set) 문제를 풀어봅시다.
그래프를 루트 없는 트리라고 생각해서 풀면 됩니다.
조금 그리디 하게 접근해서, 리프 노드에는 터미널을 설치 안하면 되는 것을 알 수 있습니다.
그렇게 리프 노드부터 위로 올라가면서, 설치 해야할 때와, 설치 안해도 될 때를 잘 구별하면 됩니다.
문제: MEETINGROOM
2-SAT 문제로 변형해서 2-SAT문제를 함의 그래프(Implication Graph)로 변형, 이후에 SCC(Strongly Connected Component)를 구분하여 문제를 풀어봅시다.
29장 그래프의 너비 우선 탐색
서론
BFS와 BFS, 양방향 BFS, IDS에 대해 배우고 이것을 상태 공간 탐색 문제에 써먹을 수 있음을 알아봅시다.
문제: SORTGAME
상태 공간 탐색(State Space Search) 문제를 풀어봅시다.
완전 탐색 + BFS로 풀 수 있습니다.
어떤 배열의 나열 상태를 표현하는 것은 lehmer code를 이용하고,
이를 통해 이미 정렬된 배열을 $state = 0$으로 가정하면, 주어진 순서의 배열의 상태 값의 $depth$를 찾는 식으로구현할 수 있습니다.
문제: CHILDRENDAY
모듈러 연산의 성질을 이용해서 상태 공간을 탐색해봅시다.
BOJ에서도 비슷한 문제가 있습니다. 조금 쉬운 버전이라고 할 수 있겠네요.
문제: HANOI4
그래프 $G$와 $G^R$에서 bfs를 수행하기 쉬울 때, 양방향에서 bfs를 수행하여 수행 시간을 더 빠르게 최적화하는 양방향 bfs를 이용합니다.