이진탐색 찾아야 하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소 관계에 따라 특정 구간으로 이동하는 것을 반복. 전제 숫자들이 좌에서 우측으로 커진다는 전제에서 가능하므로, 숫자들은 항상 정렬되어있어야 한다. 가운데의 숫자를 선택하고 해당 숫자보다 크다면 우측(최소 값 위치를 타겟 숫자 + 1로 변경, 최대 값 위치 유지) 작다면 좌측 범위를 선택하게 되는 것(최소 값 위치 유지, 최대 값 위치를 타겟 숫자 -1로 변경) 시간복잡도는 구간의 길이가 1이 될때까지 계속해서 반으로 감소하는 것을 반복하기 때문에, 루프는 약 log2​N 번 돌게 된다. 루프 내부 연산의 시간 복잡도는 O(1)이기 때문에, 자연스럽게 시간복잡도는 O(1∗logN)=O(logN) 이진 탐색을 사용 하는 이유는 ..

Insertion Sort 2번째 원소부터 시작하여 i-1(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다. 예제 1 public int[] solution(int[] arr) { if (arr == null) return null; int temp; for (int i = 1; i = 0; k--) { if (temp >= arr[k]) { break; } arr[k + 1] = arr[k..

Bubble Sort N개의 원소를 가진 배열을 정리할 때, 서로 인접한 두 개의 데이터를 비교하고, 조건에 맞춰 자리를 교환하며 정리하는 알고리즘입니다. 시간 복잡도가 O(n^{2})로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용되며. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름입니다. 예시 1 void bubbleSort(int[] arr) { int temp = 0; for(int i = 0; i arr[j]) { // 3. // swap(arr[j-1], arr[j]) temp = arr[j-1]; ar..