분류 전체보기 검색 결과
278 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 3977번: 축구 전술 (Python)

접근 이전 문제와 마찬가지로 SCC 문제로 분류되어 있기는 하지만 위상 정렬이 더 큰 비중을 차지하는 문제였다. SCC 를 먼저 탐색하여 SCC 에 속하는 위치들끼리는 하나의 노드처럼 생각하고 위상정렬에서와 같이 진입점(indegree)가 0 인 노드 혹은 SCC 를 찾는 문제이다. 이전 문제와 동일하게 풀되, 다른 점은 이전 도미노 문제에서는 시작점의 최소 개수만 체크했다면, 이번 문제에서는 시작점이 될 수 있는 요소들을 찾고 만약 그 시작점이 여러개거나 없다면 선수가 시작점을 헷갈릴 수 있기 때문에 Confused 를 출력해주면 된다. 즉, indegree 가 0 인 노드가 1개 있다: 해당 노드를 출력 indegree 가 0 인 SCC 가 1개 있다: 해당 SCC 에 속하는 노드들을 오름차순으로 출..

2021. 7. 11. 18:37
코딩/백준 (Python)

백준 4196번: 도미노 (Python)

접근 처음엔 왜 이것이 SCC 문제인가 고민을 했었다. 가장 기본적으로는 도미노의 시작점을 찾아야 하기 때문에 위상 정렬을 쓰는 것이 맞고, 추가적으로 그 사이에 SCC 를 이루는 노드들이 있을 경우 이 한덩이의 SCC 를 한개의 노드 취급을 해서 계산을 하면 옳게 풀 수 있다. 특히 SCC 를 적용하지 않을 경우 원형의 싸이클을 이루는 하나의 SCC 의 예를 들었을 때, 일반적으로 위상 정렬에 쓰는 indegree 값이 0 인 노드가 존재하지 않을 수 있다. 또한 같은 이유로 indegree 가 0 인 노드 수와 도미노 시작점의 수가 일치하지 않을 것이다. 결론적으로 풀이 방법을 보면, 전체 그래프에서 SCC 를 구한다. SCC 들을 기준으로 진입점인 indegree 를 계산해주고, indegree 값..

2021. 7. 11. 00:09
코딩/백준 (Python)

백준 2150번: Strongly Connected Component (Python)

Strongly Connected Component(SCC) 문제를 푸는 방법에는 크게 Kosaraju 알고리즘과 Tarjan 알고리즘이 있다. 두가지 알고리즘으로 푸는데 매우 헤매었기 때문에 시간을 조금 들여서라도 두가지 모두 정리하고 코드를 자세하게 주석을 달아 설명해두고 넘어가려고 한다. 접근 (Kosaraju) 코사라주 알고리즘을 수행하기 위해서는 먼저 문제에 주어진 정방향 그래프와, 각 그래프의 방향이 정반대인 역방향 그래프 두가지를 준비해야한다. 먼저 정방향 그래프를 이용하여 모든 그래프 상에서 dfs 탐색을 수행하고, dfs 탐색이 종료되는 순서대로 stack에 append 해준다. 이후 해당 stack에서 요소들을 한개씩 pop하여 순서대로 역방향 dfs를 수행하고, 한번 수행에 탐색되는 ..

2021. 7. 10. 18:06
코딩/백준 (Python)

백준 13511번: 트리와 쿼리 2 (Python)

접근 이전에 풀었던 도로 네트워크 문제와 유사한 문제였다. 오히려 조금 더 간단했던 것 같다. 도로 네트워크 문제에서 거리 저장 개념을 가져오고, k 번째 노드를 구하는 것도 LCA 구하는 것과 마찬가지로 탐색하면 된다. 물론 문제에서 요구하는 것이 많아서 코드는 훨씬 길어지게 되었다. 2021.07.02 - [코딩/백준 (Python)] - 백준 3176번: 도로 네트워크 (Python, PyPy3) 백준 3176번: 도로 네트워크 (Python, PyPy3) 접근 바로 이전에 풀었던 LCA 2 문제와 매우 유사하지만, 이번에는 도로의 길이 및 최대 거리, 최소 거리가 추가된 문제였다. 최소공통조상 문제와 동일하게 풀게 되면, 두 도시 사이는 최소공통 ca.ramel.be 기존 문제와 마찬가지로 모든 ..

2021. 7. 3. 18:57
코딩/백준 (Python)

백준 3176번: 도로 네트워크 (Python, PyPy3)

접근 바로 이전에 풀었던 LCA 2 문제와 매우 유사하지만, 이번에는 도로의 길이 및 최대 거리, 최소 거리가 추가된 문제였다. 최소공통조상 문제와 동일하게 풀게 되면, 두 도시 사이는 최소공통조상 도시를 거쳐 연결되게 된다. 최소공통조상 알고리즘 LCA 문제: 2021.06.29 - [코딩/백준 (Python)] - 백준 11438번: LCA 2 (Python, PyPy3) 백준 11438번: LCA 2 (Python, PyPy3) 접근 이번 문제는 최소공통조상을 구하는데 Sparse Table(희소 테이블)을 이용하는 문제였다. LCA 알고리즘 개념: 2021.06.27 - [코딩/백준 (Python)] - 백준 3584번: 가장 가까운 공통 조상 (Python) 백준 3584.. ca.ramel.b..

2021. 7. 2. 00:21
코딩/백준 (Python)

백준 11438번: LCA 2 (Python, PyPy3)

접근 이번 문제는 최소공통조상을 구하는데 Sparse Table(희소 테이블)을 이용하는 문제였다. LCA 알고리즘 개념: 2021.06.27 - [코딩/백준 (Python)] - 백준 3584번: 가장 가까운 공통 조상 (Python) 백준 3584번: 가장 가까운 공통 조상 (Python) 접근 문제에 있는 설명과 같이 가장 가까운 공통 조상 (LCA, lowest common ancestor) 알고리즘을 이용하여 풀 수 있다. 주어진 트리들을 이용하여 부모를 구할 수 있도록 저장해준 후, 마지막으로 비교 ca.ramel.be 희소 테이블 기본 문제: 2021.06.27 - [코딩/백준 (Python)] - 백준 17435번: 합성함수와 쿼리 (Python) 백준 17435번: 합성함수와 쿼리 (Py..

2021. 6. 29. 23:39
반응형