알고리즘/이분탐색5

• 

  [백준] 1074번: Z - java 나의 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, R, C, cnt; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextT.. 알고리즘/이분탐색 2023. 2. 20.

• [프로그래머스] 가사 검색 - 파이썬(python) 문제 설명 친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다. 그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다. 가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지.. 알고리즘/이분탐색 2022. 10. 18.

• [백준] 2110번: 공유기 설치 - 파이썬(python) 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는.. 알고리즘/이분탐색 2022. 10. 18.

• 

  [프로그래머스] 징검다리 - 파이썬(python) 도저히 이분탐색으로 푸는 방법을 생각해내지 못해, 다른 분들의 풀이를 참고하여 아이디어를 얻은 채, 다시 코드를 작성하였다. 풀이 def solution(distance, rocks, n): answer = 0 start, end = 0, distance rocks.append(distance) # 맨 뒤 거리도 계산할 수 있도록 한다 rocks.sort() # 바위 정렬 #이분 탐색 while start 바위 간격의 최솟값 del_stones = 0 # 제거한 돌 개수 pre_stone = 0 # 기준이되는 돌(시작지점) min_dis = distance for rock in rocks: dis = rock - pre_stone # 현재 바위 - 이전 바위 사이 간격 if dis < mid: # 돌사이.. 알고리즘/이분탐색 2022. 9. 24.

• 

  [프로그래머스] 입국심사 - 파이썬(python) 나의 풀이 def binarySearch(left, right, n, times): answer = right while left = n : answer = min(answer, mid); right = mid - 1 else : left = mid + 1 return answer def solution(n, times): min_time = 0 max_time = max(times) * n answer = binarySearch(min_time, max_time, n, times) return answer 이분탐색은 탐색하는데 걸리는 시간이 O(log N) 이기 때문에, 탐색해야 하는 input 이 아주 큰 숫자일 때 사용하기 좋다. 따라서, 위 문제에서도 심사를 하는데 걸리는 시간을 기준으로 이분탐색.. 알고리즘/이분탐색 2022. 9. 24.