YANGORITHM

문제 https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 풀이 수열 D의 숫자들이 반복되는 시작점을 N 이라고 했을 때 반복되는 부분을 제외한 나머지 부분의 개수는 N - 1 개가 된다. 그리고 숫자의 반복이 어디서부터 시작되는지 쉽게 알 수 있도록 그래프를 이용해 수열의 수들을 방문한 점과 방문하지 않은 점으로 구분한다. 결국 그래프에서 사이클을 제외한 길이를 구하는 문제가 된다. 1. A에 해당하는 노드를 방문한다. 방문 순서를 증가한다. 2. A = next(A)를 방문하지 않았다면 방문한다. 방문 순서를 증가한다. 3. 2를 만족한다면 계속 반복한다...

문제 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 풀이 유클리드 호제법을 사용하면 최대 공약수를 쉽게 구할 수 있다. gcd(a, b) 를 a와 b의 최대 공약수라고 하고 a % b = r 이라고 할 때, gcd(a, b) = gcd(b, r) 이다. r이 0 일때 b가 최대 공약수다. https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 위키..

문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 P 배열에서 i 번째 있는 사람은 1번부터 i - 1번째 사람까지 다 더한 값이 된다. 따라서 i 번째 있는 사람의 값이 최소가 되기 위해서는 1번 부터 i-1 번 까지 최솟값으로 이루어지면 된다. 그러므로 P 배열을 내림차순으로 정렬을 하고 P 배열의 값을 더해주면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29..

문제 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. www.acmicpc.net 풀이 가장 긴 증가하는 부분 수열 문제와 유사한 문제다. d[n] = arr[n]을 포함하는 증가하는 부분 수열의 합 이라고 하면 i = 1 부터 i = n-1 까지 증가 하는 부분 수열의 조건에 맞는 d[i]의 최대 값을 구해 arr[..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 풀이 d[n] = arr[n]을 포함하는 가장 긴 부분 수열의 길이라고 하면 d[n]을 구하기 위해서 다음의 규칙이 필요하다. 1. i = 1 부터 i = n-1 까지 arr[i] < arr[n] 이고 2. i = 1 부터 i = n-1 까지 d[i]가 최대인 값. 위 두가지 조건을 동시에 만족..

문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 풀이 세 가지 포도주를 연속적으로 선택할 수 없으므로 n 번째에서 선택을 세 가지 경우로 나눈다. 0이면 포도주를 선택 하지 않..

문제 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 문제 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3& 2&7&8&1&4&5&6 \end{pmatrix}\) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다. 순열을 배열을 이용해 \(\begin{pmatrix} 1 www.acmicpc.net 풀이 사이클을 이루는 그래프의 컴포넌트 수를 구하면 된다. 1번 정점부터 N번 정점까지 돌면서 dfs 탐색을 실행할 때 마다 컴..

문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어 www.acmicpc.net 풀이 이분 그래프 설명: https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B..

문제 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 풀이 N자리 정수가 있을 때, N번째(1의 자리)에 올 수 있는 수는 0~9 이다. 이때 0부터 9까지 각각 N-1의 자리에 올 수 있는 수는 다르다. N=0 이면 N-1=0 이고, N=1 이면 N-1=(0, 1) ......., N=9 이면 N-1=..

문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 N자리 수의 마지막 자리, 즉 1의 자리에는 0부터 9까지 올 수 있다. 이때 0과 9를 제외한 1부터 8까지는 앞 자리에 각각 2개의 수가 올 수 있다. 예를 들어, ○ ○ ○ ◎ ● 의 5자리 수가 있고 ●가 1이면 ◎에는 0, 2 이렇게 두 개가 올 수 있다. 하지만 ●가 0이면 ◎에는 1만 올 수 있다. 마찬가지로 ●이 9여도 앞에 자리에는 8만 올 수 있다. D[N][L] = N자리에 오는 마지막 수 L 이라고 하면 다음과 같은 점화식을 만들 수 있다. D[N][L] = { D[N][L] =..