분류 전체보기
-
Union-Find(합집합 찾기)란?Computer Science/Algorithm 2020. 1. 23. 22:12
Union-Find 란? union-find 연산은 Kruskal의 알고리즘에서만 사용되는 것은 아니고 일반적으로 널리 사용된다. union(x, y) 연산은 원소 x와 y가 속해있는 집합을 입력으로 받아 2개의 집합의 합집합을 만든다. find(x)연산은 원소 x가 속해있는 집합을 반환한다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 위와 같이 여러 개의 노드가 연결되지 않은 채로 있다고 가정하자. 여기서 union(1, 4)와 union(5, 2)를 하면 아래와 같은 집합으로 변환된다. {1, 4}, {5, 2}, {3}, {6}, {7}, {8} 위와 같이 합쳐지는 것이다. 더 이해가 필요하기 때문에 구체..
-
Kruskal 알고리즘이란?Computer Science/Algorithm 2020. 1. 23. 22:11
Kruskal 알고리즘 Kruskal의 알고리즘은 탐욕적인 방법(greedy method)을 이용한다. 탐욕적인 방법은 알고리즘 설계에서 있어서 중요한 기법 중의 하나이다. 탐욕적인 방법이란 선택할 때마다 그 순간 가장 좋았다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법이다. 탐욕적인 알고리즘에서 순간의 선택은 그 당시에는 최적이다. 하지만 최적이라고 생각했던 지역적인 해답들을 모아서 최종적인 해답을 만들었다고 해서, 그 해답이 반드시 지역적으로 최적이라는 보장은 없다. 하지만 다행히 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. Kruskal의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건에 근거하여, 각 단계..
-
최소 비용 신장트리(MST, Minimum Spanning Tree)란?Computer Science/Algorithm 2020. 1. 23. 19:41
신장트리 신장 트리(spanning tree)란 그래프내의 모든 정점을 포함하는 트리다. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 또한 사이클을 포함해서는 안된다. 따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다. 하나의 그래프에는 많은 신장 트리가 존재 가능하다. 신장 트리는 깊이 우선이나 너비 우선 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 또한 신장트리는 그래프의 최소 연결 부분 그래프가 된다. 여기서 최소의 의미는 간선의 수가 가장 적다는 의미이다. n개의 정점을 가지는 그래프는 최소한 (n-1)개의 간선을 가져야 하며 (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것은 바로 신장 트리가 된..
-
[Java] Generic 개념 및 정리Language/Java 2020. 1. 22. 17:21
Generic 정의 일반적인 코드를 작성하고, 이 코드를 다양한 타입의 객체에 대하여 재사용하는 프로그래밍 기법이다. 타입을 파라미터화해서 컴파일시 구체적인 타입이 결정되도록 하는 것이다. 클래스 내부에서 사용할 데이터 타입을 외부에서 지정하는 기법이다. Generic은 컬렉션, 람다식, 스트림등에서 널리 사용된다. 1 2 3 4 5 6 7 8 9 public class Person { public T info; public static void main(String[] args) { Person p1 = new Person(); Person p2 = new Person(); } } Generic 타입이란? 타입을 파라미터로 가지는 클래스와 인터페이스를 말한다. 선언시 클래스 또는 인터페이스 이름 뒤에 ..
-
백준 2164번 카드2 (Python, Java)Baekjoon 2020. 1. 20. 01:13
https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리 www.acmicpc.net 풀이 : Deque를 쓰지 않고 그냥 풀면 시간초과가 발생한다. 카드1 문제는 아무렇게나 풀어도 맞았는데 이거는 시간초과가 발생하기 때문에..
-
[Java] equals() 해시코드 비교 및 개념 정리Language/Java 2020. 1. 19. 19:50
어떤 백준 알고리즘 문제를 풀다가 문자열 비교해서 같으면 카운트하는 문제가 있었는데 == 을 써도 도저히 먹지 않았다. 왜 안되는지 이해가 안돼서 검색을 해보니 문자열 비교는 equals 를 해야한다고 했다. 그래서 그 차이점을 정리하려고 한다. 들어가기전에 알아보기 equals메소드와 hashCode() 메소드는 모든 클래스의 최상 클래스인 Object의 메소드라는 것을 알아두자. 2. equals 메소드와 == 연산자 가령 new 연산자를 이용하면 힙 영역에 메모리가 할당된다. 하지만 new를 이용하지 않고 그냥 참조변수에 값을 넣어버리면 상수 풀이라는 곳을 가르키기 때문에 위의 사진처럼 str2와 str3는 같은 곳을 가르키게 된다. 1 2 3 4 5 6 7 8 9 10 11 String str1 ..
-
백준 1181번 단어 정렬(Java)Baekjoon 2020. 1. 18. 05:46
https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 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 import java.util.*; public class WordSort{ public static void main(String[] args) { Scanner input = new Scanner(System.in); HashSet set = ne..
-
[Java] Iterable 과 Iterator 이란?Language/Java 2020. 1. 18. 00:02
Collection framework는 뭔가 되게 많고 복잡한 느낌이 들어서 완벽하게 정리가 된 느낌은 아니었다. 가령 Iterator는 어떤 역할인지는 알겠는데 어떤 계층구조를 갖고 있는지 궁금했고, 공부하다보니 Iterable이 있길래 어떤 차이가 있는지도 모르겠어서 정리하려고 한다. 1. Iterable 이란 무엇인가? Collection 인터페이스와 List, Set, Queue 인터페이스의 계층구조는 알고 있었지만, Iterable이 Collection의 상위 인터페이스 인지는 잘 몰랐다. 그래서 인텔리제이에서 내부 구현 코드를 확인해봤다. 1 2 3 4 5 6 7 8 9 10 public interface Collection extends Iterable { // Query Operations..