오늘은 크루스칼 알고리즘에 대해 정리해보겠습니다. 크루스칼 알고리즘은 최소스패닝 트리를 구하는 알고리즘으로 이전 포스팅을 보시면 이해하시기 수월하십니다. 2023.12.26 - [Algorithm] - [알고리즘] 프림 알고리즘(최소신장트리, 최소스패닝트리) [알고리즘] 프림 알고리즘(최소신장트리, 최소스패닝트리) 오늘은 프림 알고리즘에 대해 정리해보겠습니다. 스패닝 트리는 그래프 내의 모든 정점을 연결하지만 사이클이 없는 트리입니다. 밑의 그래프는 예시로 만들어본 그냥 트리입니다. 정점 4개와 6 5g-0.tistory.com 개념 크루스칼 알고리즘은 간선선택을 기반으로 합니다. 간선을 가중치의 오름차순으로 정렬하고 사이클을 형성하지 않을 때 간선을 선택합니다. 정점(노드)의 개수가 N개라고 했을때 간..

오늘은 프림 알고리즘에 대해 정리해보겠습니다. 스패닝 트리는 그래프 내의 모든 정점을 연결하지만 사이클이 없는 트리입니다. 밑의 그래프는 예시로 만들어본 그냥 트리입니다. 정점 4개와 6개의 간선으로 이루어져있습니다. 다음 그래프는 정점 4개와 3개의 간선으로 이루어져있습니다. 최소한의 간선의 갯수로 이루어져 있고 모든 정점이 연결된 스패닝 트리의 형태입니다. 스패닝 트리는 다음과 같이 간선의 갯수가 정점의 갯수 - 1 개라는 특징이 있습니다. 최소 스패닝 트리는 이러한 스패닝 트리 중 사용된 가중치 합이 최소인 트리를 뜻합니다. 스패닝 트리 - 최소한의 간선의 갯수로 이루어져 있고 모든 정점이 연결됨 - 간선의 갯수 = 정점의 갯수 - 1 최소 스패닝 트리 - 스패닝 트리 중 사용된 가중치 합이 최소인..

문제링크 : https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 누적합 문제였습니다. 신경쓸 부분이 참 많았습니다. 1. Ball 클래스(인덱스, 색깔, 크기)를 만들기 2. ArrayList를 만들어 Ball 정보들을 저장. 3. 크기를 기준으로 오름차순 정렬. 문제풀이 초기 설정을 위와 같이 잡고 문제를 풀었습니다. 문제를 보면 크기가 작고, 색이 다른 공만 잡을 수 있습니다. 예제를 보기 쉽게 나타내보면 다음과 같..

문제링크 : https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 이해가 안되서 이것저것 찾아보며 간신히 이해한 문제입니다. 1. 석순(아래), 종유석(위) 두개로 나누어서 배열 만들기 2. 높이별로 카운트를 높여서 누적합 구하기 3. 누적합 한 배열은 인덱스에서 벽을 몇개 부셔야하는지 나타냄 문제풀이 초기 설정을 위와 같이 잡고 문제를 풀었습니다. 석순 = down, 종유석 = up 배열입니다. up 배열은 인덱스가 반대입니다. 그림으로 설명드리겠습니..