목록Algorithm/Binary Search (8)
우노
문제 링크 https://www.acmicpc.net/problem/3079 풀이 m명을 심사할 수 있는 최소 시간을 찾기 위해, 이분 탐색의 범위를 [0 ~ m명을 모두 심사했을 때의 가능한 최대 시간]로 잡는게 핵심입니다. 자세한 알고리즘은 하단 예제 코드에 설명되어있습니다. 코드 import sys # 심사대의 개수와 심사를 받는 인원 n, m = map(int, sys.stdin.readline().split()) # 각 심사대의 심사 시간 arr = [] for _ in range(n): arr.append(int(sys.stdin.readline())) # m명을 심사할 수 있는 최소 시간을 찾기 위해 # [0 ~ m명을 모두 심사했을 때의 가능한 최대 시간]을 start, end 범위로 설정..
문제 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다. 그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다. 가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하..
문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 조건 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나..
문제 고정점(Fixed Point)이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때 a[2] = 2이므로, 고정점은 2가 됩니다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 고정점은 최대 1개만 존재합니다. 만약 고정점이 없다면 1을 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과'판정을 받습니다. 입력 조건 첫째 줄에 N이 입력됩니다. (1
문제 N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1, 1, 2 ,2 ,2 ,2, 3}이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 ‘시간 초과’ 판정을 받습니다. 입력 조건 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다. 1
문제 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어 높이가 19, 14, 10, 17cm 인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다. 손님이 왔을 때 요청한 총 길이가 M일 때, 적어도 M만..
문제 이미 정렬된 데이터 중에서 특정 원소가 몇 번째 위치에 존재하는지 출력하시오. 입력 예시 10 7 1 3 5 7 9 11 13 15 17 19 10 7 1 3 5 6 9 11 13 15 17 19 출력 예시 4 원소가 존재하지 않습니다. 풀이 탐색 시작 위치와 탐색 종료 위치를 반복적으로 좁혀가며, 중간값과 탐색값을 비교하면 됩니다. 또한, start 가 end 보다 커졌을때를 탐색 불가능으로 판단하면 됩니다. 예제 코드 # n(원소의 개수)과 search(찾고자 하는 값)를 입력 받기 n, search = map(int,input().split()) # 전체 원소 입력 받기 n_list = list(map(int,input().split())) def binary_search(start, end)..
문제 링크 https://www.acmicpc.net/problem/2110 풀이 중요한 부분 문제가 원하는 것은, 가장 인접한 두 공유기 사이의 거리가 최대인 것이지만, 결국, 모든 공유기들의 간격이 공평하게 설치되기를 원한다고 해석할 수 있습니다. 따라서, 모든 공유기들을 공평하게 설치할 수 있는 간격을 이분 탐색을 통해 찾아야합니다. 진행 순서 공유기 설치 좌표들을 오름차순으로 정렬합니다. 공유기를 설치할 수 있는 최소 간격과 최대 간격을 구한 뒤, 공유기를 가장 공평하게 설치할 수 있는 간격(mid)을 구합니다. 첫 번째 집에 공유기를 설치한 뒤, 첫 번째 집에서 나머지 집들 간의 간격을 확인하며, mid 이상으로 떨어져 있는 집을 탐색합니다. 첫 번째 집으로부터 mid 이상 떨어진 집을 찾은 경..