CS 드릴

1. 개념 힙 : 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된, 완전 이진 트리를 기본으로 한 자료구조 완전 이진 트리 : 부모 노드 밑에 자식 노드가 최대 2개까지 있을 수 있고, 마지막 레벨을 제외한 모든 레벨에 노드가 완전히 채워져 있는 트리 구조 최대 힙 : 부모 노드가 자식 노드보다 항상 크거나 같은 트리 최소 힙 : 부모 노드가 자식 노드보다 항상 작거나 같은 트리 힙 정렬 : 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 알고리즘 2. 구현 (kotlin) fun heapify(array: IntArray, index: Int, heapSize: Int) { // 부모 노드와 자식 노드의 인덱스 지정 var parent = index val leftChild = parent..

퀵 정렬(quick sort) 개념 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다 정렬 과정 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들) 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. - 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다. - 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스..

1. 개념 새로운 숫자가 삽입될 때 정렬된 배열 안에서 자신의 위치를 찾아가며 정렬하는 알고리즘 2. 구현 (kotlin) fun insertionSort(arr: IntArray) { for (i in 1 until arr.size) { // i = 현재 정렬된 배열의 크기 val key = arr[i] var j = i - 1 // 정렬된 배열에서 제일 큰 숫자의 인덱스(가장 오른쪽에 있는 숫자의 인덱스) while (j >= 0 && arr[j] > key) { // 정렬된 배열에서 제일 큰 숫자의 인덱스부터 0번 인덱스까지 비교하면서 현재 값이 key보다 크면, arr[j + 1] = arr[j] // 현재 값을 한 칸 오른쪽에 덮어 씌운다. j -= 1 } arr[j + 1] = key // 올..

합병 정렬(merge sort) 개념 분할 정복 방식을 이용해서 하나의 리스트를 두 개의 리스트로 분할한 다음 각각의 분할된 리스트를 정렬한 후에 합해서 정렬된 하나의 리스트로 만드는 정렬 알고리즘 정렬 과정 분할 단계 주어진 배열의 중간 인덱스를 구한다. 중간 인덱스를 기준으로 배열을 반토막 낸다. 정복 단계 반복해서 반토막을 내다가 마침내 배열의 크기가 0이나 1이 된다. 그러면 주어진 배열을 바로 '답'으로 반환한다. 합병 단계 왼쪽 배열, 오른쪽 배열을 인자로 넣어서 각각 정렬된 결과를 얻는다. 양쪽 배열의 맨 앞을 비교해 더 작은 수를 찾는다. 더 작은 수를 꺼내서 새로운 배열에 집어넣는다. 새로운 배열에 모든 숫자가 들어갈 때까지 반복한다. 예제 합병 단계 예제 예제 코드 (코틀린) const..

버블 정렬(bubble sort) 개념 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 정렬 과정 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 예제 💡 배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬..

선택 정렬 (selection sort) 개념 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 오름차순을 기준으로 했을 때 리스트의 첫 번째 인덱스에는 해당 리스트에서의 최솟값을 찾아 치환하고 그 다음 인덱스에서는 첫번째 인덱스를 제외한 리스트에서의 최솟값을 찾아 치환하고를 반복해 나가는 방식 정렬 과정 주어진 배열 중에서 최솟값을 찾는다 그 값을 맨 앞에 위치한 값과 교체한다 맨 앞에 위치한 값이 최솟값이라면 패스한다 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다 예제 💡 배열에 9, 6, 7, 3, 5가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해보자 1 회전 첫 번째 자료 9를 두 번..