PS 일지

10/11 ~ 10/20에 푼 문제들입니다. 문제의 풀이에 대한 스포일러가 포함되어 있습니다. 잘못된 풀이가 있다면 지적해주세요. 10/11 BOJ 10436 - 무한 유리수 트리 Gold 4 더보기 #math #tree $pq$인 경우는 $p 1$인 $j$는 최적해를 만들어줄 수 없다는 관찰이 필요하다. 즉, 앞뒤로 한 칸만 검사해주면 된다. $dp[i]$를 $i$번째 트럭까지 처리했을 때의 가능한 최솟값이라 하고 $addv[i][j]$를 구간 $[i-j+1, i]$에서 모든 가능한 배치 중 최솟값이라 할 때 , $dp[i] = min(dp[i-1] + addv[i][1], dp[i-2] + addv[i][2], dp[i-3] + addv[i][3])$이다. BOJ 5615 - 아파트 임대 Platin..

10/1 ~ 10/10에 푼 문제들입니다. 문제의 풀이에 대한 스포일러가 포함되어 있습니다. 잘못된 풀이가 있다면 지적해주세요. 10/2 BOJ 30284 - Karjeras Gold 5 더보기 #prefix_sum imos법으로 알려져있는 걸로 알고 있다. 구간의 변화를 시작점과 끝점에 각각 +1, -1을 취하는 방법인데, 이 문제에선 반대로 -1, +1을 해주면 된다. BOJ 30276 - Traukinys Gold 4 더보기 #greedy 만약 $a_{i}$가 $K$보다 작다면, 무조건 가까운 곳에서 끌어오는 것이 이득이다. 끌어오는 쪽의 $a_{i}$가 $K$보다 작아도 무조건 끌고 오는 것이 포인트이다. 아이디어는 금방 떠올랐지만 개인적으로 구현이 힘들었다. 10/3 BOJ 6611 - Simo..

9/21 ~ 9/30에 푼 문제들입니다. 문제의 풀이에 대한 스포일러가 포함되어 있습니다. 잘못된 풀이가 있다면 지적해주세요. 9/21 BOJ 30092 - 슥삭슥삭 나무자르기 Platinum 1 더보기 #tree #lca 경로 $a$-$b$와 $c$-$d$가 두 점 이상을 공유하는 지 판별하자. 여러 lca를 구해서 경우를 따져보면 된다. BOJ 30155 - Crazy Malvika discovers Crazy Fibonacci function Silver 3 더보기 #math 주어진 수열은 첫 6개의 항이 계속 반복되는 형태이다. 9/23 백준에 올라온 ZOAC 대회 문제들을 풀었다. 처음으로 대회 문제 출제진으로 참여했다. 문제 만들기도 어려웠지만, 다른 사람들이 만든 문제를 풀고 검수하는 게 훨..

9/11 ~ 9/20에 푼 문제들입니다. 문제의 풀이에 대한 스포일러가 포함되어있습니다. 9/11 BOJ 2263 - 트리의 순회 Gold 1 더보기 #divide_and_conquer postorder로 방문한 마지막 정점이 트리의 루트임을 이용해서 루트 기준으로 왼쪽 서브트리, 오른쪽 서브트리에 대해 각각 루트를 구해주는 방식으로 해결할 수 있다. BOJ 1774 - 우주신과의 교감 Gold 3 더보기 #mst mst에서 이미 연결된 간선들이 주어지는 것 이외에는 기본 mst 문제와 같다. BOJ 6497 - 전력난 Gold 4 더보기 #mst mst의 가장 기본적인 문제이다. BOJ 17299 - 오등큰수 Gold 3 더보기 #stack {각 수가 등장한 횟수, 인덱스} 쌍으로 stack에 차례대로..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 요약 주어진 행렬 $A$와 자연수 $B$에 대하여, $A^B$의 각 원소를 1000으로 나눈 나머지를 출력하는 문제이다. 해결 전략 어떠한 정수 $A$를 B제곱하는 것은 분할 정복을 이용하여 계산하는 것이 잘 알려져있다. $A^B = A^{B/2} * A^{B/2}$이고, $A^{B/2} = A^{B/4} * A^{B/4}$이고, ... 이렇게 계속해서 B를 절반으로 쪼개어 생각하면 $O(log{B})$에..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 요약 높이가 $N$인 하노이 탑을 푸는 데 걸리는 최소 이동 횟수와 이동 경로를 출력하는 문제이다. 해결 전략 높이가 $N$인 하노이 탑을 1번에서 3번으로 이동하는 것이 문제의 목표이다. 단순하게 생각해보자. $N = 3$인 하노이 탑이 있고, 이를 3번 판 위로 모두 옮겨야 한다. 가장 밑 발판을 제외한 $N = 2$의 하노이 탑을 2번 판으로 옮긴다. (이것은 한 번의 이동..

https://www.acmicpc.net/problem/1485 1485번: 정사각형 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 네 줄로 이루어져 있으며, 점의 좌표가 한 줄에 하나씩 주어진다. 점의 좌표는 -100,000보다 크거나 같고, 100,000보다 작거나 같 www.acmicpc.net 문제 요약 네 개의 점이 주어지면 이것들이 정사각형을 이룰 수 있는지 판단하는 문제이다. 해결 전략 우선, 네 개의 점을 입력받아 오름차순 정렬 후 두 가지 case로 나누었다. 1. x좌표를 기준으로 첫 번째, 두 번째 점을 이었을 때 y축에 평행한 경우 2. 1번이 아닌 경우 1번의 경우에는 나머지 변들이 각각 축에 평행하고 길이가 모두 같다면 정사각형이다. 2번의 경우에는 네 변..

https://www.acmicpc.net/problem/13116 13116번: 30번 첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1 www.acmicpc.net 문제 요약 2007년 수능 수리 가형 30번 문제를 푸는 문제이다. 고등학교 시절 3년을 수학에만 쏟아부었던 사람으로서, 이 문제를 보고 도저히 그냥 지나칠 수가 없었다. 문제에 써있는 것처럼, 나도 저작권 위반으로 판사님을 뵙고 싶지 않기에 궁금하다면 직접 링크를 타고 들어가보자. http://wdown.ebsi.co.kr/W61001/01exam/20061116/..

https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 문제 요약 문자열 $S$가 주어지면, $S$가 PPAP 문자열인지 확인하는 문제이다. PPAP 문자열은 다음 두 가지 방법으로 정의된다. - $P$는 PPAP 문자열이다. - PPAP 문자열에서 $P$ 하나를 $PPAP$로 바꾼 문자열은 PPAP 문자열이다. 접근 문자열 $S$에서 차례대로 문자를 하나씩 꺼내서 $PPAP$가 만들어지면 그 부분을 $P$로 바꿔주는 방식으로 구현했다. 변수 $a$와 $p$를 선언하여 각각 현재까지 나온 $A$, $P..

https://www.acmicpc.net/problem/25639 25639번: 수열과 최대 상승 쿼리 길이가 $N$인 수열 $a_1, a_2, ..., a_N$이 주어졌을 때, 다음과 같은 쿼리를 수행하는 프로그램을 작성해보자. 1 k x: $a_k$를 $x$로 바꾼다. 2 l r: 구간 $[l, r]$의 최대 상승 값을 출력한다. 구간 $[l, r]$의 최 www.acmicpc.net 문제 요약 길이가 N인 수열 $a_1, a_2, \cdots, a_N$에 두 가지의 쿼리를 수행하는 문제이다. 주어지는 쿼리는 다음과 같다. $1 k x : a_k$를 $x$로 바꾼다. $2 l r :$ 구간 $[l,r]$의 최대 상승값을 출력한다. 구간 $[l,r]$의 최대 상승값 : $max(a_j-a_i)\qua..