백준 검색 결과
248 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 15681번: 트리와 쿼리 (Python)

힌트 더보기 접근 문제에 주어진 힌트에 문제를 풀기 위한 간략한 트리에 대한 설명이 나온다. 어찌보면 간단한 내용이지만 이제 배워가는 나에게는 큰 도움이 된 것 같다. 문제 풀이에 도움이 되는 힌트의 핵심은 트리의 정점이 가진 서브트리의 갯수를 저장해주라는 것이다. 루트를 시작으로 하여 서브트리가 계속 아래로 연결되어 확장되는 식이기 때문에 BFS보다는 DFS 알고리즘을 이용하는 것이 직관적으로 풀 수 있는 방법이었던 것 같다. DFS 함수를 만들고 루트를 시작으로 루트에서 이어진 자식 노드들을 탐색하여 자식 노드들이 가진 서브트리 정점의 갯수를 더해서 저장해준다. 그 과정에서 자식 노드들이 가진 서브트리의 갯수가 필요한데, 이 것을 재귀적으로 반복하여 결과적으로는 가장 깊은 곳에 있는 노드들의 서브트리..

2021. 5. 5. 16:43
코딩/백준 (Python)

백준 17472번: 다리 만들기 2 (Python)

접근 결론적으로는 최소 신장 트리, MST 알고리즘을 이용하여 푸는 문제가 맞지만, 그 전에 그 다리들을 처리하는 것이 굉장히 까다롭게 느껴졌던 문제이다. 단계별을 풀면서 MST 알고리즘을 몇가지 풀어봤으면, 이 문제는 MST 알고리즘을 적용하는 것이 아닌 그 전에 처리하는 것이 어려웠던 문제였던 것 같다. MST 알고리즘 설명: 2021.05.02 - [코딩/백준 (Python)] - 백준 1197번: 최소 스패닝 트리 (Python) 백준 1197번: 최소 스패닝 트리 (Python) 접근 이번 기회를 통해 최소 신장 트리(MST, Minimum Spanning Tree) 알고리즘에 대해 공부하였다. Spanning Tree란 그래프 내의 모든 정점을 포함하는 트리로써 그래프의 최소 연결 부분 그래프..

2021. 5. 4. 23:19
코딩/백준 (Python)

백준 2887번: 행성 터널 (Python)

접근 Kruskal MST 알고리즘을 통해 문제를 해결할 수 있다. MST 알고리즘 설명: 2021.05.02 - [코딩/백준 (Python)] - 백준 1197번: 최소 스패닝 트리 (Python) 백준 1197번: 최소 스패닝 트리 (Python) 접근 이번 기회를 통해 최소 신장 트리(MST, Minimum Spanning Tree) 알고리즘에 대해 공부하였다. Spanning Tree란 그래프 내의 모든 정점을 포함하는 트리로써 그래프의 최소 연결 부분 그래프이다. n 개의 ca.ramel.be 이전 4386번 별자리 만들기 문제와 매우 유사해보인다. 하지만 포인트는 주어진 N, 즉 행성의 숫자가 매우 크다는 것이다. 주어진 수의 행성에 대해서 (별자리 만들기에서와 같이) 행성간의 모든 간선을 고..

2021. 5. 3. 01:13
코딩/백준 (Python)

백준 1774번: 우주신과의 교감 (Python)

접근 최소 스패닝 트리(MST) 해결 방법 중 Kruskal MST 알고리즘을 이용하여 문제를 해결하였다. MST 알고리즘 설명: 2021.05.02 - [코딩/백준 (Python)] - 백준 1197번: 최소 스패닝 트리 (Python) 백준 1197번: 최소 스패닝 트리 (Python) 접근 이번 기회를 통해 최소 신장 트리(MST, Minimum Spanning Tree) 알고리즘에 대해 공부하였다. Spanning Tree란 그래프 내의 모든 정점을 포함하는 트리로써 그래프의 최소 연결 부분 그래프이다. n 개의 ca.ramel.be 제대로 구현한 것 같은데 인덱스 에러가 계속 떠서 오래 고민했는데 역시 문제를 열심히 봐야겠다는 생각이 들었다. m개의 이미 연결된 간선이 주어질 때 싸이클을 이루는..

2021. 5. 2. 19:32
코딩/백준 (Python)

백준 4386번: 별자리 만들기 (Python)

접근 별들 간의 거리를 가중치라고 두고 이 간선들을 모두 저장하여 kruskal MST 알고리즘을 이용하여 해결하였다. MST 알고리즘 설명: 2021.05.02 - [코딩/백준 (Python)] - 백준 1197번: 최소 스패닝 트리 (Python) 백준 1197번: 최소 스패닝 트리 (Python) 접근 이번 기회를 통해 최소 신장 트리(MST, Minimum Spanning Tree) 알고리즘에 대해 공부하였다. Spanning Tree란 그래프 내의 모든 정점을 포함하는 트리로써 그래프의 최소 연결 부분 그래프이다. n 개의 ca.ramel.be 처음에 별들이 주어지고, 별들을 순환하면서 각각 거리를 측정하여 [거리, 별1, 별2] 의 형식으로 저장해주었다. 거리 관련하여 이런식으로 모두 구하는 ..

2021. 5. 2. 17:45
코딩/백준 (Python)

백준 1197번: 최소 스패닝 트리 (Python)

접근 이번 기회를 통해 최소 신장 트리(MST, Minimum Spanning Tree) 알고리즘에 대해 공부하였다. Spanning Tree란 그래프 내의 모든 정점을 포함하는 트리로써 그래프의 최소 연결 부분 그래프이다. n 개의 정점을 가지는 그래프의 최소 연결 간선의 개수는 n - 1 개이다. 그 중 Minimum Spanning Tree란 그래프의 간선이 가중치를 가지고 있을 때, Spanning Tree 중 그 가중치의 합이 가장 작은 트리를 의미한다. 이 MST를 구하는 알고리즘은 Kruskal 알고리즘과 Prim 알고리즘 두가지가 있다. Kruskal MST 알고리즘 kruskal 알고리즘은 탐욕적인 방법(Greedy method)를 이용하여 정점을 연결하는 가중치의 최소 값을 구하는 방법..

2021. 5. 2. 16:48
반응형