CS/알고리즘

이진탐색 - Lower bound, Upper bound

Target으로 찾는 값이 한 배열 안에 여러 개 존재할 때, target 값 이상의 값이 최초로 나오는 위치를 Lower Bound라고 한다. Target을 초과하는 값 중, 가장 인접한 위치를 Upper Bound라고 한다. Target보다 같거나 작은 숫자들 중, target 값이 마지막으로 나오는 위치를 Custom Bound라고 한다. Lower Bound public static int lowerBound(int[] arr, int target) { int left = 0; int right = arr.length - 1; int minIdx = arr.length; while (left = target) { right = mid - 1; minIdx = Math.min(mid, minIdx)..

이진탐색

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

[DP] 한 칸씩 이동하여 최대 합 구하기.

조건 각 칸에 숫자가 적혀있는 판이 존재한다. 이동은 (i+1, j), (i+1, j+1)만 가능하다. 풀이 마지막 방문 위치가 dp[i][j]일 때, 해당 위치에 도달할 수 있는 경우는 바로 위에서 내려온 경우, 왼쪽 대각선 위에서 내려오는 경우 두가지 경로가 존재한다. 이전 위치와 현재 위치의 값을 합한 후, 최대값을 dp[i][j]에 저장한다. 점화식 dp[i][j] = max(dp[i-1][j] + a[i][j], dp[i-1][j-1] + a[i][j])

[Sort] 삽입 정렬 (Insertion Sort | Java)

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..

[Sort] 거품 정렬 (Bubble Sort | Java)

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..