TreeSet 미친 클래스인데 왜 이때까지 안씀? 이새끼는 HashSet과 마찬가지로 중복된 오브젝트를 제거해 줄 수 있다. 근데 미친게 정렬을 자동으로 해준다.(대신 IO에 시간이 많이 든다) 게다가 tailSet() 이나 headSet()이라는 메서드가 TreeSet 인스턴스의 부분집합을 리턴해줄 수 도 있다. 예를 들면 이렇다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.TreeSet; public class Main { public static void main(String[] args..

유니온 파인드에서 항상 놓치는 부분은 연결하는 두 노드가 주어질 때 두 노드의 루트 노드가 같지 않다면 한쪽 노드의 루트노드의 루트노드를 다른 루트노드로 만들어야 된다는 점이다. 이걸 잊고 한쪽 노드의 루트노드만 다른 루트노드로 바꾸게 되면 그 한쪽노드에서 루트노드로 이어지는 다른 노드들이 다른쪽 루트노드를 가르키지 못하게 된다 그림으로 표현하면 아래와 같다. 초기 상황이다. 4번노드가 3번노드와 이어저 4번노드의 루트 노드가 3이되었다. 2번노드와 3번노드가 이어져 3번노드의 루트노드가 2가되었다. 여기서 4번노드는 고려할 필요가 없다. 3번노드에서 루트로 올라가는 함수를 거칠때 3번노드의 루트노드가 이미 3번이었기 때문에 재귀가 끝나기 때문이다. 이 과정이 유니온 파인드의 핵심이다. 2-3-4의 꼬리..

다익스트라 문제를 풀다가 크루스칼과 혼동이 와서 둘의 차이가 무엇인지 고찰해 봤다. 둘다 한 노드에서 출발하여 Priority Queue를 사용해서 다음 간선을 찾는 방식이라 혼동이 올 수있는데 그림에서 보듯이 두 알고리즘이 요구하는 그래프도 다르고 리턴하는 타입도 다르기 때문에 차이가 있다. 다만 그래프를 실제로 만들 필요는 없고 개념적으로만 존재한다고 생각하고 풀어야한다. 극단적인 그림을 그려 볼까? 이것처럼 다익스트라는 크루스칼이라면 절대 쓰지 않을 간선을 사용하기도 한다. 왜냐하면 다익스트라는 X에서 얼마나 가깝냐가 PriorityQueue의 정렬기준이고 크루스칼은 직전 단계에 만들어진 그래프의 노드들에 연결된 간선중 가장 가중치가 작은 간선을 선택하기 때문 그럼 다익스트라가 생각하는 Priori..

이분 탐색은 다음과 같은 구조로 되어있다. 1. left = 처음 값 2. right = 마지막 값 3. 반복문의 시작 if (left 와 right가 차이가 없으면) break mid = (left + right) / 2 if 용의 선상이 mid 아래면 right = mid if 용의 선상이 mid 위면 left = mid 여기서 생각해야 될 것은 두개 뿐이라는 것을 알 수 있다. 1. 이분 탐색은 선형 자료구조에서 '하나'의 값을 선택하기 위한 알고리즘이라는 것을 염두에 두면 'left 와 right가 차이가 없으면' => 이부분은 left + 1 == right 이때 while문이 멈추도록 코딩해야 한다는 것이다. 즉 while문의 조건은 항상 while(left + 1 < right) 이여야 한다..