PS 일지

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

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$과 정수..

https://www.acmicpc.net/problem/22940 22940번: 선형 연립 방정식 하나 이상의 미지수에 대해 최고차항의 차수가 1을 넘지 않는 방정식을 선형 방정식이라 한다. 족, 다음과 같은 식을 의미한다. A1x1 + A2x2 + ... + Anxn = B 선형 연립 방정식이란 유한개의 선형 방 www.acmicpc.net 문제 요약 주어지는 연립 방정식의 해를 구하는 문제이다. 접근 행렬 크기의 제한이 6 X 6으로 매우 넉넉하다. 가우스 소거법을 직접 구현하면 된다. 가우스 소거법을 모르더라도, 연립 방정식을 푸는 과정을 직접 코드로 구현하자. 어느 쪽이던 다소 번거로운 것 같다. #include using namespace std; int main() { int N; doubl..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 요약 정점에 가중치가 있는 방향 그래프가 주어졌을 때, 최초 진입 차수가 0인 정점에서부터 지정된 정점까지 가는 경로의 가중치 합의 최솟값을 구하는 문제이다. 접근 기본적인 위상 정렬 문제이다. 배열 deg를 선언하여 i번 정점을 자손으로 두는 정점의 개수를 저장한다. 다시 말해, 진입 차수를 나타내는 배열이다. deg배열과 큐 자료 구조를 이용하여 위상 정렬을 수행한다. 사전에 배열 ..