제 3회 (2 주차) 모각코 결과

    3주차 (3회차) - 최소 스패닝 트리에 대한 이론 및, 백준 응용 문제 풀기 



    1197번: 최소 스패닝 트리 (acmicpc.net)


최소 스패닝 트리란? (최소 신장 트리)

간선에 가중치가 있는 무방향성 그래프가 주어졌을때, 이 그래프에서 가장 적은 가중치로 모든 노드를 가지는 트리를 만드는 문제였다.

처음에는 문제를 이해하지 못해서 고생했다. 하지만 문제를 이해하고 난뒤에는 수월하게 풀렸다.

해당 문제를 푸는 것은 그리디한 방법으로 접근하면 쉽게 풀린다.

간선의 가중치가 적은 것 부터 노드를 이어주는 것이다. 그리고 나중에 가중치가 더 큰 간선으로 이을 려는 두개의 노드가 이미 이어져 있다면, 이을 필요가 없다.

이 과정은 유니온 파인드로 쉽게 할 수 있다.



이런 최소 스패닝 트리는 가중치를 가장 적게, 혹은 가장 크게 그래프에서 트리를 구성해야 한다는 특징만 안다면 쉽게 응용 할 수 있다.

이번 모각코에서 푼 응용문제들이다.










p.s 후에 공부를 더하고 알았는데, 내가 한 방법은 크루코살 알고리즘이라고 한다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

제 6회 (4주차) 모각코 결과

이미지
  제 6회 (4주차)  - 스위핑 알고리즘의 이론적 학습과 구현, 및 백준 응용 문제 풀기 2170번: 선 긋기 (acmicpc.net) 어려운 내용이 아닌 그냥 한번 훑으면서 같은 라인 단위로 만드는 방법이었다. 아직 스위핑 알고리즘이 뭔지 감을 잡지 못하였다. BaekJoon/선 긋기.java at main · Hy3ons/BaekJoon (github.com) 2836번: 수상 택시 (acmicpc.net) 해당 문제는 손님이 뒤로 가는 상황일 경우 역주행을 효율적으로 하는 것을 묻고 있다. 현재 나의 위치에서 내 위치 전으로 역주행 하는 상황이 앞에 안 나올 때, 모든 손님을 역주행 하면서 한번에 도착 지점으로 이동 시키면 가장 효율적 이게 된다. 방법은 아는데 구현을 어떻게 해야 될지 모르겠어, HashMap 과 HashSet을 그냥 남발하듯이 사용했다. 또한 내가 특정 지점에 도착 했는데, 역주행을 앞으로 내 위치 전으로 안해도 되는 상황이라는 것을 특정 하는 것이 어려웠다. BaekJoon/수상 택시.java at main · Hy3ons/BaekJoon (github.com) 후에 다시 개념을 정리하고 풀면서, 스위핑에 대한 이해를 높일 수 있었다. 그림을 보면 뒤로 가야 하는 상황에 대해, 겹치는 선분을 하나로 만들어서 2배하여 더해야 한다. 그럼 뒤로 가는 경우에 대해 선분을 다 만들고, 스위핑 기법을 활용 하면 끝난다. 이렇게 하면 HashMap 과 HashSet을 이용하지 않고, 효율적으로 문제를 풀 수 있다. 공유 소스 보기 (acmicpc.net) 남은 시간에는 오일러 피 함수를 알게 된 김에 폴라드로 알고리즘을 이용하여 푸는 문제를 풀어봤다. 13926번: gcd(n, k) = 1 (acmicpc.net) BaekJoon/gcd（n， k） ＝ 1.py at main · Hy3ons/BaekJoon (github.com) 순간적으로 63 비트를 넘기 때문에, python으로 구현하였다.
자세한 내용 보기

제1회 (1주차) 모각코 목표

1주차 (1회차) - 데이크스트라에 대한 이론 학습 및 코드 구현, 그리고 백준 응용 문제풀기 1504번: 특정한 최단 경로 (acmicpc.net) 데이크 스트라에 대한 이론적인 이해와 함께 단순 데이크 스트라를 이용하여 최단 거리를 구하는 문제가 아닌 그 응용 문제를 풀어 심층적인 이해를 도모 하려 한다. 1 회차가 끝나고 이해한 이론을 쉽게 풀어 쓰려고 한다.
자세한 내용 보기

제1회 (1주차) 모각코 결과

이미지
1주차 (1회차) - 데이크스트라에 대한 이론 학습 및 코드 구현, 그리고 백준 응용 문제풀기 1504번: 특정한 최단 경로 (acmicpc.net) 데이크 스트라란?     한 노드에서 다른 노드에 가중치가 있을 때, 그 가중치의 합이 가장 적은 길을 찾는 알고리즘 이다. 이런 데이크 스트라는 다이나믹 프로그래밍의 일종인데, 한 노드에서 탐색을 시작하여,  다른 노드로 갈 때, 현재의 최단 거리 값에서 다른 노드로 이동하는 거리의 합이 이전에 그 노드를 방문하여 얻은 최단 거리보다 짧은 경우 업데이트를 하여, 지속적으로 업데이트, 탐색하는 알고리즘이다.          해당 특정한 최단 경로 문제는 데이크 스트라를 돌렸을 때, dp배열의 값, 최단 거리가 무엇을 의미하는지 정확하게 묻는 문제라고 할 수 있다.     해당 문제는 양방향 간선이다. 즉, 특정한 노드에서 다른 노드로 가는 최단 거리는 그 반대여도 값이 같다는 것이다. 그리고 또한 모든 노드는 다른 노드로 가는 간선이 존재한다.     문제는 1에서 N 으로 가는 최단 거리는 우리가 거쳐가야 하는 두개의 노드가 포함 되어 있지 않을 수도 있다는 것이다.     그럼 어떻게 해결 해야 할까?     간단히 축약하여 그린 그림이다.     우리 시작 지점 1번노드 에서 거쳐야 하는 두개의 노드까지의 최단 거리를 구할  수 있다. 그리고 거쳐야 하는 두개의 노드를 시작점으로 다익스트라를 돌리게 되면,  해당 노드에서의 다른 노드까지의 모든 최단거리가 나오게 된다. 그러면 우리는 총 5개의 최단거리로 이루어진 간선을 얻게 되고 사용 할 수 있다.      우린 시작점에서 거쳐야 하는 노드 중 하나를 최단 거리를 이용하여 도착했을 때, 다른 거쳐야 하는 노드까지 현재 노드에서 최단거리를 이용하여 그 노드에...
자세한 내용 보기