이분 탐색14 [프로그래머스] 118669번 - 등산코스 정하기 [Java] https://school.programmers.co.kr/learn/courses/30/lessons/118669 문제 설명 XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다. 등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다.예를 들어 1-2-3-2-1 으로 표현하는 등산코스는 1번지점에서 출발하여 2번, 3번, 2번, 1번 지점을 순서대로 방문한다는 뜻입니다.등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수.. 2025. 3. 6. [이분 탐색] 이분 탐색, Lower Bound 이분 탐색, Upper Bound 이분 탐색 구현 및 성능 테스트 주어진 데이터들에서 특정 데이터를 찾으려면 어떻게 해야할까? 주어진 데이터가 N개라면 최대 N개의 데이터가 특정 데이터인지 비교하며 찾아야 할 것이다. 이 방법이 그렇게 나쁘게 보이진 않지만 주어진 데이터가 정렬이 되어있다면 더욱 빠르게 특정 데이터를 찾는 방법이 있다.1부터 100까지의 숫자 중 상대방이 하나의 숫자를 고르고 내가 그 숫자를 맞춰야하는 상황에서 상대방이 내가 숫자를 말하면 자기가 생각한 숫자가 그 수보다 큰지 작은지 알려준다고 할 때 1부터 100까지 순서대로 말하는 사람은 없을 것이다. 50을 말해보고 50보다 작다면 25를 50보다 크다면 75를 말하며 빠르게 숫자를 찾아나갈 것이다. 오늘 주제인 이분 탐색도 이와 같은 원리이다. 1. 이분 탐색 (Binary Search) 이분 탐.. 2025. 2. 15. [백준] 2417번 - 정수 제곱근 [Java] https://www.acmicpc.net/problem/2417 1. 아이디어 제곱값이 N보다 크거나 같은 가장 작은 정수를 찾는 문제로 Lower Bound 이분 탐색으로 해결했다.2. 문제풀이 가능한 q의 범위를 0부터 Math.sqrt(N) + 1로 설정해서 제곱이 N 이상인 수를 찾는 이분 탐색을 적용했다. 부동 소수점 이슈로 바로 적용하는 방식은 동작이 안되는 테스트 케이스가 많아서 q의 상한을 미리 정하고 돌렸다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new .. 2025. 2. 13. [소프티어] 6247번 - 자동차 테스트 [Java] https://softeer.ai/practice/6247 1. 아이디어 정렬과 이분탐색을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 주어진 연비 중 3개를 뽑았을 때 중앙값이 M이 나오는 서로 다른 경우의 수를 구하는 문제로 주어진 연비를 정렬했을 때, 주어진 M이 연비들에 존재하면 (M보다 작은 연비의 개수) * (M보다 큰 연비의 개수)가 서로 다른 경우의 수가 된다. 주어진 M이 연비들에 존재하지 않으면 0을 출력해야한다. 이를 위해 주어진 연비를 배열에 담아 정렬한 후 이분 탐색을 진행했고 이분 탐색의 결과가 -1로 존재하지 않는다는 값을 받으면 0을 출력하고 아니면 해당 곱을 출력하도록 구현했다.3. 코드 import java.io.*;import java.util.*;public cl.. 2025. 2. 6. [벌집] 27436번 - 벌집 2 [Java] https://www.acmicpc.net/problem/27436 1. 아이디어 이전 벌집 문제에서 N의 크기가 매우 커진 문제로 이전처럼 O(N) 시간복잡도의 풀이로는 해결할 수 없다. 이를 단축하기 위해 O(log N)으로 풀 수 있는 이분 탐색으로 방의 개수를 찾는 방식을 적용했다.([코딩테스트 준비/백준] - [백준] 2292번 - 벌집 [Java])2. 문제풀이 이분 탐색은 N 이상인 최솟값을 찾아야하므로 Lower Bound 이분 탐색을 적용했다. 이전 문제와 동일한 점화식 Sn = 3 * n * (n-1) + 1을 가져와서 n을 찾는 이분 탐색으로 적용했다. 대략 2 * 10^9 이면 주어진 N까지 커버할 수 있는 범위라서 아래 코드처럼 적용했는데 실제 풀이에서는 적당한 high 값을 찾.. 2025. 1. 21. [백준] 13711번 - LCS 4 [Java] https://www.acmicpc.net/problem/13711 1. 아이디어 이분 탐색을 활용한 LIS 알고리즘으로 해결할 수 있다.2. 문제풀이 문제 제목이나 설명과 달리 다이나믹 프로그래밍을 활용하는 일반적인 LCS 알고리즘으로 해결하기에는 수열의 크기가 너무 크다.문제 조건이 특이하게 1부터 N까지의 중복되지 않은 수로 이루어진 두 수열의 LCS를 구하라고 나왔는데 이를 LIS 알고리즘으로 치환해서 생각할 수 있다. 두 수열을 한 줄씩 나열한 후 같은 숫자끼리 선을 이으면 마치 전깃줄처럼 연결되어있는데 이때 이 선들이 교차하지 않게 몇 개를 지웠을 때 만들 수 있는 선의 최대 개수와 동일함을 알 수 있다. 선들은 두 수열의 같은 숫자로 이루어져 있으므로 한 수열을 기준으로 숫자를 앞에서부터 .. 2025. 1. 13. [백준] 2568번 - 전깃줄 - 2 [Java] https://www.acmicpc.net/problem/2568 1. 아이디어 이전 전깃줄 문제에서 전깃줄의 개수와 위치 번호가 늘어난 문제로 O(N^2) 시간복잡도의 다이나믹 프로그래밍으로는 해결할 수 없다. 이를 위해 이분 탐색을 활용한 LIS로 구현했고 해당 전깃줄을 포함하는 LIS의 길이를 저장하는 before 배열을 활용했다.([코딩테스트 준비/백준] - [백준] 2565번 - 전깃줄 [Java])2. 문제풀이 이전 전깃줄 문제에서 LIS 로직만 이분 탐색을 활용하도록 바꿨다. dp 배열에는 Lower Bound 이분 탐색으로 수열의 해당 수가 들어갈 수 있는 위치를 반환하게 해서 dp 배열을 해당 수로 갱신시켰다. dp 배열은 인덱스 숫자와 같은 길이의 LIS의 마지막 원소가 저장된다. 추.. 2025. 1. 13. [백준] 14003번 - 가장 긴 증가하는 부분 수열 5 [Java] https://www.acmicpc.net/problem/14003 1. 아이디어 이전 가장 긴 증가하는 부분 수열 3 문제에서 수열 출력이 추가된 문제로 수열의 해당 수가 dp 배열의 어떤 위치에 저장됐는지 before 배열을 통해 저장 후 이를 역순으로 탐색하는 방식으로 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 12738번 - 가장 긴 증가하는 부분 수열 3 [Java])2. 문제풀이 Lower Bound 이분 탐색으로 LIS 구하는 과정에서 before 배열만 추가가 됐는데 수열의 수가 dp 배열에 저장된 인덱스를 저장했다. 그러면 before 배열에는 수열에서 해당 수를 포함하는 LIS의 길이가 저장되게 되고 이 before 배열을 역순으로 돌며 len과 일치하는 위치를 찾으면 해.. 2025. 1. 13. [백준] 12738번 - 가장 긴 증가하는 부분 수열 3 [Java] https://www.acmicpc.net/problem/12738 1. 아이디어 수열의 길이가 최대 100만 문제로 O(N^2)의 시간복잡도가 소요되는 기존의 다이나믹 프로그래밍 방식으로는 해결할 수 없는데 이분 탐색을 활용하면 O(N log N)으로 해결할 수 있다.2. 문제풀이 이전 가장 긴 증가하는 부분 수열 2 문제에서 수열에 음수도 올 수 있는 조건이 추가된 문제로 수열을 저장하는 dp 배열이 양수만 있는 수열은 0으로 초기화하면 이분 탐색에서 1번 인덱스부터 활용할 수 있었지만 이번 문제는 음수도 존재하므로 dp 배열의 1번 인덱스를 문제 조건의 최소 음수보다 작게 초기화하는 방식으로 구현했다.([코딩테스트 준비/백준] - [백준] 12015번 - 가장 긴 증가하는 부분 수열 2 [Java.. 2025. 1. 13. [백준] 12015번 - 가장 긴 증가하는 부분 수열 2 [Java] https://www.acmicpc.net/problem/12015 1. 아이디어 수열의 길이가 최대 100만 문제로 O(N^2)의 시간복잡도가 소요되는 기존의 다이나믹 프로그래밍 방식으로는 해결할 수 없는데 이분 탐색을 활용하면 O(N log N)으로 해결할 수 있다.2. 문제풀이 Lower Bound 이분 탐색으로 수열을 돌며 해당 수가 dp 배열에 어디에 들어갈 수 있는지 찾는다. dp 배열은 인덱스가 LIS의 길이고 값에 해당 길이의 LIS의 마지막 원소가 들어간다. len은 현재까지 구한 LIS의 길이이다. 이분 탐색으로 얻은 인덱스로 dp 배열을 갱신해주고 만약 인덱스가 len 보다 크면 LIS의 길이가 1 늘어난 것이므로 len을 갱신해준다. 이분 탐색 과정에서 dp 배열의 패딩으로 lef.. 2025. 1. 13. [백준] 16401번 - 과자 나눠주기 [Java] https://www.acmicpc.net/problem/16401 1. 아이디어 과자 길이에 대한 매개 변수 이분 탐색을 활용하면 해결할 수 있다.2. 문제풀이 이분 탐색은 나눌 길이를 찾고 count 메서드는 찾은 길이로 줄 수 있는 과자 개수를 구하도록 구성했다.같은 개수를 줄 수 있을 때 최대 길이를 구해야하므로 N개보다 적은 개수가 나오는 직전 길이를 구하는 Upper Bound로 계산 후 -1을 해서 N개가 나오는 최대 길이를 구하도록 했다. 이때 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없으면 0을 출력해야 하는데 이분 탐색에서 mid 값이 0이 되는 순간이므로 이때는 1을 반환하도록 조건 처리를 했다.3. 코드 import java.io.*;import java.util.*;pub.. 2025. 1. 13. [백준] 2805번 - 나무 자르기 [Java] https://www.acmicpc.net/problem/2805 1. 아이디어 나무 높이에 대한 매개 변수 이분 탐색을 활용하면 해결할 수 있다.2. 문제풀이 이분 탐색은 자를 높이를 찾고 cut 메서드는 찾은 선택한 높이로 잘랐을 때 얻을 수 있는 나무를 구하도록 구성했다.얻을 수 있는 나무가 M 이상일 때 높이의 최댓값을 구해야 하는 것은 얻을 수 있는 나무가 M미만인 순간 높이의 최댓값에서 1을 빼서 M 이상을 얻을 수 있는 높이의 최댓값을 구하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2025. 1. 13. 이전 1 2 다음
