Problem Solving/이진 탐색

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net Map 이용 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); HashM..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 시간을 많이 소모하였다. 1. min값 설정을 잘못하였다. 합의 범위는 곱하기2 +1 을 해주어야 한다. 2. 출력 오름차순을 하지 않앗다. 3.서로 다른 용액을 골라야 한다. -> 이분탐색에서 조건문으로 처리해주어야 한다. 음수일 경우 left를 m+1로 하는 등 import java.util.*; import java.io.*; public class Main..

https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net SET 자료형을 이용할수도 있지만 이번엔 이분탐색 메소드를 이용해보았다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new Inpu..

조사범위를 좁혀가면서 조사하는 알고리즘 직접구현 java 메소드 이용 존재한다면 해당 인덱스값 반환 없으면 음수 반환

https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 난이도:실버1 소요시간:60분, 반례힌트 사용함 아래는 나의 코드인데 구현자체는 빠르게 하였다. 그런데 테스트케이스는 통과를 하는데 채점시 자꾸 틀리는 것이였다. 반례를 계속 찾아보았지만 찾지못하여 다른사람의 반례를 참고하였다. 그 이유를 찾으니 이분탐색 시작점을 동영상길이의 최대값으로 하였어야 하는데 동영상길이가 디스크보다 클수 없다는 것을 간과하고 min으로 동영상 최솟값으로 설정한게 원인이였다.....

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 난이도: 실버2 소요시간: 60분, 엣지케이스 관련 힌트 참고함 최대로 나올수 있는 값을 end로 정했다. 1~end를 이분탐색하여서 정답을 찾았다. import sys K,N = map(int,sys.stdin.readline().split()) end=0 cableList=[] for _ in range(K): temp=int(sys.stdin.readline())..

이 문제는 이것이 코딩테스트다 201페이지 문제이다. 이 문제는 구현자체는 쉽지만 입력의 최대값이 20억이여서 최악의 경우 최대 20억의 실행이 발생할 수있다. 그러므로 이진탐색을 사용하여야 한다. 아래는 나의 코드이다. # 떡의 개수(N)와 요청한 떡의 길이(M)을 입력 n, m = list(map(int, input().split(' '))) # 각 떡의 개별 높이 정보를 입력 array = list(map(int, input().split())) # 이진 탐색을 위한 시작점과 끝점 설정 start = 0 end = max(array) # 이진 탐색 수행 (반복적) result = 0 while(start mid: total += x - mid # 떡볶이 양이 부족한 경우 더 많이 자르기 (오른쪽 부..

이 문제는 이것이 코딩테스트다. p197페이지 문제이다. 이진탐색을 이용하지 않고도 쉽게 풀 수 있기만 오늘은 이진탐색을 연습하는 날이기에 이진탐색을 이용하여 풀었다. 이진탐색을 구현할 수만 있다면 문제의 난이도는 쉽다. 아래는 나의 코드이다. import sys seller_N = int(sys.stdin.readline().rstrip()) seller = list(map(int,sys.stdin.readline().split())) customer_N=int(sys.stdin.readline().rstrip()) customer=list(map(int,sys.stdin.readline().split())) seller.sort() def search(searchList,target): low=0 h..