그래프 구현 방식 그래프 구현 방식에는 2가지가 있다. 1. 인접 행렬 2. 인접 리스트 최단 거리 알고리즘 1. BFS - 간선 가중치가 없을 때 2. 다익스트라 - 간선 가중치가 있을 때 3. 벨만-포드 - 음의 가중치가 있을 때 4. 플로이트 워셜 - 모든 정점에서 모든 정점까지의 최단거리를 구할 때 https://velog.io/@ehdrms2034/알고리즘-최단-경로-알고리즘-다익스트라-벨만-포드-플로이드-알고리즘 2022. 3. 31. 카운팅 정렬 (도수 정렬, 계수 정렬) 요소의 대소 관계를 판단하지 않고 정렬하는 알고리즘 시간복잡도는 일단 O(N)이다. 뒤에서부터 진행하면 안정적이다. 중간에 도수분포표/누적도수분포표에 해당하는 배열을 새로 사용해야 한다. 그리고 배열의 요소값의 범위에 따라 해당 배열의 길이가 달라진다! 즉, 정렬하는 요소수는 적은데 요소값의 범위가 엄청 크다면, 극단적으로 엄청난 메모리가 낭비된다. 2021. 11. 20. 병합 정렬 요소가 2개 이상인 경우, 1. 앞 부분을 병합 정렬한다. 2. 뒷 부분을 병합 정렬한다. 3. 앞 부분과 뒷 부분을 병합한다. 추가 공간을 필요로 하기 때문에 제자리 정렬이 아니다. 안정적이다. 이진트리로 대입해서 생각해보면, 이진트리의 높이, 즉, 반으로 나눗 횟수, 다시 병합할 횟수, stage 수 등등 -> logN 어느 한 레벨에서 노드 2^M개, 한 노드에 있는 요소수 N*(1/2)^M개이므로 한 레벨에서 비교에 대한 복잡도는 O(2^M * N*(1/2)^M) -> O(N)이다. 따라서 O(NlogN)의 시간복잡도를 가진다. 2021. 11. 20. 셸 정렬 삽입 정렬의 장단점을 보면, 장점 : 거의 정렬은 마친 상태에서는 속도가 굉장히 빠르다. 단점 : 타겟 요소가 이전 요소들(정렬된)보다 작으면 이동하는 횟수가 많아진다. 셸 정렬은 단점을 보완하고 장점을 살리기 위해 고안된 정렬 알고리즘이다. 삽입 위치가 멀 경우, 한 칸씩 비교하면서 교환하는 것이 오래 걸리기 때문에, 일정 간격으로 띄엄띄엄 비교/교환을 한다는 아이디어다. 그리고 이 간격을 줄여가다보면 정렬이 완료될 것이다. 1. 얼만큼 띄어가면서 검사할 지 간격을 정한다. 2. 해당 간격만큼 요소들을 띄워 묶어서 그룹 별로 나눈다. 3. 나눈 그룹 별로 각자 삽입 정렬을 한다. 4. 적당한 간격으로, 적당한 횟수만큼 진행하여 거의 정렬된 배열을 만든다. 5. 최종적으로 1을 간격으로 하여 삽입 정렬을.. 2021. 11. 19. 삽입 정렬 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입하는 알고리즘 * 타겟인 요소와 이전 위치(이미 정렬된)에 있는 요소들을 비교하여 알맞은 위치를 찾는다. 1. 타겟 요소와 바로 이전 요소와 비교 2. 타겟 요소가 작다면 이전 요소와 교환하고 아니면 종료 3. (교환했다면) 타겟 요소와 교환한 위치의 이전 요소와 비교 4. 타겟 요소가 작다면 교환하고 아니면 종료 5. 하나의 요소의 위치가 정해지면 원래 타겟 요소 다음 위치의 요소로 위 과정을 반복한다. 차례대로 비교/교환하므로 안정적이다. 거의 정렬된 경우에는 (best 상황) n번의 비교만 하고 교환하는 과정이 없으므로, O(N) 역순인 경우 (worst 상황) 타겟 요소가 이전 요소들 중에 제일 작을 것이므로, 타겟 요소를 맨 .. 2021. 11. 16. 선택 정렬 가장 작은 요소부터 선택해 맞는 위치로 옮기면서 순서대로 정렬하는 알고리즘 1. 주어진 배열의 요소들 중에서 최소값을 찾는다. 2. 해당 값을 배열의 맨 앞자리 요소와 교환한다. 3. 맨 앞자리를 뺀 나머지 요소들도 위와 같은 방법으로 교환한다. 즉, 정렬하지 않은 부분에서 최소값을 찾고, 그 값을 정렬하지 않은 부분의 첫 번째 요소와 교환하는 과정을 반복한다. 최소값을 찾으려고 비교한 횟수가 n-1, n-2, n-3, ... , 2, 1번이므로 시간 복잡도는 O(N^2)이다. 그리고 서로 떨어져 있는 요소를 교환하므로 안정적이지 않다. 2021. 11. 16. 버블 정렬 일반적으로 가장 기본적으로 생각할 수 있는 방법 인접한 두 요소의 대소 관계를 비교하여 교환을 반복! 앞(혹은 뒤)에서부터 차례대로 비교/교환이 이루어지기 때문에 안정정렬 맨 앞에서부터 현재 요소와 바로 다음 요소끼리 비교 현재 요소가 다음 요소보다 크다면 교환 다음 인덱스로 이동해 그 다음 요소와 비교/교환을 반복 배열의 요소 갯수가 n개라 한다면, 이웃한 요소끼리 비교/교환 작업을 처음부터 끝까지 한 번 진행하면, 가장 큰 요소가 맨 마지막 인덱스로 이동한다. 이 과정을 패스라고 한다.(n-1회 비교) 그리고선 남은 n-1개 요소로 비교/교환을 앞에서부터 끝까지 한 번 진행하면, 다음으로 큰 요소가 맨 마지막 직전 인덱스로 이동한다. (n-2회 비교) 이런 식으로 계속 진행하면, 이러한 작업이 총 n.. 2021. 11. 16. 자바 배열 정렬 (Comparable / Comparator 차이) 둘 다 "객체를 특정 기준으로 비교할 수 있도록 한다." Comparable - Comparable 인터페이스를 쓰려면 compareTo(T o) 구현 - 자기 자신과 매개변수 (T클래스 자료형 o) 객체를 비교 - lang패키지에 있어 import 필요 x Comparator - Comparator 인터페이스를 쓰려면 compare(T o1, T o2) 구현 - 두 매개변수 객체를 비교 - util패키지에 있어 import 필요 - Comparator 인터페이스를 구현하는 클래스는 비교하는 두 객체와 아무 관련이 없고, compare()만 overriding해서 비교할 때만 사용하려고 하는 것이다. 그래서 Comparator을 구현하는 익명 객체를 생성하여 주로 사용한다. - Comparator을 구현.. 2021. 11. 12. 이전 1 다음