[Algorithm] 기수 정렬 (Radix Sort) Comparison Sort의 문제 해결. Radix Sort 데이터를 구성하는 기본 요소(Radix)를 이용하여 정렬. 입력 데이터의 최댓값에 따라 Counting Sort 대신 사용 가능. 자릿수 기준이므로 나올 수 있는 최대 사이즈는 9(0~9). ...

[Algorithm] 계수 정렬 (Counting Sort) n개의 원소 배열을 정렬하는 가짓수는 n! 해당 방법으로 만든 트리의 말단 노드가 n! 이상이 되기 위해선 2^h >= n!을 만족하는 h를 가지고 h > O(nlogn)을 만족.(h는 트리의 높이) O(nlogn)을 줄일 수 있는 방법은 Comparison을 하...

[Algorithm] 에라토크테네스의 체 에라토크테네스의 체. 소수를 찾는 방법. 체로 수를 거르는 것 같다 하여 이런 이름이 붙었다. 방법 1~n까지 숫자 중 소수를 찾는다고 하자. 숫자를 쭉 쓰고 1을 제거한다. 2를 제외한 2의 배수 제거 3을 제외한 3의 배수 제거 … 소수인 m(m < sqr...

[Algorithm] 순열과 조합 순열과 조합. 아래에 나오는 n은 전체 집합 요소의 개수, r은 해당 부분 집합의 길이를 의미한다. Permutation (순열, nPr) 순서를 정해서 부분 집합을 만드는 방법. 즉, 같은 요소들로 차있더라도 순서가 다르다면 다른 것으로 인식한다. 총 부분 집합의 개수는 아래와 같이 계산할 수...

[Algorithm] LRU Cache Latest Recently Used Cache Cache 데이터나 값을 미리 복사해 놓은 임시 장소. 접근 시간에 비해 원래 데이터를 접근하는 시간이 오래 걸리는 경우나 값을 다시 계산하는 시간을 절약하는 경우 사용. 미리 데이터를 복사해 놓으면 계산이나 접근 시간 없이 빠르게 데이터에 ...

[Algorithm] 최장 증가 수열 (LIS) 최장 증가 수열 ex) [7, 2, 3, 8, 4, 5] > [2, 3, 4, 5]가 가장 길게 증가하는 수열이다. 시간 복잡도 DP : O(n^2) Lower Bound : O(nlogn) 즉, n이 크다면 Lower Bound를 활용하는 것이 좋다! ...

[Algorithm] 최소 공통 조상 (LCA) 트리 형식에서 최소의 공통 조상을 찾는 알고리즘. 두 정점이 만나는 최소 부모 정점을 찾는다. 구현 내용 lowestCommonAncestor(int[] arr, int child_a, int child_b) arrLen = arr.len, nodeAIdx = index of node...

[Algorithm] 최대 공약수와 최소 공배수 (GCD and LCM) 최대공약수, 최소공배수 GCD (Greatest Common Divisor) 두 자연수의 공통된 약수 중 가장 큰 수. LCM (Least Common Multiple) 두 자연수의 공통된 배수 중 가장 작은 수. 유클리드 호제법 (Euclid...

[Algorithm] 동적 계획법 (Dynamic Programming) 다익스트라 알고리즘. DP를 활용한 최단 경로 탐색 알고리즘. 한 번 최단 거리를 구하면 다시 구할 필요가 없으므로 DP를 활용할 수 있다! 아래의 두 정보가 필요하다. 최단 거리 정점 방문 여부 알아야 할 점 ...

[Algorithm] 다익스트라 (Dijkstra) 다익스트라 알고리즘. DP를 활용한 최단 경로 탐색 알고리즘. 한 번 최단 거리를 구하면 다시 구할 필요가 없으므로 DP를 활용할 수 있다! 아래의 두 정보가 필요하다. 최단 거리 정점 방문 여부 알아야 할 점 인접 행렬로 구현하...