PS 일지

문제 풀이를 재미있게 해주는 랜덤 디펜스 확장 프로그램을 발견했다.매번 직접 하기 귀찮기도 해서 한 번 체험해보았다. BOJ 17827 - 달팽이 리스트Silver 2Elapsed Time : 7m 55s Rating : 1000 -> 1029 (+29)#implementation 사이클의 길이를 구해서 $K$를 적절히 $N$밑으로 내려주면 된다. BOJ 4358 - 생태학Silver 2Elapsed Time : 3m 12sRating : 1029 -> 1055 (+26)#map map으로 나온 횟수 저장 BOJ 15787 - 기차가 어둠을 헤치고 은하수를Silver 2Elapsed Time : 9m 24sRating : 1055 -> 1078 (+23)#bitmask 각각의 기차는 비트마스크를 이..

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

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