이분 탐색 (20) 썸네일형 리스트형 [Python] 11834번 홀짝 https://www.acmicpc.net/problem/11834 25/06/15 이전에 북마크 해두었던 문제로, 몇 개를 좀 나열해보다가 쉽게 해결할 수 있었다. 문제 접근 방식: 어떤 수열이 다음과 같은 규칙으로 주어진다. 홀수 $1$개, 짝수 $2$개, 홀수 $3$개, ... 이런 식으로 연속된 홀수와 짝수가 개수를 점점 늘려가며 늘어난다. 즉, $1 \ \ 2 \ 4 \ \ 5 \ 7 \ 9 \ \ 10 \ 12 \ 14 \ 16 \ \ \cdots$으로 이루어져있다. 이때 우리가 구하고자 하는 것은 이 수열의 $N$번째 항을 구하고 싶다. $N$의 제한이 $10^{100}$이므로, 당연히 시뮬레이션으로 구하면 터진다는 것을 확인할 수 있다. 따라서 우리는 $N$번째 항을 "이분 탐색"으로 .. [C++] 2370번 시장 선거 포스터 https://www.acmicpc.net/problem/2370 25/03/18 이전에 해결했던 좋은 문제인데, 복습할 겸 다시 적어본다. 문제 접근 방식: 일단 이 문제에는 아주 간단하고 나이브한 솔루션이 존재한다. 그 전에 내가 먼저 해결했던 방법을 소개하고자 한다. 문제를 요약하자면 다음과 같다. 1. 포스터를 순서대로 붙임.2. 즉, 포스터가 시작하는 지점 $l$과 끝나는 지점 $r$이 쿼리로 주어짐.3. 쿼리가 다 끝난 뒤에 보이는 서로 다른 포스터의 개수를 구하는 것이 우리의 목적. 포스터가 위치할 수 있는 범위는 $1$부터 $100 \ 000 \ 000$ ($1$억)까지이다. 또한 쿼리의 개수는 최대 $10 \ 000$($1$만)까지이다. 가장 단순한 방법은, $1$억짜리 배열을 하나 .. [C++] 17597번 Zipline https://www.acmicpc.net/problem/17597 25/01/12 간단한 기하학 문제다. 케이스를 나눠서 접근하면 쉽게 해결할 수 있다. 문제 접근 방식: 먼저 두 기둥을 잇는 케이블의 가장 짧은 길이는 두 기둥의 끝을 서로 이은 선분의 길이라는 사실은 쉽게 확인할 수 있다. 이제 케이블의 길이를 점점 늘린다고 해보자.문제에서 주어지는 그림이 케이블을 점점 늘린 상황이라고 가정해보자. 우리는 이 때의 경우에도 케이블 카가 지면으로부터 $r$만큼 위에 있어야 한다는 사실을 알고 있다. 근데 문제는 최저점을 찍었을 때의 상황이 언제인지를 모른다. 케이블 카가 $x$만큼 오른쪽으로 간 상황이라고 해보자. 그러면 케이블의 길이가 다음과 같다. $$l = \sqrt{(g-r)^2 + x^2}.. [C++] 2143번 두 배열의 합 https://www.acmicpc.net/problem/2143 25/01/11 이전에 북마크에 넣어두었다가 해결했던 문제다. 두 가지 해결 방법으로 해결할 수 있는데, 일단 나는 첫번째 해결 방법으로만 해결했고, 나머지 하나는 아이디어만 생각해두어서 적어보려고 한다. 문제 접근 방식: 부 배열의 합은 그냥 연속된 구간 합이다. 당연히 나이브하게 하면 시간초과가 날게 뻔하므로, 각각의 누적 합 배열을 $AA, BB$라고 하자. 이제 문제는 $T$가 주어질 때 $AA[i] - AA[j] + BB[p] - BB[q] = T$를 만족시키는 $i, j, p, q$를 구하는 경우의 수 문제로 바뀌게 되었다. 인덱스를 총 $4$개 뽑아야 되는데, 당연히 나이브하게 이걸 $4$개 뽑아서 조건을 만족시키는 것을 .. [Python] 31531번 공들의 리듬게임 https://www.acmicpc.net/problem/31531 24/03/10 풀이 아이디어가 제법 알려져 있는 문제로, 이전에 비슷한 문제를 해결했다면 쉽게 해결 할 수 있는 애드혹 문제다. 문제 접근 방식: 이 문제의 아이디어는 아래 문제에서 얻을 수 있다.https://www.acmicpc.net/problem/4307또는 아래 문제에서도 얻을 수 있다.2023.09.02 - [알고리즘/백준 문제 풀이] - [Python] 13249번 공의 충돌 [Python] 13249번 공의 충돌https://www.acmicpc.net/problem/13249 13249번: 공의 충돌 무게가 모두 같고, 크기가 0인 공 N개가 일직선 위에 놓여져 있다. 오른쪽으로 굴러가는 공과 왼쪽으로 굴러가는 공.. [Python] 31532번 선형 회귀는 너무 쉬워 3 https://www.acmicpc.net/problem/31532 31532번: 선형 회귀는 너무 쉬워 3 첫 번째 줄에 $f_3(a)$의 값이 $0$에 가장 가깝게 하는 $a$, 즉, $a_3$을 출력한다. 답이 여러 가지라면 그중 아무거나 하나 출력한다. 가능한 정답 중 최소 하나 이상과의 절대오차 또는 상대오차가 $10 www.acmicpc.net 24/03/12 지난 겨울 MatKor Cup에 나왔던 문제로, 단순한 수치해석 문제입니다. 선형 회귀는 너무 쉬워 시리즈의 3번째 문제에 해당됩니다. 서브태스크 별로 문제 해설을 해보겠습니다. 문제 접근 방식: 서브태스크 1 ($b = 0;y_i = 0$) 모든 데이터(점)들의 $y$값 들이 $0$이고, 직선의 $y$절편이 $0$으로 주어져 있습니다... [Python] 31235번 올라올라 https://www.acmicpc.net/problem/31235 31235번: 올라올라 길이가 $N$인 수열 $A$가 주어질 때, $N$ 이하의 양의 정수 $k$에 대하여 길이가 $N-k+1$인 수열 $B$를 다음과 같이 정의하자. $$B_{i}=\max_{i \le j \le i+k-1}A_j$$ 수열 $B$가 감소하지 않도록 하는 $k$의 최솟값 www.acmicpc.net 24/03/19 두 가지 방법으로 풀 수 있는 좋은 문제다. 그리디 + 스택으로도 풀 수 있고, 슬라이딩 윈도우+이분 탐색으로도 풀 수 있다. 개인적으로 전자가 더 쉽게 떠올릴 수 있다고 생각하지만 구현하는 데에 조금 실수가 생길 수 있고, 후자는 조금 더 어렵지만 구현하는 것이 그다지 어렵지 않아서, 어느 쪽으로 푸나 난이도.. [Python] 9024번 두 수의 합 https://www.acmicpc.net/problem/9024 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 24/02/12 이전에 실패 했던 문제를 다시 풀어보았다. 전형적인 투 포인터 문제이지만, 포인터를 움직이는 방향에 유의해서 문제를 해결해야만 했었다. 문제 접근 방식: 특정한 값이 주어져 있고, 그 값에 가장 가까운 두 수의 합을 만들 수 있는 모든 조합을 찾는 것이 문제의 목표이다. 투 포인터 문제임을 보자마자 파악했지만, 포인터를 움직이는 방향에 유의해야만 했다. 나는 두 가지 경우로 분리해서.. 이전 1 2 3 다음
