전체 글
15732번-도토리숨기기
문제 https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 접근방법 이 문제는 어떤 것을 탐색 기준으로 삼아야 할 지 어려웠던 문제였다. 탐색 기준은 "박스의 최대 길이"로 설정하여서 이분 탐색을 수행하였다. 박스의 최대 길이와 규칙에서 더 짧은 기준을 선정하여 check 함수 탐색의 right값을 설정하였다.(앞에서 부터 갯수를 세는 문제 조건) 그 이후 mid ..
이분탐색 구현 팁 및 반환값 줄이기(부제: 공부하며 정리하는 생각들)
공부하면서 참조한 자료 1.종만북 2. https://blog.naver.com/jinhan814/222156334908 이분 탐색, 파라메트릭 서치 안 헷갈리는 TIP 예전에 종만북을 읽으면서 아래 글을 쓴 적이 있습니다. 아래 글에는 반복문 불변식을 이용해 lower_bound,... blog.naver.com 이분탐색은 문제에서 주어지는 탐색 값의 기준을 찾는 것이 문제이다. 예를 들어 1부터 10억cm의 길이의 자를 분할해서 최소 5개의 개수로 나누고 싶은데 이 때 "분할하는 경우에 가장 큰 분할 길이를 구하시오" 같은 문제에서 분할하는 길이를 구하면 되는 문제이다. 알고리즘에 관련된 설명과 강의는 나보다 뛰어나신 분도 너무 많고 작성하시는 분도 너무 많기에 넘어가고 이분탐색을 구현할 때 구현의 ..
16434번-드래곤앤던전
문제 https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 접근방법 n의 단위가 100,000만 이므로 n^2의 알고리즘은 시간초과가 발생한다는것을 깨닫고 O(logn으로 시간복잡도를 줄여야 하는 문제란걸 문제의 조건을 읽고 알아야 하며 H의 범위가 1,000,000인데 최대 연산이 발생할 경우 INT의 범위를 초과하기에 자료형을 long long으로 설정해줘야 하는 문제이다. 문..