개발일지

이진 탐색 개요 예전 이진 탐색에 대한 개념적인 부분을 해당 글에서 다룬 적이 있었다. 다시 상기하자면, 정렬된 배열을 반으로 나눠가며 원하는 값을 찾는 알고리즘이 이진 탐색이다. 이번 시간에는 해당 알고리즘을 구현한 std::binary_search 함수에 대한 사용법을 알아보도록 하자. 본문 사용법 이진 탐색 또한 탐색의 일종이므로, 배열 내에서 특정 요소가 존재하는지 확인할 때 사용된다. 이때 대상 범위가 이미 정렬되어 있어야 하며, 중복 요소가 있는 경우 어느 요소인지 알 수 없다. 이는 함수가 단순히 주어진 값이 배열 내에 존재하는지 여부만을 체크하기 때문이다. #include #include #include int main() { std::vector v = { 1, 2, 4, 5, 9, 10..

문제설명 입출력 예제 개념 이 문제는 주어진 문자열 내에서 특정 문자가 등장하는 빈도를 특정 구간에서 확인하는 것을 요구한다. 일반적으로, 구간 l에서 r까지 특정 문자 비교를 직접 수행하는 경우, 문자열의 길이가 매우 긴 경우엔 계산 시간이 지나치게 오래 걸릴 수 있으므로 시간 초과 문제에 직면하게 된다. 이러한 문제를 극복하기 위해 '특정 구간'이라는 핵심 키워드에 주목하고, 누적합의 개념을 적용하면 이 문제를 보다 효율적으로 해결할 수 있다. 또한 문자의 등장 횟수를 벡터에 초기화하여 이진 탐색을 통해 구현할 수도 있다. 풀이 (1) 이진 탐색 #include #include #include using namespace std; vector v[26]; string str; int T, l, r; ..

문제설명 입출력 예제 개념 집합 A와 B가 주어졌을 때 (A - B) ∪ (B - A)의 값을 구하는 문제다. 자료구조 map을 이용해서 푸는 방법도 있지만, 필자는 조금 다르게 풀었다. 두 집합의 원소를 벡터에 삽입 교집합을 이진 탐색을 이용하여 정수형 변수에 삽입 벡터의 크기에서 교집합의 원소의 차를 출력 풀이 #include #include #include int main() { int N, M, n, count = 0; std::cin >> N >> M; std::vector v(N + M); 집합 A, B의 원소의 개수 N, M, 입력받을 숫자 n, 교집합의 수 count를 초기화해준다. 그리고 N + M의 크기를 가지는 벡터 v를 초기화해 준다. for (int i = 0; i < N; i++..

문제설명 입출력 예제 개념 M개의 카드 중에 N개의 숫자 카드와 같은 것이 몇 개 있는지 출력하는 문제다. map 자료 구조에 저장하여 개수를 출력하면 시간 초과 문제에 걸리게 되는데, 이는 map 자료구조는 연산이 O(logN)의 시간 복잡도를 가지기 때문이다. 즉, M개의 숫자를 하나씩 확인할 때마다 시간 복잡도가 O((N+M) logN)이 되므로 다른 방법을 찾아야 한다. 따라서 시간 복잡도를 줄이는 과정이 필요한데, 이진 탐색을 이용한 std::upper_bound() 함수와 std::lower_bound() 함수를 사용하거나 map의 멤버 함수인 find() 함수와 반복자를 적절하게 이용하면 해결할 수 있다. 풀이 (1) map #include #include #include int main()..