몽상실현개발주의

[BOJ] 10815 / 숫자 카드 / Python 파이썬 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 주어진 숫자만큼 이분탐색을 연속으로 하는 문제이다. for 문 안에서 이분탐색을 진행하여 간단하게 풀었다. N = int(input()) cards = list(map(int, input().split())) cards.sort() M = int(input()) nums = list(map(int, in..

[BOJ] 2110 / 공유기 설치 / Python 파이썬 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 풀이 방법을 떠올리기가 힘들었던 이진탐색 문제였다. "공유기 사이의 거리를 최대로 하는 설치 간격" 을 찾는 문제인데 이 조건을 "집 사이의 간격이 X 이상이 가능한 집의 수 == 공유기 대수" 로 다시 생각하여야 풀 수 있었다. 집 사이의 간격을 이진탐색으로 찾기 간격을 주어진 집..

[BOJ] 2805 / 나무 자르기 / Python 파이썬 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 이진탐색의 기본 문제이다. 주어진 나무의 높이들을 빼주면서 결과를 비교하여, 탐색 범위를 좁혀 주는 방식으로 이진탐색을 하였다. res = M : 자를 높이 증가 N, M = map(int, input().split()) trees = list(map(int,..

[BOJ] 1654 / 랜선 자르기 / Python 파이썬 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이분 탐색의 기본 문제이다. 첫 시도는 완전 탐색으로 접근하였지만 당연히 시간초과가 발생 하였다. 가장 기본적인 이분 탐색의 구조로 해결 하였다. import sys input = sys.stdin.readline K, N = map(int, input().split()) lines = [] for _ i..