Most Muscular Most Muscular

기출 : BOJ #2110 변경할 값은 인접 공유기 사이의 최대 거리이고 체크할 함수는 해당 거리일 경우 설치 가능한 공유기의 개수를 출력한다 공유기 개수가 목표한 값보다 큰경우 답을 갱신하고 범위를 줄여 다시 탐색한다 answer = 0 n,c = map(int,input().split()) h = list() for _ in range(n): h.append(int(input())) h.sort() def check(val): global h res = 1 ex = h[0] for p in h: if p>=ex+val: res += 1 ex = p return res def bs(st, en, target): global answer if st>en: return -1 mid = (st+en)//2 ..

기출 : BOJ #1654 변경할 값은 랜선의 길이이고 체크할 함수는 만들 수 있는 랜선의 개수를 출력한다 최댓값을 출력하기 때문에 범위를 줄여가면서 최댓값을 갱신한다 # input answer = 0 k, n = map(int,input().split()) lan = list() for _ in range(k): lan.append(int(input())) # sort lan.sort() def check(val): global lan, n res = 0 for l in lan: res += (l//val) return res def bs(st, en, target): global answer if st>en: return -1 mid = (st+en)//2 val = check(mid) if val>..

기출 : BOJ #1920 이진 탐색 문제의 정석같은 문제이다 이전에 풀었던 숫자 카드 문제와 완전히 동일하다 # input n = int(input()) a = list(map(int,input().split())) m = int(input()) check = list(map(int,input().split())) # sort a.sort() def bs(st, en, target): if st>en: return False mid = (st+en)//2 if a[mid]==target: return True elif a[mid]>target: return bs(st, mid-1, target) else: return bs(mid+1, en, target) # search for val in check..

기출 : BOJ #10815 변경할 값은 상근이가 가지고 있는 카드의 값이고 체크할 함수는 없다 (크기만 비교) answer = "" n = int(input()) cards = list(map(int,input().split())) m = int(input()) check = list(map(int,input().split())) cards.sort() def bs(st, en, target): if st>en: return False mid = (st+en)//2 if cards[mid]==target: return True elif cards[mid]

기출 : BOJ #2805 일반적인 이진 탐색 문제처럼 다음 두 가지를 먼저 확인해야 한다 1. 변경할 값 2. 체크할 함수 변경할 값으로는 절단기의 높이를, 체크할 함수로는 잘린 나무의 합산을 설정했다 # input n,m = map(int,input().split()) tree = list(map(int,input().split())) answer = 0 tree.sort() # target 이상인 값들의 합을 출력 def check(target, li): sum = 0 for val in li: if val>=target: sum+=(val-target) return sum # st~en 사이의 값에 대해 탐색 def bs(st, en, target): global answer if st>en: r..

기출 : BOJ #1072 이진 탐색의 핵심은 다음과 같다 1. 값을 변경할 변수 설정 2. 값을 변경하면서 체크할 함수 설정 이 문제에서는 추가적으로 진행할 게임 수가 변경할 값이고 승률 계산 함수가 체크할 함수이다 추가적으로 고려해야할 것은 승률 계산시 소수점 버리기 함수(trunc), 99퍼센트일때 예외 처리이다 from math import trunc answer = -1 x, y = map(int,input().split()) z = trunc(y*100/x) # 승률 계산 def check(val): return trunc((y+val)/(x+val)*100) # 이진 탐색 def bs(st, en, target): global answer, z if st>en: return -1 mid = ..

기출 : 2020 카카오 신입 공채 1차 이 문제를 풀면서 정말 가장 많이 배우는 것 같다 지금까지 문자열을 다루는 어려운 문제들은 풀어본 적이 없었다 이 문제는 거의 외우다시피 해야 할 것 같다 일단 문제 풀이의 아이디어는 다음과 같다 1. 주어진 단어들을 길이별로 나눈 뒤 정렬하여 저장한다 2. 주어진 단어들을 리버스하여 1의 과정을 반복한다 3. 각 쿼리들에 대해 접두사/접미사 여부, 쿼리의 길이에 따라 카운트한다 이 문제를 풀면서 알고리즘 팀 노트의 필요성을 느꼈다 countByRange 함수, replaceAll 함수 등은 다른 문제에서도 자주 쓸 것 같아서 팀 노트를 작성했다 #include using namespace std; int countByRange(vector &v, string f..

기출 : 백준 #2110 이진 탐색, 그 중에서도 파라메트릭 서치를 사용하는 문제이다 이 문제를 통해 내가 파라메트릭 서치 유형에 정말 약하다는 것을 많이 느꼈다 앞으로 파라메트릭 서치 유형의 문제를 많이 풀어볼 것이다 일단 파라메트릭 서치 문제를 해결 할 때 반드시 해야 할 것이 있다 최적화 문제를 결정 문제로 바꾸어 해결할 수 있는가?? 위 질문에 대답할 수 있다면 다음 단계로 넘어갈 수 있다 최적화 문제란 주어진 조건을 만족하는 최솟값, 최댓값 같은 것을 구하는 문제이다 결정 문제란 주어진 조건을 만족하는 아닌지 두 가지로 판단하는 문제이다 이 문제의 경우 조건은 N개의 공유기를 설치하는 것이고 구하는 것은 인접 공유기 거리의 최댓값이다 결정 문제로 바꾸면 인접 공유기 거리의 최댓값을 변화시키며 N..