C++ STL 정복하기 (2) 썸네일형 리스트형 이분탐색 (binary search) C++ STL 사용법 알아보고, 구현해보자! 1. 정의 살펴보기 오늘은 이분 탐색 알고리즘에 대해서 알아보겠다. 여느 때와 동일하게 위키피디아를 켰다. 장황하게 설명되어 있는데, 핵심 문장을 살펴보면 아래와 같다. 타겟 밸류와 배열의 중간값을 비교하여 일치하지 않았다면 '타겟이 있을 수 없는 절반의 영역을 삭제' 한 후, 나머지 절반의 영역에서 해당 과정을 반복하는 탐색방법이다. 이 탐색은 타겟이 발견될 때까지 계속된다. 라고 되어있다. 요컨데, 내가 초등학생 때 했던 놀이 중 하나와 상당히 닮아 있는 것 같다. 혹시 Up Down 게임을 해 봤다면 이해가 굉장히 쉬울 것 같다. 1부터 100까지의 숫자를 하나 생각하고, 상대가 하나를 추측해서 제시한다. 그럼 나는 내가 생각한 숫자가 더 크다면 UP, 내가 생각한 숫자가 더 작다면 DOWN을 외치.. C++ sort() 함수에 대해서 알아보자. 1. 정의 살펴보기 백준 단계별로 풀어보기 13장에 해당하는 정렬 단원에서는 algorithm STL에 속해있는 sort() 함수를 사용하는 문제가 등장한다. 우선 sort() 함수가 어떤 함수인지 먼저 알아보기로 했다. cplusplus.com 에서 제시된 sort() 함수의 사양이다. 차례로 살펴보자. 우선 sort 함수의 템플릿을 보면 변수를 2개 입력 받는 경우와, 3개 입력 받는 경우의 두 가지가 있다는 것을 알 수 있다. 이 녀석을 해석해보자. 1. [first, last) 범위에 있는 원소들을 '오름차순'으로 정렬한다. 2. 변수를 2개 입력 받는 경우는 < 연산자를 사용해 정렬하고, 변수를 3개 입력 받는 경우는 comp 변수를 사용해 정렬한다. 3. 동일한 원소의 경우 기존의 순서를 보장.. 이전 1 다음
