★
-
[알고리즘] MST (최소 신장 트리, Minimum Spanning Tree)STUDY/ALGO | DS 2021. 8. 14. 21:18
MST (최소 신장 트리, Minimum Spanning Tree) 1. MST 그래프의 모든 정점을 연결할 때, 모든 정점을 간선으로 연결하며 싸이클은 존재하지 않고, 연결된 간선들의 가중치의 합은 최소가 되는 것을 말한다. +) Spanning Tree : 그래프 내 모든 정점을 포함하는 트리 +) 정점 : V , 간선 : E 2. Kruskal's Algorithm | 크루스칼 알고리즘 - 간선 선택 기반 - 시간복잡도 : O(ElogV) ㄴ 간선 정렬 : O(ElogE) ㄴ Unifon Find : O(1) * E = O(E) O(ElogE + E) => O(ElogV^2), (E O(ElogV) 1) 간선 리스트의 가중치들을 오름차순으로 정렬 2) 가중치가 작은 간선 선택 3) union-fin..
-
[프로그래머스] 섬 연결하기ALGORITHM/PROGRAMMERS 2021. 8. 14. 21:15
https://programmers.co.kr/learn/courses/30/lessons/42861# 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 2021-08-14 MST 알고리즘 1. 크루스칼 알고리즘 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 import java.util.*; class Solution { static int[] parent; static int find(int x) { if(x == parent[x..
-
[알고리즘] Union-Find (유니온 파인드)STUDY/ALGO | DS 2021. 8. 14. 19:43
Union-Find (유니온 파인드) 1. Union-Find - 합집합 찾기 알고리즘 - Disjoint-Set, 서로소 집합 이라고도 한다. - 2개의 서로 다른 노드(x, y)를 선택했을 때, 2개의 노드가 같은 집합(그래프)에 속하는지 확인하는 알고리즘 2. Union - 서로 다른 2개의 노드 x, y가 포함되어 있는 집합을 합치는 연산 1 2 3 4 int find(int x) { if(x == parent[x]) return x; return parent[x] = find(parent[x]); } Colored by Color Scripter cs 3. Find - 노드 x가 어떤 집합에 포함되어 있는지 체크하는 연산. 루트 노드 반환. 1 2 3 4 5 6 7 void union(int x..
-
[백준] 1717 집합의 표현ALGORITHM/BOJ 2021. 8. 14. 19:42
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 2021-08-14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 import java.io.*; import java.util.*; public class ..
-
[프로그래머스] 이중우선순위큐ALGORITHM/PROGRAMMERS 2021. 8. 11. 13:53
https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 2021-08-11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import java.util.*; class Solution { public int[] solution(String[] operations) { PriorityQueue pq = new PriorityQueue(); for(int i = 0; i x).max().getAsInt()); else pq.poll(); } } } if(pq.size() == 0) return new int[]{0, 0}; return new..
-
[프로그래머스] 등굣길ALGORITHM/PROGRAMMERS 2021. 8. 11. 11:11
https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 2021-08-11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { static int[] dx = {-1, 0}; static int[] dy = {0, -1}; public int solution(int m, int n, int[][] puddles) {..
-
[프로그래머스] 단어 변환ALGORITHM/PROGRAMMERS 2021. 8. 11. 09:48
https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 2021-08-11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 import java.util.*; class Solution { public int solution(String begin..
-
[프로그래머스] 위클리 챌린지 2주차ALGORITHM/PROGRAMMERS 2021. 8. 9. 22:06
https://programmers.co.kr/learn/courses/30/lessons/83201 코딩테스트 연습 - 2주차 [[100,90,98,88,65],[50,45,99,85,77],[47,88,95,80,67],[61,57,100,80,65],[24,90,94,75,65]] "FBABD" [[70,49,90],[68,50,38],[73,31,100]] "CFD" programmers.co.kr 2021-08-09 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public String solution(int[][] scores) { StringBuilder sb = new St..
-
[프로그래머스] 위클리 챌린지 1주차ALGORITHM/PROGRAMMERS 2021. 8. 9. 22:04
https://programmers.co.kr/learn/courses/30/lessons/82612 코딩테스트 연습 - 1주차 새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이 programmers.co.kr 2021-08 1 2 3 4 5 6 class Solution { public long solution(int price, int money, int count) { long answer = (long)money - ((count*(price + ((long)price*count)))/2); return answer
-
[프로그래머스] 예상 대진표ALGORITHM/PROGRAMMERS 2021. 8. 7. 22:04
https://programmers.co.kr/learn/courses/30/lessons/12985 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 2021-08-07 1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int solution(int n, int a, int b) { int answer = 0; while(a != b) { answer++; a = (a + 1) / 2; b = (b + 1) / 2; } return ans..