아무 말

https://www.acmicpc.net/problem/9002 9002번: Match Maker Print exactly one line for each test case . The line should contain a stable match for the test case. Each match should be represented as a sequence of the women’s id, according to the increasing order of men ’s id. The woman with the first id in the www.acmicpc.net 풀이 여자와 남자를 정점으로 하고 모든 여자와 남자를 간선으로 이으면 이는 이분 그래프를 띤다. 안정된 매칭을 만들기 위해서 아래와 같..

10403번: 나머지 https://www.acmicpc.net/problem/10430 10430번: 나머지 첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000) www.acmicpc.net 그냥 문제에서 원하는걸 출력하자. 생각을 할 필요조차 없다. 1 2 3 4 5 6 7 #include int main(){ int A,B,C; scanf("%d%d%d",&A,&B,&C); printf("%d\n%d\n%d\n%d",(A+B)%C,(A+B)%C,(A*B)%C,(A*B)%C); return 0; } Colored by Color Scripter cs 4373번: 1 https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어..

https://www.acmicpc.net/problem/9008 9008번: Castle Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with integer n, the number of points, where 4 ≤ n ≤ 10,000. Each of the following www.acmicpc.net 사용 알고리즘 깊이 우선 탐색 정렬 풀이 문제의 "the interior angle formed by its two incident edge..

https://www.acmicpc.net/problem/9061 9061번: 두 직사각형 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스는 첫 줄에 자연수 N (1 ≤ N ≤ 10000) 이 주어지며, 그 이후 N www.acmicpc.net 사용 알고리즘 세그먼트 트리 (초반에 생각을 못해서 세그먼트 트리를 이용했다.) 정렬 풀이 그냥 x좌표나 y좌표 중 하나로 잡고 정렬해서 모든 점에 대해서 그 점을 기준으로 두 직사각형을 만들어서 답을 구하면 된다. 이때 두 직사각형은 모든 점을 다 포함해야 함으로 왼쪽과 오른쪽에 있는 모든 점들의 y좌표의 최대값과 최소값을 알아야 한다. 이를 구하기 ..

https://www.acmicpc.net/problem/22345 22345번: 누적 거리 KOI 나라는 수직선 위에 놓인 N개의 마을로 구성되어 있다. 이 중 i (1 ≤ i ≤ N)번째 마을은 xi 위치에 놓여 있으며 ai명이 거주 중이다. 또한 서로 다른 두 마을이 같은 위치에 놓인 경우는 없다. KOI www.acmicpc.net 이전에 포스팅한 Stadium이라는 문제와 매우 유사하다. 다만 이 문제에서는 x좌표가 정렬이 되어있지 않으므로 정렬을 해주어야 한다. 그리고 주어지는 후보지점에서의 값을 계산해주면 된다. Stadium에서는 변화량에 집중하였다면 이번에는 그냥 계산하면 된다. 누적 거리를 구하기 위해서는 각 쿼리가 어떠한 두 마을 사이에 있는지 알아야 하며, 이를 이분탐색을 통해 찾아..

https://www.acmicpc.net/problem/9027 9027번: Stadium Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of three lines. The first line of each test case contains an integer N (1 < N ≤ 1 www.acmicpc.net 문제가 영어로 되어 있으므로 문제에 대한 간단한 설명을 하겠다. $$ \sum_{i=1}^N \left| x-x_i \right| - ..

간단한 설명 병합 정렬은 존 폰 노이만에 의해 고안된 알고리즘이다. 병합 정렬은 분할정복 기법을 이용하며 다음과 같이 작동한다. 분할: 정렬할 n개 원소의 배열을 n/2개 씩 부분 수열 두 개로 분할한다. 정복: 병합 정렬을 이용해 두 부분 배열을 재귀적으로 정렬한다. 결합: 정렬된 두 개의 부분 배열을 병합해 정렬된 배열 하나로 만든다. 계속해서 분할을 하다 보면 원소의 수가 하나가 되고 이는 원소가 하나임으로 이미 정렬된 수열이다. 이 하나의 원소로 이루어진 부분수열로 부터 각 부분수열을 병합해가면서 정렬하는 알고리즘이 바로 병합 정렬이다. 알고리즘의 설계 알고리즘의 설계를 위해 트리를 하나 생각해보자. 이 트리의 각 정점에는 두 개의 자식노드가 있고(물론 한개의 자식만 가질수도 있다.) 맨 아래쪽의..

삽입 정렬은 수를 정렬된 상태로 삽입함으로서 정렬하는 방법이다. A라는 배열이 있을 때 {A[1]}을 초기에 정렬된 배열이라고 하고 이 배열의 처음부터 끝까지를 확인하면서 A[i]보다 큰 수가 나오면 그 자리에 A[i]를 삽입한다. 이때 원래 자리에 있던 수를 비롯한 A[i]보다 큰 수들은 한 칸씩 뒤로 밀리게 된다. 또한 이 정렬된 배열을 따로 만들지는 않으며, A의 앞부분에 나타낸다. INSERTION-SORT(A) for j=2 to A.length key=A[j] i=j-1 while i>0 and A[i]>key A[i+1]=A[i] i=i-1 A[i+1]=key 위는 배열 A에 대한 삽입 정렬의 의사코드이다. A.length는 수의 개수이고 key는 현재 정렬해야하는 수를 의미한다. 삽입정렬에..

문제링크: https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net D[i][j]={i개의 색 중, j개의 색 선택시 문제의 답} 이라고 정의하겠다. D[i][j]를 점화식으로 표현하기 위해서 case1) i번째 색을 선택한다. case2) i번째 색을 선택하지 않는다. 위와같이 케이스를 나누어서 생각했을때 D[i][j]= case1) + case2) 이다. case1) 과 case2) 를 D로 나타내면 다음과 같다. case1) D[i-2][j-1] (i번째 색을 선택했으므..

이 문제는 DP로 해결할 수 있다. 먼저 D[i][j][p]를 i~j까지의 가로등이 꺼져있고, p가 0일때 마징가는 i, p가 1일때 마징가는 j의 위치에 있는 상태에서 가로등 끄기를 시작했을때 낭비되는 최소한의 전력이라고 정의한다. 따라서 처음 시작위치는 M번째 가로등이므로 D[M][M][0] or D[M][M][1]의 값을 구해주면 된다. 수가 늘어나는 방향을 오른쪽, 그 반대방향을 왼쪽이라고 하면, 마징가가 현재위치에서 왼쪽, 오른쪽으로 이동하는 상황을 나누어 생각해주면 된다는 것을 쉽게 알 수 있다. 이를 생각하면 D[i][j][p]=min(D[i-1][j][0]+'이 경우 이동에 사용되는 전력', D[i][j+1][1]+'이 경우 이동에 사용되는 전력') 저 경우에 따른 이동에 사용되는 전력은 ..