Coding Test/Search

[3079] 입국심사 (이분 탐색)

3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net """ 입국심사대는 총 N, 상근이와 친구들은 총 M k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk 상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) 2 6 7 10 """ n,m=map(int, input()..

[1477] 휴게소 세우기 (이분 탐색)

1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄 www.acmicpc.net 분석 풀이 """ 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다. 다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.) 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에..

[1300] k번째 수 (이분탐색, 2차원 배열)

1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 분석 n=3, k=7로 가정 중앙값보다 작거나 같은 수의 개수 = 중앙값을 N으로 나눈 값 1. 최초의 중앙값 : 4 = (1+7)/2 1*1 = 1 1*2 = 2 1*3 = 3 1행 : 4/1 = 4지만 행의 크기가 3개이므로 3 2*1 = 2 2*2 = 4 2*3 = 6 2행 : 4/2 = 2 3*1 = 3 3*2 = 6 3*3 = 9 3행 : 4/3 = 1 cnt를 다 더하면 5이므로 k(7)보다 작음 => 중앙값을 증가시킴 ..

[2343] 기타 레슨 (블루레이 만들기, 이진탐색)

2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 분석 뮤직비디오 (이분탐색, 결정 알고리즘) 문제 DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 순서가 그대로 유지되어야 한다. 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. M개의 DVD에 모든 동영상을 녹화하기로 하였다. DVD karla.tistory.com 풀이 n,m=map(int,input().split()) a=list(map(int,input().split())) start=end=0 for i in a: if startm: sta..

마구간 정하기 (이분탐색, 결정 알고리즘)

문제 N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력 자연수 N(3

뮤직비디오 (이분탐색, 결정 알고리즘)

문제 DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 순서가 그대로 유지되어야 한다. 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. M개의 DVD에 모든 동영상을 녹화하기로 하였다. DVD의 용량 크기는 (녹화 가능한 길이) 최소 DVD의 용량은 같은 크기여야함 곡 수 N(1≤N≤1,000), DVD 개수 M(1≤M≤N) 다음 줄에는 부른 순서대로 부른 곡의 길이(자연수, 분단위) 부른 곡의 길이는 10,000분을 넘지 않는다고 가정 DVD의 최소 용량 크기를 출력 9 3 1 2 3 4 5 6 7 8 9 설명 : 3개의 DVD용량이 17분짜리이면 (1, 2, 3, 4, 5) (6, 7), (8, 9) 이렇게 3개의 DVD로 녹음을 할 수 있다. 17분 용량보다 작은 용량으로는 3개의..

[1654] 랜선 자르기(이분탐색, 결정 알고리즘)

1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 분석 이분 탐색 문제 임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 출력 자연수 karla.tistory.com 풀이 import sys input=sys.stdin.readline k,n=map(int,input().split()) a=[] for _ in range(k): a.append(int(inpu..

이분 탐색

문제 임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 출력 자연수 N(3

사과나무(BFS, 격자탐색, 다이아몬드)

분석 풀이 """ 현수의 농장은 N*N 격자판, 각 격자안에는 한 그루의 사과나무가 심어저 있다, N의 크기는 항상 홀수 사과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자안의 사과는 새들을 위해서 남겨놓는다. 입력 첫 줄에 자연수 N(홀수)이 주어진다.(3

송아지 찾기(BFS : 상태트리탐색)

분석 풀이 """ 현수의 위치와 송아 지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 앞으로 1, 뒤로 1, 앞으로 5를 이동. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E, 직선의 좌표 점은 1부터 10,000 까지이다. 5 14 3 """ from collections import deque s,e=map(int, input().split()) # 출발점, 도착점 max=10000 # 좌표 최댓값 visited = [False]*(max+1) visited[s]=True # 시작점 방문 dist=[0]*(max+1) dist[s]=0 queue = deque() queue.append(s) while ..