다시 사용될 수 있는 아이디어나 발상들을 따로 정리해둔 글이다.
1. 백준 16437번 (https://viyoung.tistory.com/343)
- 그래프 상에서 두 정점 사이에 유일한 경로가 있다는 의미는 트리 구조라는 의미이다. (사이클이 존재하지 않는다.)
2. 백준 4803번 (https://viyoung.tistory.com/341)
- 그래프 상에서 트리 구조임을 직접 확인하는 방법. (간선을 추가할 때, 시점과 종점을 바꾼 간선도 추가해줘서 파악)
3. 백준 1967번 (https://viyoung.tistory.com/110)
- 루트로부터 가장 멀리 있는 정점을 아무거나 찾고, 그 정점으로부터 가장 먼 정점과의 거리가 트리의 지름이다.
(증명 : https://m.blog.naver.com/kks227/220788265724)
4. 백준 1354번 (https://viyoung.tistory.com/278)
- DP에서 저장해야하는 값의 범위가 크지만 그 수가 적은 경우에는 set을 사용할 수도 있다. (DP + Set)
5. 백준 1327번 (https://viyoung.tistory.com/349)
- visited 배열을 쓸 때 필요한 것보다 공간을 훨씬 더 많이 잡아야할 경우, set 자료구조를 활용하는 것이 효율적일 수도 있다.
(4번과 완전히 비슷한 맥락이다.)
6. 백준 2098번 (https://viyoung.tistory.com/348)
- visited를 비트마스킹을 활용해서 처리할 수 있다. (다만, 이 경우에는 정점이 매우 작아야 한다.)
7. 백준 1102번 (https://viyoung.tistory.com/357)
- 비트마스크를 사용할 때, 집합 안에 몇 개의 원소가 있는지 파악하기 위해서는 __builtin_popcount() 함수를 사용해주면 된다.
8. 백준 1194번(https://viyoung.tistory.com/360), 백준 2206번(https://viyoung.tistory.com/334), 백준 14442번(https://viyoung.tistory.com/335), 백준 2001번(https://viyoung.tistory.com/361),
- Visited 배열을 관리할 때, 같은 장소라고 해도 의미가 다른 경우에는 차원을 늘려서 동일한 의미에서 방문할 때만 방문처리를 해야한다.
9. 백준 1504번(https://viyoung.tistory.com/364)
- 최단경로의 길이를 구하는 과정에서 특정한 정점을 반드시 거쳐야하면서 중복된 정점과 간선을 지날 수 있으면, 다익스트라를 찢어서 구할 수 있다.
10. 백준 1854번(https://viyoung.tistory.com/368)
- 다익스트라에서 탐색 도중에 의도적으로 최단 경로가 아닌 경우를 배제하는 양상에 대해서 정확하게 이해해야 한다.
11. 백준 13907번(https://viyoung.tistory.com/369), 백준 1162번(https://viyoung.tistory.com/365), 백준 15422번(https://viyoung.tistory.com/367), 백준 10217번(https://viyoung.tistory.com/380), 백준 13308번(https://viyoung.tistory.com/390)
- 다익스트라 + DP, 의미가 갈라지는 부분에 대해서 따로 차원을 잡아줘서 처리해주면 된다.
12. 백준 5719번(https://viyoung.tistory.com/376)
- 다익스트라에서 최단 경로를 모두 구하기 위해서는 parent를 배열이 아니라 vector로 잡으면 된다. 갱신될때마다 parent 벡터를 초기화시키고, 만약 같은 값이 나올 경우에는 pq에 갱신을 하지 않고 parent vector에 원소만 추가한다.
13. 백준 1182번(https://viyoung.tistory.com/379)
- 순열을 통해 나올 수 있는 모든 케이스를 검토해야하는데, n이 작은 경우에는 비트마스킹을 활용해줄 수 있다. 단순 순열의 경우는 2진법을 활용해주면 되고, 중복 순열의 경우에는 k진법을 활용해주면 된다. (참고 : https://blog.naver.com/jinhan814/222579884777)
14. 백준 18111번(https://viyoung.tistory.com/378)
- 특정한 값을 고정시켜서 문제를 단순화시킬 수 있는 양상에 대해서 잘 기억해두도록 하자. 완전 탐색과 결부되는 경우가 많음.
15. 백준 11779번(https://viyoung.tistory.com/381), 백준 5719번(https://viyoung.tistory.com/376), 백준 2211번(https://viyoung.tistory.com/374)
- 다익스트라에서 parent 배열을 잡아서 최단 경로를 역추적할 수 있다.
16. 백준 2336번(https://viyoung.tistory.com/393)
- 세그먼트 트리를 특정 정보에 대해서 순차적으로 갱신하여, 쿼리에 담긴 여러 개의 정보를 동시에 처리할 수 있다. (세그먼트 트리 + 스위핑) 금광세그와 비슷한 느낌으로 접근해주면 된다.(북서풍 문제 다시 풀기)
17. 백준 9246번(https://viyoung.tistory.com/394), 백준 5419번(https://viyoung.tistory.com/257), 백준 1517번(https://viyoung.tistory.com/395), 백준 7578번(https://viyoung.tistory.com/403)
- 세그먼트 트리 + 스위핑 (특히 9246, 5419의 경우 이차원 세그)
18. 백준 12899번(https://viyoung.tistory.com/396)
- k번째 숫자를 구하기 위한 테크닉(세그먼트 트리 + 이분 탐색)
19. 백준 16975번(https://viyoung.tistory.com/397), 백준 10999번(https://viyoung.tistory.com/398), 백준 12844번(https://viyoung.tistory.com/399), 백준 14268번(https://viyoung.tistory.com/400), 백준 14288번(https://viyoung.tistory.com/401), 백준 16404번(https://viyoung.tistory.com/407), 백준 13925번(https://viyoung.tistory.com/408)
- 구간에 대한 정보를 업데이트 해야하는 경우 Lazy propagation을 생각해주면 된다.
- 정확히 겹치는 부분에 대해서만 처리해주고 나중에 합쳐주는 방식으로도 가능하기는 하다.
20. 백준 14287번(https://viyoung.tistory.com/245), 백준 15899번(https://viyoung.tistory.com/245), 백준 18227번(https://viyoung.tistory.com/261), 백준 14268번(https://viyoung.tistory.com/400), 백준 14288번(https://viyoung.tistory.com/401), 백준 16404번(https://viyoung.tistory.com/407)
- 서브 노드에 대한 정보를 일괄적으로 업데이트 해야하는 경우 오일러 투어 테크닉을 생각해주면 된다.
21. 백준 17353번(https://viyoung.tistory.com/402)
- 세그먼트 트리를 활용하기 위해서는 일관된 계산을 기준으로 처리해야 한다는 점이다. 필요할 경우, 공통된 연산으로 처리하기 위해 정보를 다른 관점에서 바라보아야 할 수 있다.
22. 백준 1395번(https://viyoung.tistory.com/405), 백준 12844번(https://viyoung.tistory.com/399)
- 연산의 특징을 활용해서 Lazy propagation (연산을 반복수행하면 결과적으로 수행하지 않은 것과 같다는 점을 이용한 문제)
23. 백준 13925번(https://viyoung.tistory.com/408)
- ax + b 형태의 lazy propagation
