힙 힙정렬을 이해하기 전에 힙에 대한 이해가 필요하다. 힙을 이해하기 위해선 다음 포스트를 확인해보자. https://ybdeveloper.tistory.com/132 힙 정렬이란? Max Heap, Min Heap을 구성해 정렬하는 방법이다. 내림차순 정렬을 위해서는 Max Heap, 오름차순 정렬을 위해서는 Min Heap을 구성하면 된다. 즉, 데이터들을 Max Heap이나 Min Heap 형태로 유지한 채 루트 노드의 데이터를 뽑아내 정렬을 하는 방식이다. 힙 정렬 구현 (내림차순) 1. n개의 데이터에 대해 반복한다. O(n) 1-1. 배열에 데이터를 삽입하며 Max-Heap 특성을 만족하도록 조정한다. O(lgn) 2. Max-Heap에 데이터가 존재하지 않을 때 까지 데이터를 뽑아낸다. O(..

다익스트라 알고리즘이 뭘까? 다익스트라 알고리즘이란 하나의 출발점에서 도달할 수 있는 모든 도착점에 대한 최단 경로를 구할 수 있는 알고리즘이다. 대신 조건이 있는데 다익스트라 알고리즘은 간선들의 비용이 모두 양수여야만 적용이 가능하다. 만약 음의 비용을 가진 간선이 존재한다면 최단 경로를 구할 수 없다. 다익스트라 알고리즘과 다이나믹 프로그래밍 다익스트라 알고리즘의 메인 아이디어는 다이나믹 프로그래밍(DP)이다. 다익스트라 알고리즘은 기존에 구해놓은 최단 거리를 이용하여 최단 거리를 갱신해나가는 메인 아이디어를 가지고 있다. (최단 경로는 최단 경로들의 집합으로 이루어져 있다) 다익스트라 알고리즘의 복잡도 (좀 더 자세히 알아볼 것) 원래 다익스트라 알고리즘은 O(V^2)의 시간 복잡도를 가지고 있었지..

기수 정렬이란? 낮은 자리수부터 비교하여 정렬해가는 알고리즘이며 비교 연산이 불필요한 정렬이다. 자릿수에 해당되는 값에 따라 버킷에 데이터들을 삽입하기 때문에 비교 연산이 불필요하지만 자릿수만큼의 추가적인 메모리 공간이 필요하다. (또한 자릿수만큼의 추가적인 로직도 필요하다) 자릿수가 비정상적으로 큰 데이터가 존재한다면 쓸데없는 메모리의 크기를 차지하게 된다. 구현과 시간 복잡도 자바를 이용한 구현 public static void main(String[] args) { RadixSort radixSort = new RadixSort(); for(int i=0; i

최대 공약수 구하기 유클리드 알고리즘이란? 최대 공약수(GCD)를 구할 수 있는 알고리즘으로, gcd(a,b)와 (r=a%b라고 할 때), gcd(b,r)의 최대 공약수는 같다. 즉, gcd(a,b) == gcd(b,r)이다. 이 성질에 따라 gcd(a,b) == gcd(b, a%b) == gcd(a%b, (a%b)%b).... 반복하여 나머지가 0이 되었을 때 나뉘어지는 수가 a와 b의 최대공약수가 된다. 정리하자면 gcd(a,b) -> cdg(a, a%b) .... -> gcd(x, 0)이면 a와 b의 최대 공약수는 x이다. 구현 private static int gcd(int a, int b) { if(b == 0) return a; return gcd(b, a%b); } 최소 공배수를 구하는 방법..

LCA(Lowest Common Ancestor) 알고리즘이란? 두 개의 노드의 가장 가까운 공통된 부모를 찾는 알고리즘을 말한다. 어떻게 찾을 수 있을까? 위의 트리에서 9와 13의 공통 부모는 둘의 바로 위에 있는 2이다. 물론 9와 13과 같이 같은 Level에 있는 노드인 경우에 두 노드의 Level을 동시에 하나씩 줄여가며 찾을 수 있겠지만 만약 서로 다른 Level에 있는 경우 동시에 거슬러 올라간다 한들 공통 부모를 찾을 수 없다. 따라서 Level이 다른 경우에는 하나의 노드를 거슬러 올라가도록 하여 같은 Level로 맞춰줘야만 한다. 정리하자면, 더 깊은 Level에 있는 노드의 Level을 줄여 얕은 Level에 있는 노드와 동일하게 맞춰줘야 한다. Level과 부모 노드 구하기 우선 ..