알고리즘

최단 경로 알고리즘 - JAVA

1. 최단 경로 알고리즘 - 목적지에 이르는 모든 가능한 경로 중 최단 경로를 찾는 알고리즘 - 종류: ①다익스트라 알고리즘 ②벨만-포드 알고리즘 ③모든 쌍 최단 경로 알고리즘 ※ ①② 와 ③의 코딩테스트 제출 차이 - 특정 시작점에서 모든 정점들까지의 최단 경로 구하기 --> 다익스트라, 벨만-포드 - 모든 시작점에서 모든 정점들까지의 최단 경로 구하기 --> 모든 쌍 최단 경로 알고리즘 (대표: 플로이드와샬) ※ 최소 신장 VS 최단 경로 "최소 신장"과 "최단 경로"는 얼핏보면 같은 말 같다. 뭐가 다르길래 굳이 알고리즘을 나누었나 궁금하여 차이점을 간단히 메모해둔다. * 최소 신장 - 모든 정점을 방문하면서 간선의 비용이 합이 최소가 되는 "트리"를 만듦 - ex) 프림 알고리즘, 크루스칼 알고리..

[Java] 에라토스테네스의 체 - 소수 판별

[에라토스테네스의 체] - 가장 대표적인 소수 판별 알고리즘. 소수(Prime)이란 양의 약수를 1과 자기자신만 가지고 있는 자연수. - 대량의 소수를 빠르게 구하는 방법 * 일반적인 소수 판별 코드 (시간 복잡도: O(N)) boolean isPrime(int x) { for (int i=2; i < x; i++) { if (x % i == 0) { return false; } } return true; } [에레토스테네스의 체 동작 방식] ex) 1~25에서 소수 판별 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 2. 2부터 시작해서 특정 숫자의 ..

이분 탐색(Binary Search)

이분 탐색(Binary Search) - 정렬되어 있는 배열에서 데이터를 찾으려 할 때 탐색 범위를 절반으로 줄여가며 데이터를 찾는 방법 - 배열의 중앙값을 조사하여 탐색하고자 하는 값이 왼쪽 혹은 오른쪽에 있는지 알아내어 검색해야할 배열의 크기를 반으로 줄인다. - 순차 탐색에 비해 굉장히 효율적인 알고리즘 ex) 10억명의 이름이 담긴 배열에서 특정 이름을 찾으려면 순차탐색에서는 약 5억번의 비교가 필요하지만 이분탐색으로는 약 30번의 비교만으로 찾을 수 있다. * 이분 탐색을 할 수 있는 데이터의 조건 : 정렬이 된 배열이어야 함. * 이분 탐색에 적합한 데이터 : 삽입, 삭제가 빈번하기보다는 고정된 데이터 이분 탐색 동작 과정 ex1) 배열 [1,3,5,6,7,9,11,20,30]에서 5을 검색 ..

LRU(Least Recently Used) 캐시 알고리즘

LRU 캐시 알고리즘 - Least Recently Used (가장 최근에 사용한) - 가장 오래전에 참조된, 덜 최근에 사용된 데이터를 내쫓는다. 최근에 참조된 것이 가까운 미래에 참조될 가능성이 높은 성질을 이용한 알고리즘이다. - JAVA에서는 Queue 자료구조를 사용하여 구현할 수 있다. 실행 과정 1) data : 1 , 캐시 비어있음. 캐시에 1 삽입 2) data : 2, 캐시 공간 있음. 캐시에 2 삽입 3) data : 3, 캐시 공간 있음. 캐시에 3 삽입 4) data : 4, 캐시 공간 있음. 캐시에 4 삽입 5) data : 1, 캐시에 이미 데이터 1이 있음. continue 6) data : 2, 캐시에 이미 데이터 2가 있음. continue 7) data : 5, 캐시가 ..