오늘은 크루스칼 알고리즘에 대해 정리해보겠습니다. 크루스칼 알고리즘은 최소스패닝 트리를 구하는 알고리즘으로 이전 포스팅을 보시면 이해하시기 수월하십니다. 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 배열은 인덱스가 반대입니다. 그림으로 설명드리겠습니..

문제 링크 : https://www.acmicpc.net/problem/15683 백트래킹 문제였습니다. CCTV 클래스를 만들기. CCTV는 위치정보와 CCTV타입을 가지고 있음. cctvList를 만들어 CCTV들을 저장 경우의 수를 모두 구해 사각지대 최솟값 도출 문제풀이 초기 설정을 위와 같이 잡고 문제를 풀었습니다. 코드가 상당히 길게 나왔는데 문제의 핵심은 dfs메서드의 이 부분입니다. CCTV now = cctvList.get(depth); // cctv의 타입에 따라 switch (now.type) { case 1: // dir은 방향, 1번 유형은 4개의 경우의 수 for (int dir = 0; dir < 4; dir++) { // map의 정보를 copy에 복사해놓고 copy(map,..

문제 링크 : https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 골드 문제 치고 간단한 BFS 문제였습니다. 1. R, G, B로 나누어져 있을때의 덩어리 갯수(cnt)를 구하기 2. G -> R로 변경하여 R과 B로 나누어졌을때 덩어리갯수(cntRG) 구하기 문제풀이 초기 설정을 위와 같이 잡고 문제를 풀었습니다. 핵심이 되는 bfs는 초기 시작점인 Point p와 bfs중 방문하는 nr, nc의 map 값이 같을때만 진행하도록 하였습니..