푸으름

목차이분 탐색이란?기본 구현 — 직접 짜는 이분 탐색STL — lower_bound / upper_bound매개변수 탐색(Parametric Search)백준 문제 풀이 ✏️ 1. 이분 탐색이란?이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾을 때, 탐색 범위를 절반씩 줄여가며 탐색하는 알고리즘으로, 선형 탐색은 최악의 경우 배열의 모든 원소를 확인해야 하지만, 이분 탐색은 매 단계마다 탐색 범위를 절반으로 줄이기 때문에 훨씬 빠르다.이분 탐색은 반드시 정렬된 상태의 배열에서만 적용 가능하므로 정렬되어 있지 않다면 탐색 전에 먼저 정렬해야 한다.N = 1,000,000일 때 선형 탐색은 최대 1,000,000번 비교하지만, 이분 탐색은 최대 약 20번만 비교하면 된다. 방식시간 복잡..

✏️ 분할 정복(Divide and Conquer)이란?분할 정복은 큰 문제를 작은 문제로 나누어 해결하는 알고리즘 설계 패러다임으로 세 단계로 이루어진다.1. Divide (분할) : 문제를 더 작은 부분 문제로 나눈다2. Conquer (정복) : 부분 문제를 재귀적으로 해결한다3. Combine (결합) : 부분 해를 합쳐 원래 문제의 해를 구성한다 ✏️ 핵심 아이디어 크기 N인 문제를 크기 N/2인 두 문제로 나눌 수 있다면, 재귀 트리의 높이가 log₂N로 줄어든다. 예를 들어, N=8짜리 문제를 단 3단계(log₂8=3)만에 base case까지 분해하게 되는데 이 구조 덕분에 많은 알고리즘이 O(N) → O(N log N) 혹은 그 이하로 줄어든다solve(1..8)├── solve(1...

✏️  문제 링크https://www.acmicpc.net/problem/20920 ✏️ 문제 설명✏️ 로직mapmp를 생성해서 단어와, 해당 단어의 개수를 저장한다.mp의 정보를 vector>v에 저장한다.customSort 함수 생성하기가장 자주 나오는 값 기준단어의 길이순오름차순sort를 통해 정렬하기v[i].first.length() ≥ m인 경우만 출력✏️ 코드#include using namespace std;map mp;// customSort 함수 수정bool customSort(const pair &a, const pair &b) { if (a.second != b.second) { // 가장 자주 나오는 값을 기준 return a.second > b.second; ..

✏️  문제 링크https://www.acmicpc.net/problem/1021✏️ 문제 설명✏️ 로직입력받는 값을 저장할 queue와 위치를 저장할 deque를 생성한다.queue의 길이만큼 반복문을 돌려서 지민이가 뽑아내려고 하는 원소를 뽑는 데 걸리는 연산의 횟수를 더한다fun함수q.front()를 인수로 받아서 만약 dq.front() == q.front()라면 연산 횟수를 returndeque안에서 q.front()의 위치(pos2)가 어디인지 구한다 ⇒ findValuePos함수 구현만약 pos2가 deque의 중간보다 왼쪽에 있다 ⇒ 문제에서 주어진 2번 연산 수행만약 pos2가 deque의 중간보다 오른쪽에 있다 ⇒ 문제에서 주어진 1연 연산 수행단, deque.size()가 홀수인 상황..