분류 전체보기 검색 결과
281 개의 검색 결과가 있습니다.
코딩/백준 (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
코딩/백준 (Python)

백준 9372번: 상근이의 여행 (Python)

접근 처음 문제를 보자마자 답은 n - 1 인 것을 알았다. 그래도 탐색을 통해 답을 구하는 방법이 없을까 고민하여 BFS 알고리즘을 이용하여 풀게 되었다. BFS 알고리즘을 통해 순환하면서 새로운 경로를 통해 새로운 정점을 만나면 카운트해주는 방법이다. 코드 import sys def bfs(x): q = [x] visited[x] = 1 cnt = 0 while q: now = q.pop(0) for nx in air[now]: if visited[nx] == 0: visited[nx] = 1 cnt += 1 q.append(nx) return cnt for _ in range(int(sys.stdin.readline())): n, m = map(int, sys.stdin.readline().spli..

2021. 5. 2. 02:03
코딩/백준 (Python)

백준 20040번: 사이클 게임 (Python)

접근 이번 문제에서는 유니온파인드 알고리즘을 이용하여 풀 수 있다. 유니온파인드 알고리즘 설명: 2021.05.01 - [코딩/백준 (Python)] - 백준 1717번: 집합의 표현 (Python) 백준 1717번: 집합의 표현 (Python) 접근 파인드유니온 알고리즘을 모르지만 일단 구현되게 하여 풀기는 하였다. 하지만 파인드유니온 알고리즘을 처음 접했으니 제대로 공부하고 최적화 방법도 알아보고 코드를 다시 작성해보았 ca.ramel.be 유니온파인드 알고리즘을 수행하면서 i 번째 단계에서 주어진 두개의 수의 루트 노드가 같으면 싸이클이 이루어지므로 i를 출력해주고 연산을 마친다. 코드 import sys def find(x): if connect[x] < 0: return x p = find(co..

2021. 5. 2. 01:18
코딩/백준 (Python)

백준 4195번: 친구 네트워크 (Python)

접근 유니온파인드 알고리즘을 이용하여 풀 수 있다. 유니온파인드 알고리즘 설명: 2021.05.01 - [코딩/백준 (Python)] - 백준 1717번: 집합의 표현 (Python) 백준 1717번: 집합의 표현 (Python) 접근 파인드유니온 알고리즘을 모르지만 일단 구현되게 하여 풀기는 하였다. 하지만 파인드유니온 알고리즘을 처음 접했으니 제대로 공부하고 최적화 방법도 알아보고 코드를 다시 작성해보았 ca.ramel.be 여기서는 weighted union find를 사용하지 않고 대신 문자형을 받을 수 있는 dictionary를 두개 사용하여 문제를 해결하였다. 기존 리스트들의 역할을 하는 딕셔너리와 집합의 크기를 나타내는 딕셔너리를 각각 이용했다. 코드 import sys def find(x)..

2021. 5. 1. 22:47
반응형