만족

문제 길이가 4인 [1,2,3,4] 배열이 있다. 여기에서 인덱스 0번부터 2번까지의 합을 구하라. 또, 인덱스 1번의 값을 10으로 변경했을 때의 인덱스 0번부터 2번까지의 합을 구해보라. 생각해볼 것 가장 간단한 방법은 주어진 범위(0~2)까지 배열을 순회하며 합계값을 구할 수 있다. 중간에 값이 바뀌면, 배열의 해당 인덱스의 값을 바꾼 후, 다시 주어진 범위에 대해 순회하며 합계값을 구할수 있다. 그러나 여기서 배열의 길이가 4가 아니라, 천만으로 증가하고 구간이 0~500만, 200만~700만, ... (구간의 길이가 500만)처럼 구해야 하는 누적합의 종류가 100가지라고 해보자. 이렇게 되면 매 구간에 해당하는 인덱스 위치를 모두 순회하여 부분합을 새로 계산해야 하므로 구간의 길이인 500만에..

버블 정렬은 2중 for문을 사용해 각 순회마다 인접한 요소들을 비교해 조건을 만족할 경우 위치를 스왑하는 방식(한칸씩 미는 방식)으로 요소를 정렬한다. 매우 쉽지만, 소팅 방법중에 효율이 나쁜 편에 속한다. 작동예시 [3,2,1]을 오름차순 정렬한다고 생각해 보자. 첫 번째 반복 arr= [3,2,1] //i=0. j= 1 to 2 (i+1부터 배열의 길이-1 까지) [2,3,1] //3과 2를 비교하는데 2가 더 작으므로 위치 스왑 (i=0, j= 1) [2,1,3] //3과 1을 비교하는데 1이 더 작으므로 위치 스왑 (i=0, j=2) //첫 번째 반복에서 가장 큰 수는 3으로 결정되었으므로 마지막 요소(arr[2])는 더 이상 검사하지 않음 //i=1. j= 2 to 2 (i+1부터 배열의 길이..

O 표기법 Big O 표기법이라고 읽는다. 알고리즘의 Time Complexity를 분석하는 데 가장 많이 쓰이는 표기법이다. O(g(n)) = { f(n) | 충분히 큰 n에 관해서 f(n)

이분 탐색(Binary Search) 정렬되어 있는(이분 탐색의 주요 조건) 배열에서 데이터를 찾으려 시도할 때, 순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라 탐색 범위를 절반씩 줄여가며 찾아가는 Search 방법이다. 작동예시 1 2 3 4 5 6라는 값에서 6을 찾고자 한다면 배열의 중간에 위치한 3이라는 값과 6을 비교한다. 6은 3보다 크므로, 이제 3의 왼쪽에 위치하는 값들은 탐색할 필요가 없으므로 (어차피 3 왼쪽에 있는 수들은 3보다 작기 때문이다) 3의 오른쪽에 있는 값들을 대상으로 탐색을 다시 시도한다. 이제 4 5 6이 남았으므로, 다시 중간값인 5와 찾고자 하는 대상인 6를 비교한다. 6은 5보다 크므로, 5의 오른쪽에 있는 값들을 대상으로만 탐색..

퀵 정렬 Merge Sort와 비슷하게 Divide and Conquer기법을 사용하고 Recursive Function을 이용한다. 매 재귀마다, Quick Sort는 Pivot이라는 정렬의 기준이 될 기준을 선정한다. 효율적인 Pivot을 선정하는 방법은 다음에 설명하기로 하고, 우선 Pivot을 현재 배열의 마지막 데이터로 하기로 하자. 그 Pivot을 기준으로 Pivot보다 작은 데이터들은 Pivot의 왼쪽으로, 큰 데이터들은 Pivot의 오른쪽으로 옮긴다. 그러면, Pivot은 제 위치를 찾게 되고(정렬이 끝난 뒤의 위치에 존재한다) 정렬되지 않은 배열은 Pivot의 왼쪽과 오른쪽이다. (2개의 정렬되지 않은 부분배열로 나누어진다.) 이제 정렬되지 않은 부분배열에 대해서 Quick Sort를 반..

병합 정렬 n개의 정렬되지 않은 데이터들이 들어있는 배열에서1번째부터 n/2번째까지, n/2+1번째부터 n번째까지의 데이터를 2개의 배열로 나누고 이 나누어진 배열을 다시 1번째부터 (n/2)/2번째까지, (n/2)/2+1번째부터 n/2번째까지의 2개의 배열과(n/2)+1번째부터 (n/2)+1 + (n/2)/2번째까지, (n/2)/2+1 + (n/2)/2+1번째부터 n번째까지 2개의 배열로 나눈다. 이러한 과정을 계속 반복하여각각의 array의 길이가 1이하가 될 때 까지 n개의 데이터가 들어있는 1개의 배열을 k개의 부분배열로 나눈다. 그리고 잘게 쪼개어진 배열들을 2쌍씩 묶어서 정렬한다. 쉽게 말해서, 큰 문제를 여러 개의 작은 문제들로 쪼개어 처리하는 Divide and Conquer기법을 사용한다..

n개의 데이터가 있는 배열이 있다고 하자. 2번째 데이터부터 n번째 데이터까지 하나씩 데이터를 선정하여 반복하는데 선정된 데이터의 번쨰(index)가 k번째 데이터라면 k-1번째 데이터부터 1번째 데이터까지 k번째 데이터와 비교하면서, 만약 비교당하는 ?번째 숫자가 k번째 데이터보다 크다면 ?번째 데이터를 오른쪽으로 한 칸씩 옮긴다. 그리고 ?번째에 원래의 k번째에 있던 데이터를 삽입한다. 이 과정이 끝나면 k+1번째를 시작하면서 같은 과정을 n번째 데이터까지 반복한다. Java Code public static void insertionSort(int[] array){ for(int i=1; i=0 && array[j]> target){ array[j+1]= array[j]; j--; } array[j..

선택 정렬 오름차순 정렬을 한다고 하면, n개의 데이터가 있는 배열에서 첫 번째 데이터를 선택하고, 두 번째 부터 n번째 배열을 첫 번째 데이터와 비교하면서 가장 작은 값의 데이터를 찾는다. 찾았다면, 그 데이터와 첫 번째 데이터의 위치를 서로 바꾼다. 이 과정을 첫 번째 데이터부터 n-1번째 데이터까지 반복한다. [Java Code] public class EEE { public static void main(String args[]){ int array[]= {1,3,4,6,2,8}; selectionSort(array); for(int i=0; i arr[k]) { minIndex = k; } } if (minIndex !== l) { const temp = arr[minIndex]; arr[min..