해당 수열에서 가장 큰 값을 구하라 or 해당 값이 포함되는지 판단하라.

PS를 하다보면 값의 크기를 기준으로 값을 탐색하는 경우가 많다. 이런 경우 고려해볼 수 있는 알고리즘과 자료구조들을 모아보자.

전체 탐색

최댓값이나 최소값을 고정된 수열에서 탐색한다면 그대로 전체 탐색을 진행하면 된다.

O(n)

• 검색(최댓값, 최솟값) : O(n)

정렬

다양한 응용이 가능하다.(전처리) n번째로 작거나 큰값을 구하는 성능이 빠르다.(O(1)) 데이터 변형은 느리다.

자바에서는 Arrays.sort의 경우 Dual-Pivot Quicksort라는 Quick sort기반의 알고리즘을 사용하며 내부적으로는 배열 크기나 재귀의 깊이를 고려해 최적화한다. Collections.sort는 Tim sort를 기반으로 사용한다. 라이브러리에서 정렬은 정말 중요한 알고리즘인만큼 최적화에 힘써 하나의 알고리즘을 사용하지는 않는다.

기본적으로 빠른 알고리즘들을 사용하면 Quick sort나 Merge sort를 사용한다면 시간복잡도 O(nlogn)이다.

• 구성 : O(nlogn)
• 탐색(n번째로 큰 값) : O(1)
• 탐색(해당 키가 존재하는지 검색) : 전체탐색 O(n) 이분탐색으로 O(logn)
• 값을 추가 : 재정렬 O(nlogn)
• 값을 삭제 : 배열 복제 O(n)

힙

최댓값 최솟값에 빠르게 접근 가능하다. O(1) 특정값 검색은 어렵다.

힙은 반쯤 정렬이라는 말이 있다. 다소 이상한 말 같지만 완화된 기준으로 이루어진 정렬이라고 볼 수 있다. 최소 최댓값 만을 사용한다면 정렬과 동일하게 사용 가능하다. 최댓값 최솟값은 필요하지만 데이터 변동이 잦다면 정렬된 배열보다 빠르다.

• 구성 : 최적화시 O(n) 삽입으로 구성하면 O(nlogn)
• 탐색(최댓값, 최솟값)(peek) : O(1)
• 값을 추가 : O(logn)
• 값을 삭제(최댓값, 최솟값) : O(logn)

자가 균형 이진 탐색 트리

변형에 강하고 조회도 준수하다. 중복 원소가 들어갈 수는 있으나 자바는 중복원소를 허용하는 API가 없다.(Set)

자가균형탐색트리의 경우도 일종의 정렬이라고 볼 수 있다. 힙 보다 엄격한 기준을 가지고 이루어진 정렬이다.

• 구성 : O(nlogn)
• 탐색(특정 키값이 포함되는지) : O(logn)
• 키값을 추가 : O(logn)
• 키값을 삭제 : O(logn)

중요한 점은 자바의 TreeSet TreeMap은 중복키를 허용하지 않는다(하나로 유지됌)

비교분석

일단 구성하는 것 자체는 이런 관계에 있다.

• 힙의 경우 라이브러리 자료구조를 활용해 삽입연산으로 만든다면 O(nlogn)이다.
• 힙에서 정렬된 배열로 만드는 방법은 heap sort를 사용할 수 있다.

서로 제공할 수 있는 연산과 시간복잡도가 다르기 때문에 적절히 선택하여 사용하는 것이 중요하다.