이분 탐색과 깊이 우선 탐색 기반 문제 해결
T1. 이분 탐색: 정렬된 배열에서 값 찾기
정렬된 배열 내에서 특정 값을 찾아 그 인덱스를 반환하는 문제입니다. 배열 크기가 최대 106까지 가능하므로, 배열 선언 시 크기를 충분히 확보해야 합니다.
오류 원인: 배열 크기 지정이 부족 (105+7로 설정했으나, 106+7 필요)
핵심 전략: 이분 탐색은 값이 일치할 경우에도 왼쪽 경계를 찾기 위해 r = mid로 업데이트
#inc ...
6월 25일 21:05에 게시됨
코드포스 라운드 988 (Div. 3) 문제 해설
A. 동일 숫자 페어 계산
배열 요소의 빈도를 저장하는 카운터를 활용하여 동일한 숫자 쌍의 최대 개수를 계산합니다. 각 숫자에 대해 발생 횟수를 2로 나눈 몫을 합산하여 해결합니다.
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int testCase ...
6월 23일 03:04에 게시됨
트래킹 세그먼트 (이분 탐색, 구간 누적합)
문제 설명
n개의 0으로 초기화된 배열 a가 주어집니다. 또한 m개의 구간이 주어지며, 각 구간은 l_i와 r_i(1 ≤ l_i ≤ r_i ≤ n)로 정의됩니다. 이는 배열 a의 부분 배열 a[l_i], a[l_i+1], ..., a[r_i]를 의미합니다.
특정 구간에서 1의 개수가 0의 개수보다 크다면 해당 구간을 아름다운 구간이라고 합니다. 예를 들어, a = [1, 0, 1, 0, 1]인 경우 구간 [1, 5]는 1이 3 ...
5월 31일 13:04에 게시됨
전화선 최소 비용 계산
문제 개요
농부 존은 자신의 농장에 전화선을 설치해야 한다. 그러나 통신사의 협조가 부족하여, 일부 전화선은 비용을 지불해야 한다.
전체적으로는 N (1 ≤ N ≤ 1,000)개의 전화 기둥이 있으며, 각각 1부터 N까지 번호가 매겨져 있다. 현재는 아무 기둥도 연결되어 있지 않다.
총 P (1 ≤ P ≤ 10,000)개의 기둥 쌍 사이에 전화선을 설치할 수 있으며, 나머지는 거리가 너무 ...
5월 22일 02:20에 게시됨