Algorithm

Counting Sort (계수 정렬) 시간 복잡도 Counting Sort 알고리즘은 추가적인 배열을 이용하여, 두 수를 비교하는 과정 없이 정렬하는 알고리즘으로, 시간복잡도는 O(n)이다. 장/단점 일반적으로 빠르다는 정렬 알고리즘의 평균 시간복잡도는 O(nlogn)이다. 이에 비하면 Counting Sort는 굉장히 빠른 시간이지만, 메모리 낭비와 정수로 표현되는 자료에 제한된다는 등의 단점으로, 보통은 O(nlogn)의 정렬 알고리즘을 이용한다. Counting Sort는 정렬할 데이터의 크기가 비교적 작을 때 효율적이다. 알고리즘 1. array를 순회하며, 각 값이 나올 때마다 해당 값을 index로 하는 count 배열의 값을 1 증가시킨다. ex. if arr[3] == 1 -> count..

Binary Search (이분 탐색 / 이진 탐색) 정렬된 배열에서 특정 값을 찾는 알고리즘 시간복잡도 O(logN) 알고리즘 이분 탐색은 내가 찾고자 하는 값(key)과 배열의 중간 값을 비교한다. 이 때, key가 더 크다면, 중간 값 이후의 값들만이 탐색 대상이 된다. 반대로, key가 더 작다면, 배열의 중간값 이전의 범위가 다음 탐색의 범위가 되는 것이다. 이렇게 탐색의 범위를 1/2씩 줄여 나간다. (-> 시간복잡도가 logN이 되는 이유) lo 와 hi의 초기 값은 각각 0, arr.size()-1 이다. 중간 인덱스 구하기 mid = (lo + hi) / 2 내가 찾는 값과 중간 값(중간 인덱스에 위치한 값) 비교하기 arr[mid] vs key 비교 결과에 따라 다음 탐색 범위 정하기 ..