binary search

[3020] 개똥벌레(C++)

문제 3020번: 개똥벌레 문제 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석�� www.acmicpc.net 해결 방법 1. 석순의 길이는 입력받는 값 그대로 stalagmite 배열에 저장 2. 종유석의 길이는 바닥과 종유석까지의 거리로 변환(동굴의 높이 - 종유석 길이)하여 stalactite 배열에 저장 3. stalagmite, stalactite 배열을 각각 오름차순 정렬 4. 1번째 구간부터 동굴의 높이와 같은 구간까지 탐색하며 해당 구간에서 석순과 종유석과 각각 몇 개씩 만나는지 계산! 이때 lower_bound() 함수를 사용하여 만나는 개수를 바..

[1920] 수 찾기(C++)

문제 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 해결 방법 1. n개의 정수를 배열 a에 입력받는다. 2. 배열 a를 오름차순으로 정렬한다. 3. 배열 a에 존재하는지 알고싶은 숫자들을 하나씩 입력받으면서 직접 구현한 binsearch 함수를 실행한다. (binsearch 함수는 그냥 일반적인 binary search 함수로 구현하면 된다.) 이 문제에서 핵심은 '시간 초과'가 나지 않도록 하는 것이었다. 처음에는 cin, cout, sort()를 사용하여 코..

[2512] 예산

문제 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. www.acmicpc.net 처음엔 코드도 60줄이 넘고 내가 생각하기에도 코드가 너무 복잡한 것 같은데 제출 결과도 계속 틀렸다고 떠서 뭐가 문제일까 생각해봤더니 예외 테스트케이스가 있었다... 이분 탐색 문제였기 때문에 자꾸만 어떤 표본들의 중간값을 찾으려고 했던 탓이다. 예를 들어, 각 지방에서 요청한 예산이 100, 110, 120, 130 ..

[2872] 우리집엔 도서관이 있어(C++)

문제 바로가기 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근이는 책을 알파벳 순서대로 정렬하려고 한다. 사전 순으로 가장 앞서는 책은 가장 위에 놓고, 가장 뒤에 있는 책은 가장 밑에 놓아야 한다. 책을 정렬할 때 사용할 수 있는 방법은 책 하나를 뺀 다음, 가장 위에 놓는 것이다. 책은 1부터 N까지 번호가 책 이름의 사전 순으로 매겨져 있다. 1은 사전 순으로 가장 앞서는 책이다. 따라서, 위에서부터 책의 번호를 읽으면 (1, 2, ..., N)이 되어야 한다. 예를 들어, 책이 3권있고 처음에 (3, 2, 1)로 쌓여있을 때, 2번 만에 사전순으로 책을 쌓을 ..

분할 정복(Divide and Conquer)

[1654] 랜선 자르기

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다. www.acmicpc.net 🔎 해결 방법 [2110] 공유기 설치와 정말 정말 유사한 문제이다. 코드도 거의 복붙 수준 ㅋㅋ 1. left = 1, right = (가장 긴 랜선의 길이)로 선언 2. left left, right, mid, answer 모두..

[2110] 공유기 설치

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. www.acmicpc.net 🔎해결 방법 1. 집의 좌표를 입력받은 뒤, 오름차순으로 정렬 2. left = 1, right = 첫번째, 마지막 집 사이의 거리, mid = 가장 가까운 집 사이의 거리 이렇게 선언한 뒤, check 함수에서 router 함수를 계속 호출한다. 1) router 함수 처음 호출 2) 두번째 호출 3) 세번째 호출 4..