본문 바로가기

이진 탐색

STL 알고리즘과 직접 작성하는 이진 탐색 알고리즘 이진 탐색 알고리즘은 로그 시간 복잡도를 보여주는 대표적인 탐색 알고리즘이다. 정렬된 컨테이너에서 어떤 요소를 찾아야 한다면, 우선적으로 고려해봐야 하는 알고리즘 중 하나이다. 만약, STL을 사용하고 있다면 이진 탐색을 적용하는 것은 매우 쉽다. STL 알고리즘은 binary_search, lower_bound, upper_bound, equal_range와 같은 로그 시간 복잡도를 가지는 탐색 함수들을 이미 가지고 있다. 그러나, 때로는 이들 함수를 직접 적용하는 것이 가끔 곤란할 때가 있다. 즉, binary_search는 이진 탐색 함수이기는 하지만 컨테이너에서 주어진 값을 가진 원소가 있는지 없는지만 알려줄 뿐, 컨테이너 내에서의 원소 위치를 알려주지 않는다. lower_bound의 경우, 주어.. 더보기
맵과 정렬된 벡터 : 어느 것이 더 나은가? STL의 연관 컨테이너와 시퀀스 컨테이너는 몇 가지 중요한 차이점이 있다. 가장 중요한 것은, 메모리의 연속성이다. 벡터와 같은 시퀀스 컨테이너는 켄테이너 요소들의 인접성을 보장하지만, 연관 컨테이너는 이것을 보장하지 않는다는 점이다. 그러나, 연관 컨테이너는 언제라도 평균 이상의 컨테이너 요소들의 삽입, 삭제, 검색을 보장해주는, 중요한 특징을 가지고 있다. 흔히 이야기하는, '맵을 사용하는 것보다 정렬된 벡터를 사용하는 것이 낫다'라는 이야기는, 이 메모리의 연속성 여부와 관련있다. 즉, 맵은 하나의 노드를 생성하는데 메모리가 연속된 형태가 아니기 때문에 나름대로의 메모리 할당 비용이 발생하며, 벡터보다 약간 비싼 오버헤드가 존재한다. 노드 하나를 추가하는데 추가적인 메모리 할당 비용이 들어가는 것은.. 더보기

티스토리툴바