이분 탐색(Binary Search)은 탐색 공간을 절반씩 줄여가며 원하는 값을 찾는 알고리즘이다. 정렬된 배열에서 값을 찾는 알고리즘 이라고 알고 있지만, 실제로 코딩 테스트에서 더 중요한 형태는 매개변수 탐색(Parametric Search)이다. 즉, 단순 배열 탐색이 아닌, 결정 문제(Decision Problem) 를 반복적으로 풀어가며 최적해를 찾아야 하는 경우가 많다. 이분 탐색(Binary Search) 정렬된 배열에서 특정...
C++ STL의 unordered_map은 Key-Value 형태의 데이터를 해시 기반으로 저장하는 연관 컨테이너 이다. 이전 포스팅에서 살펴본 map과 기능적으로는 유사하지만, 정렬을 하지 않고 속도에 집중한 컨테이너 라는 점이 가장 큰 차이이다. std::unordered_map은 내부적으로 해시 테이블 을 사용한다. 특징 Key 중복 X 정렬 X 삽입/삭제/탐색: O(1) 최악의 경우: O(n) (해시 충돌이 심한 경우)...
C++ STL의 map은 Key-Value(키-값) 쌍을 저장하는 연관 컨테이너(associative container)이다. map을 제대로 이해하려면, 그 기반이 되는 pair부터 짚고 넘어가는 것이 좋다. pair std::pair는 서로 다른 두 개의 값을 하나의 객체로 묶어주는 구조체이다. STL에서 아주 자주 사용되며, map의 내부 요소 타입도 pair이다. pair의 선언과 사용 #include <iostream> #include <utility> using namespace std;...
C++ STL의 deque 은 양쪽 끝에서 삽입과 삭제가 모두 가능한 컨테이너 이다. 이름은 double-ended queue 의 약자이며, vector와 queue의 특징을 적절히 섞은 자료구조라고 볼 수 있다. std::deque 은 앞(front)과 뒤(back) 양쪽에서 모두 O(1) 시간에 삽입/삭제가 가능 하다. 또한 vector처럼 인덱스를 활용한 임의 접근(random access) 도 지원한다. 특징 요약 앞/뒤 삽입,...
앞선 포스팅에서는 Gamma Transformation , Negative Transformation 과 같이 픽셀 단위로 밝기 값을 직접 변환하는 기법을 살펴보았다. 이번 포스팅에서는 이러한 단순 밝기 변환의 한계를 보완하는 Histogram Equalization 에 대해 다룬다. Histogram Equalization이 필요한 이유 Gamma Transformation과 같은 기법은 모든 픽셀에 동일한 변환 함수를 적용한다. 이로 인해 특정 밝기 구간에 픽셀이...