본문 바로가기

binary search25

[Problem Solving] 2019 카카오 개발자 겨울 인턴십: 징검다리 건너기 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/64062?language=python3 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr디딤돌의 숫자는 디딤돌을 밟으면 1 줄여진다.디딤돌의 숫자가 0인 칸은 건너뛰어야 하고, 건너뛸 수 있는 최대 거리가 k라고 할 때,징검다리를 최대 몇 명 건널 수 있는지 구하는 문제이다. 이 문제는 징검다리를 최대 몇 명 건널 수 있는지의 수를 매개변수로 취급하여 최적의 매개변수를 탐색하는 문제이다.low는 0, high는 200000001로 설정한다. (디딤돌의 수의 최댓값은 200000000이기 때문이다.).. 2025. 9. 7.
[Problem Solving] BOJ 16566: 카드 게임 문제 출처: https://www.acmicpc.net/problem/16566 철수가 내려는 카드를 아는 민수는 그것보다 큰 카드 들 중에서 가장 작은거를 내면 된다. 철수가 내려는 카드보다 큰 것이 처음 나타나는 지점의 인덱스를 알면 된다. 고른 카드를 정렬하고, 철수가 내려는 카드의 upper_bound를 찾으면 된다. 이제 그 카드를 버려야하는데, 여기서 erase를 해버리면 O(KM)이 되기 때문에, 시간 초과가 난다. M을 log M 연산으로 변환하기 위해 Union Find를 도입할 수 있다. 우선 모든 카드의 parent를 자기 자신의 index로 설정한다. 철수가 내려는 카드보다 큰 것을 찾으려고 할 때, 찾은것의 parent index를 찾고, 그 index가 위치한 곳에 있는 카드 번.. 2025. 8. 23.
[Problem Solving] BOJ 2866: 문자열 잘라내기 문제 출처: https://www.acmicpc.net/problem/2866 R개 행과 C개 열로 이루어진 테이블에 C 길이인 문자열 R개를 넣는다.각 테이블의 열을 위에서 아래로 읽어서 문자열을 만드는데, 중복이 존재하지 않으면 맨 위에 행을 없앤다. 이때 cnt를 올린다.이 과정을 반복하는데, 중복이 존재하는 순간 반복을 멈추고 cnt를 출력한다. 여기서 최대 cnt를 찾아야하는데 이는 반복적으로 찾으면 비용이 너무 높아서 1초 안에 문제를 풀 수 없다. O(R*R*C)는 10억이기 때문이다. 이를 완화하기 위해cnt를 매개변수로 취급하여 매개변수 탐색으로 찾으면 된다. -> O(logR * R * C) low를 0으로high를 R - 1로 설정한다.mid는 low와 high의 중간 값이다.mid행.. 2025. 7. 10.
[Problem Solving] BOJ 2515: 전시장 문제 출처: https://www.acmicpc.net/problem/2515 그림을 1열로 세워놓았을 때 세로 S만큼 보이는 그림을 판매 가능 그림이라고 한다. 판매 가능 그림의 합이 최대가 될때 그 최댓값을 구하는 문제이다. 이 문제는 DP와 이분탐색으로 풀 수 있다. 판매 가능 그림 세트를 만들어서 맨 앞에다가 둔다고 생각하면 된다.DP테이블을 정의하자면, 그림의 높이를 기준으로 오름차순으로 정렬했다고 했을 때,DP[i]는 i번째 그림까지 취급할 때, 판매 가능 그림의 합의 최댓값이다. H 기준 오름차순으로 정렬된H = {8, 10, 15, 17, 20, 26}C = {230, 100, 80, 200, 75, 80}의 예시가 있다고 하자. 1)일단 DP[0] = 230이다. 2)H[0:1]에서 H[.. 2025. 6. 30.
[Problem Solving] BOJ 16564: 히오스 프로게이머 문제 출처: https://www.acmicpc.net/problem/16564 매개변수 탐색 문제이다. 캐릭터의 레벨이 배열 X에 주어지고, 총량 K 만큼 임의로 레벨 업 할 수 있을 때, 최대 K번 레벨 업 하였을 때 팀 레벨의 최솟값의 최댓값을 구하는 문제이다. test함수는 매개변수 t를 받고, 레벨이 t 이하인 캐릭터들을 모두 t로 레벨업 할 경우 필요한 총량을 return하는 함수이다. low = 1로 설정하고high = 1000000001로 설정한 다음, 매개변수 T의 최댓값을 매개변수 탐색 방식으로 찾는다. test(mid)값이 K이하 라면, 팀원 전체의 레벨을 mid 이상으로 맞출 수 있고 mid보다 더 큰 값으로 맞출 가능성도 있다는 뜻이다.따라서 T = mid로 설정하고, low = .. 2025. 6. 2.
[Problem Solving] BOJ 3896: 소수 사이 수열 문제 출처: https://www.acmicpc.net/problem/3896 에라토스테네스의 체를 사용해서 소수리스트를 만들고, K를 입력받아서 그 K보다 큰 소수와 작은 소수의 차이를 구하는 문제이다.소수를 찾을 때는 이진탐색을 사용해서 찾으면 빠르게 찾을 수 있다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { public static int T; public static int K; public static ArrayList prime_numbers; public static int res.. 2025. 5. 15.
[Problem Solving] BOJ 2613: 숫자구슬 문제 링크: https://www.acmicpc.net/problem/2613 인접한 구슬끼리 묶어서 그룹을 만든다. 각 그룹에는 한 개 이상의 구슬이 있다. low: 구슬의 적힌 숫자 중 최댓값high: 구슬의 적힌 숫자들의 합으로 설정하고low mid는 (low + high) / 2이다.1. 각 그룹의 구슬에 적힌 숫자의 합이 mid가 넘지 않도록 그룹을 만들었을 때, 발생하는 그룹의 수가 M보다 작거나 같다. -> 최소의 mid를 구하기 위해 범위를 더 낮춰본다. -> opt = min(opt, min), high = mid - 12. 각 그룹의 구슬의 적힌 숫자의 합이 mid가 넘지 않도록 그룹을 만들었을 때, 발생하는 그룹의 수가 M보다 많다. -> mid가 너무 작아서 너무 많은 그룹이 생겼으.. 2025. 4. 12.
[Problem Solving] BOJ 14426: 접두사 찾기 문제 링크: https://www.acmicpc.net/problem/14426 S를 정렬한다.S에서 각 T[i]에 대해 이진탐색 한다.java에서 이진탐색의 결과는 정확히 일치하는 값이 있으면 그 값이 존재하는 S에서의 index를 반환하고, 일치하지 값이 없으면 T[i]가 삽입될 자리를 -index-1로 반환한다. 이 때 index = -index-1로 바꿔주면 S[index]는 T[i]를 접두사로 갖는 문자열이다.index가 N보다 작고 S[index]가 T[i]로 시작하는 문자열인지 startsWith함수를 사용해 확인하여 이 결과가 참이라면 result를 1증가시킨다. import java.io.BufferedReader;import java.io.IOException;import java.io.. 2025. 3. 25.
[Problem Solving] BOJ 2632: 피자판매 문제 링크: https://www.acmicpc.net/problem/2632 피자 A와 피자 B가 있다.각 피자는 다양한 크기의 여러 조각으로 나누어져 있는데, k 크기 만큼의 피자를 구매하려고 할 때, 피자 A에서 연속된 조각, 피자 B에서 연속된 조각으로 혼합하여 구매하거나, 피자 A에서만 k 크기 만큼의 연속된 조각을 구매하거나 피자 B에서만 k 크기 만큼의 연속된 조각을 구매할 수 있다. k 크기 만큼의 피자를 구매할 수 있는 모든 경우의 수를 구하는 문제이다. 일단 피자 A와 피자 B 각각에 대해 getPartSums함수를 통해 구간합의 집합을 return 받는다.getPartSums함수는 다음과 같이 동작한다.1. 어떤 조각도 고르지 않는 경우인 0을 추가한다.2. 모든 조각을 고르는 경우를.. 2025. 3. 15.
[Problem Solving] BOJ 13397 : 구간 나누기 2 문제 링크 : https://www.acmicpc.net/problem/13397 배열을 최대 M개로 분할할 수 있을 때, 각각의 분할의 최댓값-최솟값중 가장 큰 값을 구하는데, 그것의 최솟값을 구하는 문제이다. 1.배열 v가 있다.low = 0high = max(v)-min(v)로 설정한다. 2.low  mid = (low + high) / 2로 설정한다. func(x)함수는 각각의 분할의 최댓값-최솟값이 x이하의 값이 되도록 분할하는 함수이다. 이 때 분할의 개수가 M보다 크면 false를 return, 그렇지 않다면 true를 반환한다.x가 작을수록 잘게 분할되어 분할이 많아지고, x가 클수록 크게 분할되어 분할의 수가 작아진다. func(mid)가 true라면분할이 M개 이하로 생긴 것이다.ans.. 2025. 2. 22.
[Problem Solving] BOJ 3745 : 오름세 문제 링크 : https://www.acmicpc.net/problem/3745 각 테스트케이스마다 LIS의 길이를 구하는 문제이다.LIS 알고리즘 : https://junstory314.tistory.com/entry/Computer-Algorithms-LIS-Longest-Increasing-Sequence-%EC%B5%9C%EC%9E%A5-%EC%A6%9D%EA%B0%80-%EC%88%98%EC%97%B4 #include #include #include #include #include #include #include #include #include #include #define endl '\n'using namespace std;int N;vector p;vector lis;void input(){.. 2025. 2. 17.
[Problem Solving] BOJ 16434 : 드래곤 앤 던전 문제 링크 : https://www.acmicpc.net/problem/16434 전형적인 구현 + 매개변수 탐색 문제이다. 문제에 나와있는대로 simulate함수를 구현한다. 그런데 영웅과 몬스터가 한 대 씩 딜을 주고 받는 것으로 구현한다면 시간이 초과된다. 그러므로 다음과 같이 계산해서 구한다. 영웅이 몬스터를 처치하기까지, 혹은 처치하기 전까지 필요한 타격의 수 = 몬스터의 현재 HP / 영웅의 공격력몬스터가 영웅을 처치하기까지, 혹은 처치하기 전까지 필요한 타격의 수 = 영웅의 현재 HP / 몬스터의 공격력 이 중 더 작은 값을 구해서 cnt에 저장한다. 그리고 다음을 계산한다.몬스터의 현재 HP -= 영웅의 공격력 * (cnt - 1)영웅의 현재 HP -= 몬스터의 공격력 * (cnt - 1).. 2025. 2. 1.
[Problem Solving] BOJ 3649 : 로봇 프로젝트 문제 링크 : https://www.acmicpc.net/problem/3649 x * 10000000 == l1 + l2를 만족하는, l1  1. x, n, l을 입력받는다.2. l을 오름차순 정렬한다.3. n이 2 미만이면 l1와 l2 두개를 고를 수 없으므로 danger 출력.4. low와 high를 각각 양쪽 맨 끝에 설정하고, l[low] + l[high]가 x보다 크다면 high를 내리고, x보다 작으면 low를 올린다. x와 같다면 findFlag를 True로 설정하고 그 때의 l[low]를 l1에, l[high]를 l2에 저장한다.5. findFlag가 False면 danger 출력, Flag가 모두 True라면 yes l1 l2 출력  import sysread = sys.stdin.re.. 2025. 1. 26.
[Problem Solving] BOJ 1561 : 놀이 공원 문제 링크 : https://www.acmicpc.net/problem/1561 놀이 기구에 승객을 탑승 시키는 데, 동시에 탑승 가능 한 놀이기구가 여러 개 있을 때에는 놀이기구 순서대로 탑승시킨다. 이럴 때, 마지막 승객이 탑승하는 놀이기구가 무엇인지 구하는 문제이다. 승객의 수(N)가 기구의 수(M) 보다 작거나 같을 때에는 N을 출력하면 된다. N이 M보다 클 때는 다음과 같은 방식으로 해결할 수 있다. func(x)는 주어진 시간 x 동안, 탑승 시킬 수 있는 승객의 수를 return 하는 함수이다.우선 0초에 아무도 탑승하지 않았을 때에는 기구에 모든 승객으로 채울 수 있으므로 ret의 초깃값을 M으로 설정한다.x를 각 기구의 운영 시간 time으로 나누면 각 기구가 x동안 탑승 시킬 수 있는.. 2025. 1. 7.
[Problem Solving] BOJ 2295 : 세 수의 합 문제 링크 : https://www.acmicpc.net/problem/2295   x + y + z = k를 만족하는 x, y, z, k번째 수가 있을 때, k의 최댓값을 찾는 문제이다. O(n^3) 반복문을 쓰면 O(n^3 * log n)만큼 걸리기 때문에 시간초과가 난다.  때문에 이 문제는 x + y = k - z 을 만족할 때, k의 최댓값을 찾는다고 생각하면 O(n^2)에 해결할 수 있다.  우선 모든 x + y를 added 배열에 추가한다. 다음으로 모든 k - z를 subed배열에 추가하고, k - z 결과에 대한 k의 최댓값을 map 자료구조에 저장한다.  x + y = k - z인 경우를 이진탐색으로 찾고 그 때의 k값을 answer에 저장한다. #include #include #inc.. 2024. 8. 23.

티스토리툴바