Idea그리디(Greedy) 알고리즘은 현재 상황에서 가장 좋은 선택을 하는 방식으로 최적의 해답을 찾는 알고리즘이다. 각 단계에서 가장 좋다고 생각되는 선택을 함으로써 최종적인 해답에 도달하는 것이 목표이다. 따라서 그리디 알고리즘이 항상 최적의 해를 보장하지는 않지만, 특적 문제에서는 매우 효과적으로 작용한다.첫 번째 그림과 같은 그래프가 있을 때, 거쳐가는 모든 값의 최댓값을 만든다고 한다면 정답은 Optimal 부분의 0 → 3 → 100 일 것이다. 하지만 그리디 알고리즘을 사용한다면 현재 위치에서의 최선의 선택을 하기 때문에 0의 위치에서는 3과 10 중에 10이 더 크므로 10으로 이동하고 10의 위치에서는 7과 8 중에 8이 더 크므로 8로 이동할 것이다. 즉, 그리디 알고리즘을 사용하면 ..
Idea이진 탐색(이분 탐색)은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.이진 탐색을 사용할 때는 반드시 배열 내부의 데이터가 정렬되어 있어야 한다.(left, mid, right)를 사용하며 찾아야 하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소관계에 따라 특정 구간으로 이동하는 것을 반복한다.범위 속의 원소의 개수가 1개가 될 때까지 계속 탐색을 진행해야 하므로 while문을 통해 (left 영상의 Binary search(이분 탐색)과 Sequential search(순차 탐색)의 비교 횟수를 보면 이분 탐색의 탐색 횟수가 훨씬 적은 것을 확인할 수 있다.Codepublic class BinarySearch { // 반복문 이용 ..
Idea 기수 정렬은 맨 뒤에 있는 자릿수부터 해당 자릿수를 기준으로 정렬한 뒤, 앞으로 이동하며 각 자리 수를 기준으로 정렬하다가 최종적으로 가장 높은 자리수를 기준으로 정렬하는 방법이다. [823, 916, 423, 840, 268]을 기수 정렬을 이용해서 정렬해보겠다. 가장 낮은 1번째 자리(1의 자리)부터 가장 높은 3번째 자리(100의 자리) 순으로 정렬한다. 첫 번째로 가장 낮은 자리인 1의 자리 수를 기준으로 버킷에 넣는다.0 ~ 9 까지 버킷 번호에 각 숫자들이 자리를 찾아 배치되고 정렬되어 나온다.(버킷 내에서 정렬되는 것이 아님)이렇게 1의 자리수를 오름차준으로 정렬하여 [0, 3, 3, 6, 8]이 되고, 이를 기준으로 계수를 정렬하면 [840, 823, 423, 916, 268]으..
버블 정렬Idea첫 번째 값과 두 번째 값을 비교하고, 두 번째 값과 세 번째 값을 비교하며 n-1 번째 값과 n 번째 값을 비교한다. 만약 n-1 값이 n 값 보다 크다면 서로 순서를 바꾼다. 이렇게 한 번 루프를 거치면 가장 큰 값이 오른쪽 끝에 위치하게 된다. 이 루프를 반복하여 정렬을 완료한다.Codepublic class Main { public static int n; public static int[] arr = new int[100]; public static void bubbleSort() { boolean sorted; do { sorted = true; for(int i = 0; i arr[i + 1])..
