지잉지잉 개발일기 지잉지잉 개발일기

그리디 알고리즘(Greedy Algorithm)이란? 탐욕 알고리즘, 욕심쟁이 알고리즘이라고 불림. 매 단계별 현재 최선의 답을 선택해 나가는 알고리즘 백트래킹을 통해 추가적인 검증을 하지 않음. 현재의 선택을 검증하지 않고 바로 다음단계로 이동. 속도가 매우 빠르지만 현재만의 최선의 답을 선택해 나가는 이유로 결과는 최선이 아닌 경우가 있다.

BFS(Breadth First Search, 너비 우선 탐색) 정점들과 같은 레벨에 있는 노드를 먼저 탐색함. 구현에 큐를 사용한다. Root Node로부터 가장 가까운 Node부터 탐색하므로 Root Node와 가까이 있는 Target Node를 찾는데 유용하다. 최단거리 탐색, SNS 친구추천 등에 사용되고 있음. 시간복잡도 O(N) DFS(Depth First Search, 깊이 우선 탐색) Root Node에 이어진 Child Node들 부터 먼저 탐색함. 구현에 스택을 사용한다. BFS보다 속도가 느릴 수 있다. 미로게임 등에서 경로가 존재하는지 여부를 판단할 때 유용하다. 시간복잡도 O(N) 탐색 방식 비교 BFS: A - B - C - D - G - H - I - E - F - J DFS:..

퀵정렬 (Quick Sort) 매우 빠른 수행속도를 자랑하는 정렬방법, 분할 정복 알고리즘에 해당 분할 정복(divide and conquer) 방법 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 합쳐 원래의 문제를 해결하는 전략. 과정 배열 내에서 하나의 요소(피벗(pivot))를 선택한다. 피벗을 기준으로 피벗보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 분류한다. (Divide) 왼쪽, 오른쪽 배열도 피벗을 선택한 후 왼쪽/오른쪽 배열로 분류한다. (재귀) 배열의 크기가 0 혹은 1이 될 때까지 반복한다. (Conquer) 모든 정렬된 배열을 합친다. (Combine) 구현 public class Main { public static void quickSort(int[] arr..

삽입정렬 (Insertion Sort) i번째 데이터를 이전의 원소부터 0번째까지의 데이터들과 비교하여 자리를 교환하는 정렬방식. 예) [1, 3, 5, 2, 4] 배열에서 원소 "2"는 이전의 원소 "5"보다 작으므로 자리교환 -> [1, 3, 2, 5, 4], 그 이전의 원소 "3" 보다 작으므로 자리교환 -> [1, 2, 3, 5, 4] 구현 public static void main(String[] args) { int[] array = {2, 4, 1, 5, 3}; int length = array.length; for (int i = 1; i = 0 && target < arra..

선택정렬 (Selection Sort) 가장 작은 원소를 찾아 앞의 데이터와 자리 교환하는 정렬방식. 예) [2, 3, 1, 5, 4] 배열에서 원소 "1"은 가장 작은 원소이므로 원소 "2"와 자리교환 -> [1, 3, 2, 5, 4] 구현 public static void main(String[] args) { int[] array = {2, 4, 3, 5, 1}; int length = array.length; for (int i = 0; i array[j]) minIndex = j; } int temp = array[i]..

버블정렬 (Bubble Sort) 인접한 두개의 원소를 비교, 자리를 교환하는 정렬방식. 구현 public class Main { public static void main(String[] args) { int[] array = {2, 4, 3, 5, 1}; int length = array.length; for (int i = 0; i array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } } }​ 배열의 길이만큼의 for문을 2번돌리기에 시간복잡도는 O(N^2)