[9095번] 1, 2, 3 더하기
문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 문제접근법. 규칙을 발견해야 문제를 해결할 수 있다. 점화식만 보고 직관적으로 이해가 되면 좋겠지만, 대부분이 그렇지 않을 것이다. n = 4 라는 예제를 통해서 이해도를 높여보자. n >= 4 일 때, f(n) = f(n - 1) + f(n - 2) + f(n - 3)이다. n = 1 일 때, 1 n = 2 일 때, 1 + 1 / 2 n = 3 일 때, 1 + 1 + 1 / 2 + 1 / 1 + 2 / 3 n..
[11722번] 가장 긴 감소하는 부분 수열(DP)
가장 긴 감소하는 부분 수열 성공 문제 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. 문제접근법. 1. 하나의 원소를 기준으로 가장 긴 문자열을 찾아야 한다. 2. 반복적으로 특정 원소를 기준으로 한 연산이 없도록 한다.(메모이제이션) 앞선 코드와 비슷하지만, 재귀함수 호출없이 문제를 풀 것이다. DP[i]는 해당 인덱스(i)에서 시작해서 가장 길게 만들 수 있는 값을 저장한다. 다음과 같은 재귀식을 만들 수 있다. DP[i]를 정의하는 것이 가장 중요하다. 처음에, DP[i]를, ..
[11722번] 가장 긴 감소하는 부분 수열
가장 긴 감소하는 부분 수열 성공 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 256 MB 8943 5611 4608 64.828% 문제 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. 문제접근법. 1. 하나의 원소를 기준으로 가장 긴 문자열을 찾아야 한다. 2. 반복적으로 특정 원소를 기준으로 한 연산이 없도록 한다.(메모이제이션) 해설코드(C++) 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 2..
[2257번] 화학식량 (스택 풀이)
지난 번, 재귀함수 풀이에 이어서 스택 풀이입니다. 문제 접근법. 1. 괄호에 대해서 먼저 연산을 할 필요가 있다. 2. 숫자가 있는 경우, 앞에 있는 문자나 괄호식에 대해서 곱셈을 해줘야 한다. 괄호와 같은 우선 순위가 필요한 연산일 경우, 적합한 자료구조는 스택입니다. 스택을 이용해서, 특정 우선 순위에 대해서 먼저 처리해주는 것이 필요합니다. H, C, O에 대해서는 해당하는 숫자(1, 14, 16)를 넣어줍니다. (은 우선순위 연산을 위해서 사용되므로, 그대로 넣어줍니다. )의 경우에는 (를 만날 때까지 만나는 숫자들을 모두 더하도록 처리합니다. 숫자의 경우에는 스택의 Top에 대해서 곱셈을 처리해서, *다시 숫자를 넣어줍니다. * )의 경우에 모든 숫자를 더할 수 있는 이유는, 스택에 들어가는 ..
