회고장

👣 개요 특정 노드에서 나머지 모든 노드로의 최단거리를 계산하는 알고리즘 최단 경로 문제를 해결하기 위한 그래프 탐색 알고리즘. 그리디 알고리즘가 쓰여 매 순간 가장 최단거리만 선택해서 계산한다. 이 알고리즘을 사용하려면 음의 가중치를 가지지 않은 그래프여야 한다. 여기서 음의 가중치라는 것은 경로를 움직일 때마다 Cost가 늘어나야지 줄어들면 안 된다는 것이다. 👣 복잡도 평균 Big O 표기법 O((V + E)logV) V는 노드 갯수, E는 그래프 간선 수 👣 알고리즘 절차 그래프의 시작 노드를 선택합니다. 시작 노드에서부터의 시작 노드의 거리는 0으로 설정합니다. 나머지 노드들의 거리는 무한대(infinity)로 초기화합니다. 시작 노드를 포함한 모든 노드들을 탐색하기 위해 다음 과정을 반복합니다..

👣 개요 그래프 탐색 알고리즘으로 DFS는 Branch를 탐색할 때, 끝까지 탐색 후에 다른 Branch로 넘어가고 BFS는 특정 노드에 인접한 노드를 최우선으로 탐색한다. 👣 알고리즘 절차 👣 DFS - 재귀 함수 시작 노드에서 함수를 호출하고, 방문한 노드에서 다시 함수를 호출합니다. 노드 말단에서 조건문에 의해 더 이상 함수를 호출하지 않을 때까지 반복합니다. 👣 DFS - Stack 시작 노드를 방문하고, 방문한 노드를 Stack에 넣습니다. Stack에서 가장 최근에 넣은 노드를 꺼내고, 해당 노드의 인접한 미방문 노드를 방문합니다. 이후, 방문한 노드를 Stack에 넣습니다. Stack이 빌 때까지 2단계를 반복합니다. 👣 BFS - Queue 시작 노드를 방문하고, 방문한 노드를 Queue에..

👣 개요 쉽게 말해서 정답을 찍는 방법이다. 다만, 스무 고개 처럼 범위를 점차 줄여가며 찍는 범위를 점차 줄여가는 방법이다. 보통 문제를 직접 풀 수가 없지만 정답값이 주어졌을 때, 해당 값이 정답인지 아닌지 확인하기 더 수월할 때, 사용한다. 👣 복잡도 평균 Big O 표기법 O(log n) 👣 알고리즘 절차 시작점과 끝점을 설정합니다. 시작점과 끝점을 이용하여 중간점을 계산합니다. 중간점은 (시작점 + 끝점) // 2로 구할 수 있습니다. 중간점의 값과 찾고자 하는 값과 비교합니다. 중간점의 값이 찾고자 하는 값보다 크면, 찾고자 하는 값은 중간점의 왼쪽에 위치하므로 끝점을 중간점의 이전 인덱스로 업데이트합니다. 중간점의 값이 찾고자 하는 값보다 작으면, 찾고자 하는 값은 중간점의 오른쪽에 위치하므..

개요 최대 Heap 자료 구조를 이용해서 최대값을 pop하고 해당 값을 뒤부터 적재하며 정렬. 복잡도 최악 평균 최소 Big O 표기법 O(nlogn) O(nlogn) O(nlogn) 알고리즘 절차 모든 요소를 최대 heap 자료 구조로 만들 수 있도록 heapify 시킴. 최대 heap 에서 pop을 하고 마지막 요소와 swap함. 이 과정을 모든 요소가 정렬이 되도록 계속 반복함. 자바 코드 class Heap { public static void main(String[] args) { int[] testCase1 = {1, 26, 9, 67,653,452,2,3,46,87,356543}; heapSort(testCase1); for (int item : testCase1) { System.out.p..

개요 우선 전체 요소를 각 부분 집합의 크기가 1개가 될 때까지 반절로 재귀적으로 쪼갠다. 그리고 쪼개진 부분 집합들을 역순으로 조립해나간다. 이 때, 조립은 2 개씩 진행하며 2개를 조립할 때 각 부분 집합을 큐로 취급하여 두 큐의 맨 앞 요소 중 가장 작은 값을 선택하고 pop하며 차곡차곡 조립한다. 이 과정을 재귀적으로 진행하면 결국 전체적으로 정렬이 된다. 복잡도 최악 평균 최소 Big O 표기법 O(nlogn) O(nlogn) O(nlogn) 알고리즘 절차 합병 정렬을 준비하기 위해 정렬할 배열[arr]와 크기가 똑같은 빈 배열[tmp]을 생성한다. 정가운데 요소를 기준으로 arr를 반으로 잘라내고 각 부분을 재귀적으로 합병 정렬한다. 이 때, 정렬은 후위 순회를 하며 진행한다. 실제 정렬 방법..

개요 특정 값[A]을 기준으로 (A 앞은 A 값 이하의 값들)[B]을, (A 뒤는 A 값 이상의 값들)[C]을 배치한다. 이를 각각 B와 C에 대해 재귀적으로 실행하면 결국 전체에 대해 정렬하게 된다. 복잡도 최악 평균 최소 Big O 표기법 O(n^2) O(n log n) O(n log n) 알고리즘 절차 임의의 특정 값[A]을 기준으로 잡고 A를 제외한 부분의 양쪽 값부터 검사를 진행한다. 즉, 포인터 start와 end를 설정해 특정 규칙에 맞게 start와 end 인덱스의 값들을 Swap한다. 특정 규칙이란, A값을 기준으로 특정 인덱스[pivot]을 기준으로 pivot 앞의 요소들은 A값보다 작아야 하고 pivot 뒤의 요소들은 A값보다 커야 한다는 것을 의미한다. 포인터 start는 맨 앞의 ..

개요 삽입 정렬을 보완한 형태의 정렬. 삽입 정렬은 때에 따라 오른쪽 끝에 있는 요소를 왼쪽 끝으로 옮기기 위해 불필요한 Swap을 수행해야 할 수도 있다. 이를 막기 위해 Swap을 1 칸 단위로 수행하는 것이 아닌 그 이상의 값으로 수행하는 정렬. 복잡도 최악 평균 최소 Big O 표기법 O(n^2) O(n^1.5) O(n) 알고리즘 절차 gap을 설정할 때, 전체 길이의 반절부터 시작해서 다음 단계에서는 그 길이의 반절, 그 다음에서는 또 그 길이의 반절로 설정을 하면 된다. 단, 해당 길이가 짝수일 경우, +1을 해 홀수로 만들어 준다. 해당 gap이 결정되면 모든 범위를 커버할 수 있도록 인덱스 0부터 gap-1까지 반복합니다. 시작점과 gap을 가지고 insertSort를 수행하면 됨. 자바 ..

개요 손 안의 카드 뭉치를 정리하는 것과 같은 원리. 특정 카드가 해당 카드의 앞 카드 뭉치 중 적절한 위치에 삽입하는 방법의 정렬. 복잡도 최악 평균 최소 Big O 표기법 O(n^2) O(n^2) O(n) 알고리즘 절차 첫번째 요소는 스킵하고 2 번째 요소부터 검사를 시작함. i 번째 요소를 임시로 tmp 변수에 담아놓는다. i 번째 요소를 i-X 번째 요소와 비교한다. 만약 i 번째 요소가 더 작다면 i-X 번째 요소에 i-X+1 번째 위치에 놓아 빈 공간을 마련해줌. 이 경우, X값을 +1해서 다시 수행한다. 만약 i 번째 요소가 더 크다면 i-X+1위치에 tmp에 저장한 값을 위치시킴. 이 경우, 3번의 루프를 탈출한다. 자바 코드 class Insert { public static void m..

개요 최소값의 인덱스값을 찾고 해당 위치와 타겟 위치를 Swap하며 정렬하는 방법. 복잡도 최악 평균 최소 Big O 표기법 O(n^2) O(n^2) O(n^2) 알고리즘 절차 타겟 인덱스를 0으로 설정함. 타겟 인덱스부터 끝까지 선형 탐색하며 최소값의 인덱스값을 기억함. 타겟 인덱스와 최소값의 인덱스를 활용해서 Swap함. 타겟 인덱스값을 1로 설정하고 1~3 과정을 다시 반복함. 모든 요소가 정렬되면 종료. 자바 코드 class Selection { public static void main(String[] args) { int[] testCase1 = {1, 26, 9, 67,653,452,2,3,46,87,356543}; selectionSort(testCase1); for (int item : ..

개요 너비가 2인 Window를 (n-1)번 정도 움직이며 Window의 내에서 Swap하며 정렬하는 방법. 복잡도 최악 평균 최소 Big O 표기법 O(n^2) O(n^2) O(n^2) 알고리즘 절차 인덱스 0부터 인덱스 n-2까지 움직이는 크기가 2인 Window를 운용한다. 이 때, 윈도우를 움직일 때마다 크기가 정렬되어 있지 않다면 Swap하기. 1번의 결과로 n-1에는 최대값이 위치하게 되고 다시 인덱스 0부터 인덱스 n-3까지 움직이는 Window를 운용한다. 이 과정을 모든 요소가 정렬될 때까지 진행한다. 자바 코드 class Bubble { public static void main(String[] args) { int[] testCase1 = {1, 26, 9, 67,653,452,2,3..