YANGORITHM

문제 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] =..

문제 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 1부터 N까지의 수 중에서 조합을 해서 N을 만드는 경우의 최대값을 구하는 문제이다. D[N]을 N개를 갖기 위해 지불하는 최대 금액으로 한다. N이 4라고 하고 P[1] ~ P[4]까지 카드의 금액이 주어진다고 하면 ○ + ○ + ○ + ● = 4 에서 ●에 올 수 있는 수는 1, 2, 3, 4 가 된다. 그럼 가능한 점화식은 다음이 된다. D[4] = max { D[4-1] +P[1], D..

문제 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 풀이 9개 중에서 7개를 골라서 더하여 100을 만드는 것보다, 9개의 합에서 2개씩 순서대로 묶어서 빼다가 100이 되는 순간 출력을 하면 된다. 코드 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #includ..

문제 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 풀이 점수가 최대가 되야하므로 점수를 내림차순으로 정렬해서 선택한다. 그리고 마감일이 오래 되는 과제는 당장 해결 할 필요가 없으므로 미룰 수 있을 만큼 미뤄야 한다. 이를 위해 배열 due를 만들어서 이 배열에다 선택 된 과제들만 저장한다. 1. index에 마감일을 저장 2. 마감일이 중복이 아니면 (due[index] == 0) 점수 저장 (마감일까지 과제를 최대한 미룸) 3. 마감일이 중복되면 (due[index] != 0) -..