이분탐색

🗂️ 문제문제김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.게임 기록은 다음과 같이 생겼다.게임 횟수 : X이긴 게임 : Y (Z%)Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라..

🗂️ 문제문제현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.입력1번째 줄에는 N과 M이 공백으로 ..

🗂️ 문제https://www.acmicpc.net/problem/2512 💡 접근법총 예산이 예정 예산을 초과할 경우 예산의 상한액을 설정해야 하며, 이때 이분탐색을 사용한다.하지만 만약 모든 예산이 배정될 수 있는 경우에는 상한액을 설정할 필요가 없으니 예산의 최댓값을 리턴한다. 이분탐색을 위해 low=1, high는 예산들 중 최댓값으로 설정한다. 이때 mid를 통해 상한액을 정하고,상한액보다 적은 예산은 그대로 예산을 적용하되, 상한액을 초과하는 예산은 상한액으로 금액을 산정하여 예산의 합을 계산한다. 만약 예산의 합이 총 예산보다 크다면, 상한액을 더 내려야 하므로 high 값을 mid-1로 조정한다. 만약 예산의 합이 총 예산보다 작다면, 이는 상한액을 더 올려야 하므로 low 값을 mid..

🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 접근법바위 사이의 거리의 최솟값을 기준으로 이진 탐색의 범위를 조절해야 한다. low는 distance의 바위 사이 거리의 최솟값인 1로, high는 바위 사이 거리의 최댓값인 distance로 설정한다. mid를 바위 사이 거리의 최솟값으로 생각하고 탐색을 진행한다. 이때 바위 사이의 거리의 최솟값 중 최댓값을 구하는 것이 목표이다. 따라서 바위 사이의 거리를 구하고, 구한 ..

🗂️ 문제링크: https://www.acmicpc.net/problem/10815 💡 접근법이분탐색 시 탐색 범위를 설정해야 한다. 해당 문제에서는 카드 리스트를 정렬하고, 카드 리스트 인덱스의 최솟값(0)과 최댓값(len(card_list)-1)을 low와 high로 각각 지정한다. mid의 값을 변경하며 탐색한다. 이때 카드 리스트에서 mid 인덱스에 해당하는 값보다 상근이가 가지고 있는 숫자가 작으면 mid 값을 줄여야하므로 high = mid - 1로 설정한다. 반대의 경우엔 mid 값을 키워야하므로 low = mid + 1로 설정한다. 만약 카드 리스트에서 mid 인덱스에 해당하는 값이 상근이가 가지고 있는 숫자와 같다면 1을 저장한다. 😎 내 코드import sysN = int(sys...

🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=python3# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 접근법문제에서 원하는 것은 모든 사람이 심사를 받는데 걸리는 시간이므로 start와 end 그리고 mid 모두 시간에 관련된 변수라고 짐작할 수 있다. 즉, 입국 심사에 걸리는 최소 시간과 최대 시간을 의미하므로 low는 1로 지정하고 high는 max(times) * n로 지정한다. 탐색할 범위를 지정했으므로 mid 값을 변경시켜 값을 확인해야..

🗂️ 문제링크: https://www.acmicpc.net/problem/1654 💡 접근법“N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.”라는 문제 조건에 따라 이분탐색의 기준을 필요한 랜선 개수 이상인지 이하인지 따라 범위를 좁혀나간다. 따라서 만들 수 있는 랜선의 수가 N개일 때 종료조건을 걸지 않고 계속해서 범위를 좁혀나가면서 최대의 랜선 길이를 구한다. 더이상 탐색 범위가 좁혀지지 않을때 high 값이 가장 긴 랜선의 길이가 되어 출력된다. 😎 내 코드import sysK, N = map(int, sys.stdin.readline().split())line = [int(sys.stdin.readline()) for _ in range(K)]def cal_line_num(heigh..

🗂️ 문제링크: https://www.acmicpc.net/problem/2805 💡 접근법N과 M의 범위가 크기 때문에 모든 경우의 수를 계산할 경우 시간초과가 발생한다. 절단 높이를 작게하면 가져가는 나무의 길이가 크고, 절단 높이를 크게하면 가져가는 나무 길이기 작다.이를 이용하여 절단 높이를 기준으로 이분 탐색을 수행한다. 또한 절단 높이를 최대로 하여 필요한 만큼의 나무를 가져가므로, 나무의 길이가 딱 떨어지지 않는 경우를 생각해야 한다. 이 경우엔 high(mid-1) 값을 출력하면 필요한 만큼 나무를 가져가면서 최대로 하는 절단 높이를 구할 수있다. 😎 내 코드import sysN, M = map(int, sys.stdin.readline().split())tree = list(map(..