본문 바로가기

이분탐색8

[백준/C++] 급상승 (No. 23978) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 상승시켜야하는 코인 가격의 최소를 구하는 문제다. 그러므로 코인의 가격을 C라고 하면 가격이 C일 때 현금화 했을 때 가격이 K보다 크거나 같게 할 수 있는지 판단하면 된다. 이때, 적절한 C를 빠르게 찾기 위해 이분탐색을 사용하면 O(N*log K)로 문제를 해결할 수 있다. 그러므로 범위를 최소 범위와 최대 범위인 st=1, ed=2*10^9로 설정하고 이분탐색을 이용해 적절한 C가격을 찾아나가면 된다. 이때, 코인의 상승가격이 C인 경우 현금화 가격 K가 가능한지 계산하기 위해서는 상승 가격의 기간이 중요하다. 코인이 상승하는 기간의 차이를 A일이라고 하면, 상승가격 C와 A를 비교한다.. 2024. 12. 15.

[백준/C++] 줄다리기 (No. 31444) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때 어떻게 풀어야할지 감이 잘 안왔다. 모든 경우를 전부 구하면 2^2000으로 시간이 초과됐고, 우선순위 큐를 이용해 그리디하게 풀어도 동점의 경우 명확하지 않다는 문제가 있었기 때문이다. 고민을 하다 힌트를 보니 이분탐색으로 문제를 풀 수 있겠다는 생각이 들었다. 먼저 두 팀의 팀워크 점수를 A값보다 크거나 같게 만들 수 있는지 검사한다.그러면 같은 팀이 된 사람들의 점수가 A보다 크거나 같아야 하므로, i번째 사람과 j번째 사람의 팀워크 점수가 A보다 작다면 두 사람은 같은 팀이 되면 안된.. 2024. 11. 19.

[프로그래머스/C++] 선입 선출 스케줄링 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 core가 처리해야하는 작업이 있다면, 모든 작업을 처리할 경우 몇 번째 코어가 최종작업을 실행하는지를 찾는 문제다. 특정 시간에 각 core가 처리한 작업의 수를 찾는 방법은 나눗셈을 이용하면 쉽게 계산할 수 있다. 그렇기 때문에 n개의 작업을 처리할 수 있는 특정 시간을 찾으면 몇 번째 코어가 최종 작업을 실행하는지 알 수 있다. 여기서 특정 시간을 찾는 방법은 이분탐색으로 쉽게 찾을 수 있다. 이분탐색을 사용할 경우 log(N)의 시간 복잡도로 탐색을 할 수 있기 때문에 이 문제의 시간 복잡도는 코어의 수*log(N) 이 된다. 여기서 주의할 점은 특정 시간에 수행할 수 있는 작업은 0시간에는 c.. 2024. 3. 21.

[프로그래머스/C++] 징검다리 건너기 (2019 카카오 개발자 겨울 인턴십) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 문제를 푸는 방법이 몇 개 생각났지만, 그 중에서도 이분탐색으로 몇 명이 건널 수 있는지를 먼저 선택하고 실제로 건널 수 있는지를 체크하는 방법이 빠르다고 생각했다. 생각한 방법들 중 하나를 소개하자면, k개 만큼의 돌들을 탐색하고 그중에 max값을 찾으면 max 값을 저장하고 그 이후의 돌 부터 다시 k개 돌을 탐색해 max값이 얼마인지 찾으면서 탐색하는 방법이다. 대신 이 방법을 쓰게 되면 우선순위 queue가 필요하고, 우선순위 queue를 쓰더라도 edge case가 생길 여지가 있어 이분탐색 방법을 선택했다. 이분 탐색으로 n명이 건널 수 있다고 가정할 경우 1. 만약 n보다 같거나 작은돌이 연속으로 n.. 2024. 1. 29.

[프로그래머스/C++] 입국심사 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 문제를 봤을 때, 범위가 말이 안되기 때문에 times의 최소공배수를 구해서 나누어야하나? 생각이 들었다. 그런데 아무리 봐도 times의 범위도 매우 길 뿐더러 나눠도 해결이 안될 것이라고 생각해 다른 방법을 생각해봤다. 그 다음으로는 최소힙을 만들고 거기에 특정 심사가 만료되면 몇분이 되는지를 저장하는 방식을 생각했다. 구현만 하면 가능하겠지만, 1,000,000,000번 힙에 삽입 삭제를 하면 시간초과가 될 게 분명해서 이 방법도 넘겼다. 이렇게 힙을 생각하다보니 특정 사람의 심사가 끝나는 시간을 한명씩 넘겨가면서 구하는 것보다 반대로 특정 시간에 몇명을 심사할 수 있는지를 계산하면 되겠다는 생각이 .. 2024. 1. 26.

[프로그래머스/C++] 쿠키 구입 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 쿠키의 길이가 최대 2000이기 때문에 시작점과 끝 점을 고르면 이분탐색으로 절반으로 나눌 수 있는지 쉽게 구할 수 있다고 생각했다. 그리고 계속 반복해서 시작점과 끝점을 더하는 계산이 나오지 않도록 부분합을 이용해 반복 덧셈을 줄였다. 쿠키의 시작점과 끝점이 주어지면 먼저 쿠키의 개수의 총합이 홀수인지 짝수인지 확인한다. 홀수인 경우는 절반으로 나눌 수 없으므로 패스한다. 짝수일 경우는 이분탐색으로 쿠키를 절반으로 나눌 수 있는지 탐색하면 된다. [아이디어 정리] 쿠키의 부분합을 구한다. (반복 덧셈을 줄이기 위해서) 시작점과 끝점을 기준으로 이분탐색을 해 쿠키를 절반으로 나눌 수 있는지 구한다. 쿠키를 절반으로.. 2024. 1. 12.

[백준/Python] 1920번 - 수 찾기 HTML 삽입 미리보기할 수 없는 소스 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다. HTML 삽입 미리보기할 수 없는 소스 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. HTML 삽입 미리보기할 수 없는 .. 2024. 1. 4.

[백준/Python] 1654번 - 랜선 자르기 HTML 삽입 미리보기할 수 없는 소스 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 .. 2024. 1. 4.

이전 1 다음

티스토리툴바