[유형]이분탐색 [문제링크]https://school.programmers.co.kr/learn/courses/30/lessons/64062 [요약]디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요. [문제풀이]mid : 징검다리를 건널 수 있는 최대 인원cnt : 건너지 못하는 연속된 돌의 개수stone stone > mid : mid가 stone을 모두 건널 수 있으므로, 건너지 못하는 연속된 돌의 개수를 0으로 초기화한다.cnt >= k :징검다리를 건널 수 있는 최대 인원을 줄여야 한다는 의미이고cnt def solutio..

[유형]이분탐색 [문제링크]https://www.acmicpc.net/problem/1300 [요약]세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. [문제풀이]N=3, 7보다 작거나 같은 수를 생각해보면1행의 경우, 1*1~1*3까지 3개, 2행의 경우, 2*1~2*2까지 2개,3행의 경우, 3*1~3*2까지 2개이다. temp에 저장된 값이 K개보다 많거나 같으면, mid 값을 줄이고K보다 적으면 mid 값을 늘린다.import sysfrom collections import defaultdictdef input(): return sys..

[유형]이분탐색 [문제링크]https://www.acmicpc.net/problem/2110 [요약]C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. [문제풀이]start = 공유기 간의 거리 최솟값end = 공유기 간의 거리 최댓값start와 end의 중간 값인 mid를 구하고, 탐색을 시작한다.공유기의 갯수가 C보다 크다면, 거리를 넓혀야하므로 mid+1을공유기의 갯수가 부족하다면, 거리를 좁혀야하므로 mid-1을 해준다.import sysfrom collections import defaultdictdef input(): return sys.stdin.readline().rstrip()homes = []N, C = map(i..

[유형]이진분류 [문제링크]https://www.acmicpc.net/problem/1654 [요약]첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오. [문제풀이]start =1, end=가지고 있는 랜선 길이 중 가장 긴 랜선의 길이mid = (start + end)//2의 길이로 랜선을 자를 때, N개 보다 많다면 mid보다 더 크게 잘라도 되는지 확인하기 위해 start = mid+1을 한다. N개의 랜선을 만들 수 없다면 mid보다 더 작게 자르기 위해 end = mid-1..

[유형]이진탐색 [문제링크]https://www.acmicpc.net/problem/7453 [요약]정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. [문제풀이]a+b+c+d = 0이므로, a+b = -(c+d)이다.따라서, dict을 사용해서 a+b를 key에 추가하고, -(c+d)를 key로 가지는 dict이 존재한다면, value만큼 answer에 더해주면 된다.하지만, 처음에 이 방법을 사용했더니 시간초과가 발생하였다.import sysfrom collections import defaultdictdef input(): return sys.stdin.readlin..

[유형]이분탐색 [문제링크]https://www.acmicpc.net/problem/10816 [요약]숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. [문제풀이]collections의 Counter를 사용한다.import sysfrom collections import Counterdef input(): return sys.stdin.readline().rstrip()list_n = []list_m = []n = int(input())list_n = list(map(int, input().split()))m = int(input())list_..