2021 하계 모각코 5주차 목표와 회고

01 Aug 2021

Reading time ~1 minute

5주차 (08월 01일)

목표

알고리즘 < 최소 신장 트리 > 문제풀기 (백준 9372번, 백준 1197번, 백준 4386번)

회고

알고리즘 < 최소 신장 트리 > 문제 : 백준 9372번(“상근이의 여행”) -> 난이도 : 실버4

해결 방법 : 처음에는 크루스칼 알고리즘을 사용하는 문제인줄 알았는데, 비용도 없고 모든 국가는 항상 연결 되어있다는 조건이 있어서 가장 적은 종류의 비행기를 타고 이동하는 방법은 (국가의수 - 1)이다.(그래프에서 모든 정점이 이어지기 위한 간선의 최소 개수는 (v-1)개이다.)

코드일부

T = int(input())

for _ in range(T):
    N, M = map(int, input().split())
    for i in range(M):
        a, b = map(int, sys.stdin.readline().split())
    print(N-1)

알고리즘 < 최소 신장 트리 > 문제 : 백준 1197번(“최소 스패닝 트리”) -> 난이도 : 골드4

해결 방법 : 최소 스패닝 트리를 구하는 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있는데, 크루스칼 알고리즘을 사용해서 최소 비용을 구했다.

코드일부

cost = 0
for edge in edges:
    weight, a, b = edge
    if find(a) == find(b):
        continue
    else:
        union(a, b)
        cost += weight

print(cost)

알고리즘 < 최소 신장 트리 > 문제 : 백준 4386번(“별자리 만들기”) -> 난이도 : 골드4

풀다가 시간이 부족해서 해결하지 못했다. 다음주 모각코 전까지 풀어와야겠다.

2021 하계 모각코