제민
4월 2주차 정리노트 본문
위상정렬
https://jemin06.tistory.com/152
위상정렬
https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다
jemin06.tistory.com
위상정렬을 배웠다. 위상정렬은 DAG에서만 가능하다는 것을 꼭 기억하자.
Union Find
https://jemin06.tistory.com/155
Union Find
https://m.blog.naver.com/fbfbf1/222278788809 유니온 파인드(Union Find) c++ 유니온 파인드 정의 - 공통 원소가 없는 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하... blog.naver.com 원래 바킹
jemin06.tistory.com
분리집합을 배웠다. 재밌는 알고리즘이었다. find, merge를 통해 쉽게 사이클 여부를 판단할 수 있던게 기억에 남는다.
BFS/DFS
https://jemin06.tistory.com/156
14395 4연산
https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전
jemin06.tistory.com
BFS로 최단 거리를 찾는다.
나는 경로를 역추적해서 부호를 가져와야하나 걱정했는데 그냥 큐에 인자로 받으면 됐다.
https://jemin06.tistory.com/157
1194 달이 차오른다, 가자
https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의
jemin06.tistory.com
비트마스킹을 곁들인 BFS 문제였다.
다음주에는 주로 유니온 파인드를 이용해 문제들을 풀 것 같다.
스택을 배울 때부터 건드리지 못하고 놔둔 두 히스토그램 문제랑 MST 최소 스패닝 트리를 풀 것이다.
또, 위상정렬 문제 중 3665 최종 순위 문제가 있는데 이걸 풀 것이다.
https://www.acmicpc.net/problem/3665
3665번: 최종 순위
올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에
www.acmicpc.net
'주별 개인평가' 카테고리의 다른 글
| 4월 1주차 정리노트 (2) | 2024.04.07 |
|---|---|
| 3월 3,4주차 정리노트 (0) | 2024.03.31 |
| 3월 2주차 정리노트 (0) | 2024.03.17 |
| 3월 1주차 정리노트 (0) | 2024.03.09 |
