mondegreen

구하고자 하는 바를 기준으로 로직을 생각하니 금방 구현할 수 있었다. 여기서 구하고자 하는 건 질투심 즉, 가장 사탕을 많은 아이의 사탕 갯수이다. 사탕 갯수 배열을 두번만 돌아도 백억을 넘기 때문에 시간 초과가 발생할 것이고 이분 탐색을 활용해서 풀이한다. left는 [1, 10^9] 구간 중 1이 가장 적은 사탕의 수가 되고 가장 사탕의 수가 많은 종류를 한 아이가 다 받는 경우 즉, 10^9가 right이다. 이를 테스트케이스에 적용하면 색상별 사탕의 수를 입력 받고 해당 배열을 정렬하면 첫번째 원소에는 최소 질투심이 될 수 있는 수, 마지막 원소에는 최대 질투심이 될 수 있는 수가 담겨있다. 이를 통해 이분 탐색을 진행하고 중간 값인 m 값이 질투심이라고 가정했을 때, 반복문을 돌면서 해당 질투심..

[Part1-Chapter07-Clip10] - 백준 2110 공유기 설치 정말 어리석게도 이분탐색으로 공유기를 설치할 집을 찾고 있었다. 사실 이런 접근을 생각하지 못하고 있었다. 그래도 정리해보자면 우리가 구하고자 하는 값은 인접한 공유기가 가질 수 있는 최대 거리! 이 값을 이분 탐색으로 처리한다. left가 되는 가장 작은 값은 한 집에 한 공유기를 설치할 수 있고 연속된 두 집에 모두 공유기가 설치되어 있다면 그 경우 1이 된다. right 값, 즉 인접한 공유기 거리가 최대가 되는 경우는 집 배열을 오름차순으로 정렬했을 때 가장 첫 번째 원소와 가장 마지막 원소의 집에 공유기를 설치하는 경우다. 이렇게 이분 탐색을 진행하는데 임시 공유기 거리인 중간 값을 기준으로 공유기를 설치한다 가정하고 이..

[Part1-Chapter07-Clip09] - 백준 6236 용돈관리 항상 고민하는 부분인데 코드를 간결하게 작성하는 것이 필요하지만 또 한 편으로는 협업을 고려해 구체적으로 작성하다보면 내 코드는 줄줄이 길어지는 경우가 많더라. 아직은 후자를 기준으로 두고 작성하지만 이러다 불필요한 자료구조나 변수 선언으로 메모리 효율이 낮아질 것 같아 고민이다. 아래 코드는 기존의 이분 탐색과 크게 다르지 않다. 다만 금액이 이번에 지출해야 하는 금액보다 적게 남았을 때는 해당 금액을 반환하고 다시 인출한다는데 총 인출할 수 있는 금액이라는 게 정해져 있지 않기 때문에 로직적으로만 생각하면 결국 그냥 잔돈이 기본 인출금액으로 리셋되면 된다. 반대로 금액이 이번에 지출해야 하는 금액보다 많이 남았을 때가 고민되는 지..

[Part1-Chapter07-Clip07] - 백준 2805 나무 자르기 풀고 나니 간단해 보이는데 분기를 짜는데 조금 시간이 걸렸다. 일단 좀 특이한 점은 자르고자 하는 높이를 설정하고 나무가 잘라진 길이를 구할 때 나무를 일단 정렬하고 잘리는 나무들의 시작 인덱스를 이분탐색으로 구했다는 점이다. 기본적으로 자를 높이는 가져가고자 하는 나무 길이의 최솟값이 1이므로 가장 큰 나무의 길이보다 -1한 값을 r로 설정하고 모두 베어버리는 경우가 가장 긴 나무 길이를 가져 가는 것이므로 l 는 0으로 설정했다. 이분 탐색을 통해 가져가고자 하는 길이와 같은 경우, 짧은 경우, 긴 경우를 분기하여 로직을 구현했다. import java.io.*; import java.util.*; public class Ma..

[Part1-Chapter07-Clip06] 매개변수 탐색은 이분 탐색을 이용해 최적값을 탐색하는 기법이다. 연속적인거나 이산적인 값의 집합에서 최적값을 X를 찾고자 할 때 X를 경계로 조건을 만족하는 집합과 답이 될 수 없는 집합을 판정할 수 있을 때 추정 값 A에 대한 판정을 반복해 X를 찾는 방법이다. 이때 판정의 대상이 되는 추정값을 구할 때 이분 탐색을 이용하면 O(logX)의 복잡도의 로직을 짤 수 있다. 보통 ~ 조건을 만족하는 최솟값과 최댓값을 구하라는 문제가 해당된다. 이전에 lowerBound와 upperBound를 찾았던 백준 10816 숫자 카드 2 문제에서 적용했던 것도 이 매개변수 탐색의 일종이라 할 수 있다. - 백준 2417 정수 제곱근 long의 범위에 있는 숫자를 찾으려면..