정렬 썸네일형 리스트형 이진탐색(Binary Search)와 Parametric Search 이진탐색(Binary Search)와 Parametric Search 1. 이진탐색1.1 기본 아이디어우리가 원하는 값을 찾고 싶을 때에는 정말 간단하게 생각하면, 모든 값들을 하나씩 보면서 맞는지 아닌지 확인는 방법이 직관적인 방법이라고 할 수 있다. 하지만 이렇게 찾는 것은 가장 마지막에 원하는 값이 있을 경우, 모든 값 들을 한번 씩 살펴보아야 하기 때문에, O(N)으로 볼 수 있다. 그렇다면 좀더 효율적인 방법은 없을까? 에서 시작한 것이 바로 이진탐색(Binary search)이다. 이진탐색(Binary search)의 경우는 결과적으로 보면 O(logN) 만에 원하는 값을 찾을 수 있는데, 그 이유는 정렬이 되있다는 가정이 있기 때문이다. 아래의 그림을 보면서, 왜 그러한지 직관적으로 이해를 .. 더보기 퀵소트(quick sort) 알고리즘 퀵소트(quick sort) 알고리즘 정렬 알고리즘 중 평균적으로 O(NlogN)으로 알려져 있는 Quick sort에 대해 알아보자. 1. 기본 아이디어 기본적으로 O(N^2)으로 정렬하는 알고리즘(Ex : 버블정렬)은 바꾸는 기준이 순회를 하면서 바뀌어 지면서, 일반적으로 for문의 중첩으로 O(N^2)의 복잡도를 가지게 된다. 하지만 퀵소트 알고리즘은 직관적으로 보았을 때, 비교를 반씩 줄여나가면서 해보자! 라는 생각으로 접근을 하면 이해하기 좋을 것 같다. 즉 재귀를 이용한 분할정복 알고리즘이다. 기본적인 아이디어는 상당히 쉽다. 특정한 기준을 Pivot 이라고 부르고 이 pivot을 기준으로 pivot보다 작으면 왼쪽으로, pivot보다 크면 오른쪽으로 이동한다. 기본적인 아이디어를 바탕으로 제.. 더보기 이전 1 다음
