YANGORITHM

문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 풀이 연속해서 세 개의 계단을 밟을 수 없으므로 n번째 계단에서 가능한 경우는 두 가지가 있다. 1. n-1번째 계단과 n번째 계단을 밟는 경우 2...

문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 n번째 숫자에서 발생하는 비교 연산은 다음과 같다. ( n - 1 번째 숫자까지의 최대값 + arr[n] ) , arr[n] 두 숫자 중 큰 값이 n번째 숫자에서의 최대값이 된다. d[n] = arr[n]을 포함하는 연속된 수열 중 최대값 이라고 하면 다음의 점화식을 구할 수 있다. d[n] = max { ( d[n-1] + arr[i] ), arr[i] } 코드 1 2 3 4 5 6 7 8 9 ..

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 d[k] = A[k]을 포함하는 가장 긴 바이토닉 부분수열 이라고 하면 i = 1 부터 i = k 까지 가장 긴 증가하는 부분 수열과 i = N 부터 i = k 까지 가장 긴 증가하는 부분 수열을 구해서 더하면 된다. 이때 k번째는 겹치게 되므로 -1을 해준다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 ..

문제 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 탐색을 실행할 때 마다 컴..