PS 일지

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

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; double map[6]..

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

https://www.acmicpc.net/problem/2405 2405번: 세 수, 두 Mn개의 정수 A[1], A[2], …, A[n]이 있다. 서로 다른 세 정수 i, j, k에 대해서 a = A[i], b = A[j], c = A[k]라 하자. 세 수의 중위(Median)값은 정렬했을 때 가운데에 오는 수가 된다. 세 수의 평균(Mean)값은 (a+b+c)www.acmicpc.net 문제 요약주어지는 N개의 정수 중 세 개의 수를 골랐을 때 중위값과 평균값의 차이의 최댓값을 세 배 곱하여 출력하는 문제이다. 접근선택된 세 개의 수를 오름차순으로 $a, b, c$라고 하자. 중위값은 $b$이고, 평균값은 $\dfrac{a+b+c}{3}$ 이다.세 배 곱하여도 최대인 경우의 $a, b, c$는 변하..