📚 [C++/ 백준 11066번] 파일 합치기 - DP(다이나믹 프로그래밍), prefixsum(누적합)🔍 문제 요약문제링크 : 백준 11066번주요 태그: DP 다이나믹프로그래밍, prefixsum 누적합 소설을 여러 장으로 나누어 작성하며, 각 장은 서로 다른 파일로 저장된다. 이 파일들을 하나로 합치기 위해 두 개씩 계속 합치기를 반복한다.이때 두 파일을 합치는 데 드는 비용은 두 파일의 크기의 합이다.파일의 순서를 바꿀 수는 없으며, 모든 파일을 하나로 합치기 위한 최소 비용을 구해보자.💡 문제 분석입력:테스트케이스 수 T각 테스트케이스마다 K (파일 개수), 그리고 각 파일의 크기 (정수 K개)출력:각 테스트케이스마다 모든 파일을 하나로 합치기 위한 최소 비용제한 조건:3 ≤ K ≤ 500..

✅ 1. 이분 탐색 (Binary Search)🔍 개념정렬된 배열(또는 수의 범위)에서 원하는 값을 빠르게 찾는 알고리즘→ 매 반복마다 탐색 범위를 절반으로 줄여 O(log N)의 시간복잡도를 가짐📌 사용 조건조건설명정렬된 배열값이 오름차순 또는 내림차순으로 정렬되어 있어야 함단조성비교 결과가 "왼쪽" 또는 "오른쪽"으로 명확히 구분되어야 함인덱스로 접근 가능보통 배열, 벡터처럼 중간 값을 쉽게 접근할 수 있어야 함📘 대표 문제 유형숫자 X가 배열에 있는지?조건을 만족하는 최솟값 or 최댓값 찾기 (lower/upper bound)mid 값을 기준으로 문제의 조건을 판별 → 범위를 조절해 나가는 문제🧠 예시 코드 (정수 제곱근 문제)long long left = 0, right = n;while ..

🔍 문제 요약문제링크 : [백준 24444번]주요 태그 : BFS, 너비 우선 탐색정점 N개, 간선 M개로 구성된 무방향 그래프가 주어졌을때, 시작 정점 R에서 너비 우선 탐색(BFS)을 수행하고, 각 정점의 방문 순서를 출력한다. 인접 정점은 오름차순으로 방문해야 하며, 시작 정점에서 도달할 수 없는 정점은 0을 출력한다.💡 문제 분석그래프가 무방향이며, 인접 정점은 오름차순으로 방문해야 한다.정점의 수는 최대 100,000개, 간선은 200,000개 → O(N + M)BFS를 이용하되, 방문 순서를 기록해야 하므로 단순 방문 여부가 아닌 방문 순서 배열을 사용해야 한다.🔑 아이디어그래프 표현: 인접 리스트 (vector>)방문 순서 기록: visited[i] = 방문 순서BFS 구현: 큐(qu..

🔍 문제 요약문제 링크: 백준 13023번 - ABCDE주요 태그: DFS, 백트래킹, 그래프 탐색💡 문제 분석총 N명(0 ~ N-1)이 참가한 알고리즘 캠프에서 친구 관계가 M개 주어진다.관계 A-B-C-D-E와 같은 연속된 5명의 친구 관계가 존재하는지 확인해야 한다.A-B B-CC-DD-E🔑 아이디어DFS를 활용하여 모든 노드에서 깊이 4까지 탐색한다. (간선 4개)경로 탐색 중 동일한 사람을 중복해서 방문하지 않기 위해 visited[] 배열을 활용깊이 4에 도달하면 즉시 종료하도록 flag 사용탐색을 마친 후에는 visited[]를 원래 상태로 복구 (백트래킹)🧩 풀이 전략인접 리스트 방식의 그래프 방식으로 푼다.모든 노드에서 DFS를 시작하면서 깊이 0부터 탐색방문한 노드는 visite..

🔍  문제 요약문제 링크: 백준 9419 - 프로그래밍 대회 전용 부지상근이의 목표상근이는 해마다 땅을 하나씩 사면서, 모든 땅을 최소 비용으로 사들이려 한다.1년이 지날 때마다 땅값은 두 배로 상승하므로, 더 비싼 땅일수록 먼저 사야 전체 비용이 줄어든다.조건매년 1개 땅만 구입 가능 (1년 후부터)가격은 2 × L × t^t로 증가 (L은 땅값, t는 구매한 해의 번호)총 보유 금액: 5,000,000 억원목표: 주어진 테스트 케이스마다 땅을 모두 구입할 수 있는지, 최소 비용을 출력한다.💡 문제 분석가격은 매년 기하급수적으로 증가하기 때문에, 비싼 땅부터 먼저 구매해야 최적의 해법각 테스트 케이스는 0으로 끝나며, 최대 40개의 땅 → O(n log n) 정렬 후 계산 가능단위가 억이고, 총 예..