PS 일지

9/11 ~ 9/20에 푼 문제들입니다.문제의 풀이에 대한 스포일러가 포함되어있습니다.9/11BOJ 2263 - 트리의 순회Gold 1더보기 #divide_and_conquerpostorder로 방문한 마지막 정점이 트리의 루트임을 이용해서 루트 기준으로 왼쪽 서브트리, 오른쪽 서브트리에 대해 각각 루트를 구해주는 방식으로 해결할 수 있다. BOJ 1774 - 우주신과의 교감Gold 3더보기 #mstmst에서 이미 연결된 간선들이 주어지는 것 이외에는 기본 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})$에 $A^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 ≤ 1www.acmicpc.net 문제 요약2007년 수능 수리 가형 30번 문제를 푸는 문제이다.고등학교 시절 3년을 수학에만 쏟아부었던 사람으로서, 이 문제를 보고 도저히 그냥 지나칠 수가 없었다. 문제에 써있는 것처럼, 나도 저작권 위반으로 판사님을 뵙고 싶지 않기에궁금하다면 직접 링크를 타고 들어가보자.http://wdown.ebsi.co.kr/W61001/01exam/20061116/mathga..

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..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스www.acmicpc.net 문제 요약가중치 있는 유향 그래프가 주어지고 시작 정점과 도착 정점이 주어졌을 때, 시작 정점에서 도착 정점까지의 경로의 가중치 합의 최솟값을 구하고, 경로에 속한 정점들을 방문 순서대로 출력하는 문제이다. 접근기본 다익스트라 알고리즘에서 경로 추적을 해야 한다.다익스트라를 수행하면서 정점들이 지나온 경로들을 새로운 2차원 벡터 R에 저장하였다.벡터 R[i]에 저장된 ..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에www.acmicpc.net 문제 요약주어진 그래프가 이분 그래프인지 판별하는 문제이다. 더보기이분 그래프(Bipartite Graph)?그래프의 정점의 집합을 둘로 분할했을 때, 각 집합에 속한 정점끼리 서로 인접하지 않게 할 수 있는 그래프이다. 접근이분 그래프를 모르는 상태에서 문제를 접하다보니 구현에 실수가 조금 있었다. 양방향 그래프를 입력 받고, visit배열을 통해 방문 여부를 확인하며 평범한 DFS를 구현했다. 이..

https://www.acmicpc.net/problem/3769 3769번: 최댓값첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 한 줄이고, $m, p, a, b$로 이루어져 있다. ($m \le 2000, p \le 12, p$는 짝수) 항상 주어진 조건을 만족하는 \(x_1, x_2, \dots, x_m\)이 존www.acmicpc.net 문제 요약$m$개의 수 $x_1, x_2, \cdots, x_m$을 정수 $a$, $b$에 대하여 다음과 같이 정의한다. $(a > 0)$1. $\quad -\frac{1}{\sqrt{a}} \le x_i \le \sqrt{a}$2. $\quad x_1+x_2+\dotsb+x_m=b\times\sqrt{a}$자연수 $m$과 정수 $a$, ..