joseph0528 코딩 블로그

이분 탐색이란 이름 그대로 두 개로 나누어 탐색을 한다는 것이다. 기본적인 구조는 분할정복과 유사하지만, 반을 나누고 둘 중 한쪽으로만 탐색을 진행한다는 점에서 차이가 있다. 그럼 이분탐색은 어떻게 진행하는지 알아보자. 이분 탐색의 가장 대표적인 예로 Up, Down 게임이 있다. Up, Down 게임은 상대방이 어떤 숫자를 생각하면, 도전자가 숫자를 예측하며, 상대방은 그 숫자에 대해 Up, Down을 말한다. 그럼 이 방법에서 최소한의 횟수로 정답을 맞추는 방법은 뭘까 바로 내가 말할 수 있는 숫자의 범위 중, 정확히 반에 해당하는 숫자를 말하는 것이다. 게임을 통해 예시를 들어보자. 해당 게임에서는 상대방이 77이라는 숫자를 생각하였고, 우리는 그 숫자를 맞추기 위해 숫자를 부를 것이다. 일단 우리..

https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 간단한 세그+이분 탐색 문제이다. 처음 봤을 땐 이게 어떻게 세그로 되는 건지 싶을 수 있지만 간단한 세그로 풀수 있다. 일단 1번쿼리는 나중에 생각하고 2번 쿼리부터 보자 2번 쿼리같은경우 b맛의 사탕을 c개 넣는 거니까 b, b구간에 c를 더하는 거와 같다 마이너스여도 코드에는 변화가 없으니 그냥 한 구간에 c를 더해주면 된다. 여기까진 쉬운데 1번 쿼리에서 b번째 사탕..

solved.ac 티어 : 골 4 https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 오랜만에 시험 끝나고 돌아왔다 당연히 시험은 망했고 오랜만에 와서 풀이를 쓸려고 한다 이 문제는 KOI 2013 중등, 고등 1번 문제이다 이 문제는 자명 풀이가 이분 탐색(binary search)이라는데 그것보다 스위핑처럼 하는 방법이 먼저 떠올라 그걸로 풀었다 방법은 이분 탐색만큼 간단한데 동물들의 점..

solved.ac 티어 : 골드 3 www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 이문제는 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 나올 수 있는 최대 개수를 구하는 것이다. 이때 이문제에서 꼬이지 않게 하려면 i번째의 값보다 i+1번째 값이 더 커야 된다. 즉 이문제는 LIS(최장 증가 부분 수열)이라는 거다. 그러므로 이분탐색 LIS를 구해주면 된다. import sys sys.setrecursionlimit(10000..