이분탐색
1.[백준] 2805번 - 나무 자르기
아이디어 이진탐색으로 접근해야 했지만 일단 가장 먼저 떠올랐던 생각은 부등식을 세워 최댓값(정수)을 구하는 방법이었다. 어떻게 이진탐색을 활용해야 할지가 고민이었는데 구매했던 도서의 예제 문제에서 답을 찾을 수 있었다. 중요 포인트 (책 내용 발췌) 1) 이러한 문제의 유형은 parametric search 유형의 문제이며 이는 최적화 문제를 결정 문제로...
2.[백준] 1654번 - 랜선 자르기
아이디어 나무 자르기 문제와 너무 유사했다. 단지, 체크해야 하는 부분이 다르다는 점? 나무 자르기는 자른 나무를 합한 값을 체크해야 했고, 랜선 자르기는 랜선의 수를 체크해야 했다. 따라서, 나무 자르기에서는 check값에 (나무 - mid)값을 넣어주었다면, 랜선 자르기에서는(랜선 // mid)값을 넣고 비교하였다. 1차 시도 런타임 에러 발생 (Z...
3.[백준] 3079번 - 입국심사
아이디어 이분탐색 문제에서 중요하다고 생각되는 점 1) 시작, 끝 점을 어떤 값으로 지정할 것 인지 2) 최솟값, 최댓값을 구하기 위한 check값을 어떻게 지정할 것인지 3) start,end 값 변경 조건 이 문제에서 start값은 문제 조건에 의해 1로 두었고, end값은 오래 걸리는 심사관한테 계속 심사받는 경우라고 생각하여 M * max(dela...
4.[백준] 2110번 - 공유기 설치
아이디어 거리의 최댓값을 구하는 문제이므로 start, end값도 거리값으로 지정해주었다. start = 1 end = 가능한 최댓값 (맨 끝집 사이의 거리) 나머지 과정은 이분탐색 패턴과 동일하다. 이 문제에서 새로웠던 점은 가장 인접한 공유기 사이의 거리의 최댓값을 구해야 하기 때문에 최댓값을 발견하면 기존 값(check(공유기 수), home_che...
5.[백준] 2512번 - 예산
요청 배정여부에 따른 조건문을 제외하고는 지난주에 풀었던 이진탐색 코드와 매우 유사했다. 모든 요청이 배정될 수 없는 경우에 mid값을 상한액으로 생각하여 최대 상한액을 찾는 방식으로 구현했다.
6.[백준] 2776번 - 암기왕
아이디어 이진 탐색을 진행하기 위해 정렬 작업을 진행해줘야 함 타겟값 발견시 mid 반환, 발견 못하면 None 반환 코드
7.[백준] 1072번 - 게임
계산법의 문제 : 100을 나중에 곱해주면 오차가 발생하기 때문에 미리 곱해주는 방식을 택함승률이 99이상일 경우 z값이 변화하지 않기 때문에 -1 출력
8.[백준] 2343번 - 기타 레슨
최대 기타 강의 길이보다 mid값이 작은 경우\-> start값을 mid+1값으로 수정하고 넘어가도록 하였다나머지 부분은 일반적인 이진탐색과 동일했다.
9.[백준] 6236번 - 용돈 관리
기타 레슨과 동일한 문제 min값 지정만 list.append방식이 아닌 min함수를 활용한 방식으로 변경하였다.
10.[백준] 2110번 - 공유기 설치
공유기 설치