[문제 링크]https://www.acmicpc.net/problem/11053문제 설명수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50} 이고, 길이는 4이다. 입력첫째 줄에 수열 A의 크기둘째 줄에 수열 A를 이루고 있는 원소들출력가장 긴 증가하는 부분 수열의 길이입출력 예시입력예시출력예시610 20 10 30 20 504 문제 풀이다이나믹 프로그래밍으로 풀이dp[i] : array[i]를 마지막 값으로 가지는 증가 부분 수열들 중에서 가장 긴 부분수열의 길이array[i]가 어떠한 증가 부분 수열의 마지막 값이 되려면, ar..

문제 설명두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B를 만들고자 한다.문자열 A를 편집하여 문자열 B로 만들기 위해 사용하는 연산의 수를 '편집 거리'라고 할 때, 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요.문자열을 편집할 때는 다음의 세 연산 중 한 번에 하나씩 선택하여 편집한다.1. 삽입(insert) : 특정한 위치에 하나의 문자를 삽입합 니다.2. 삭제(remove) : 특정한 위치에 있는 하나의 문자를 삭제합니다.3. 교체(replace) : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다. 입력조건문자열 A, B출력조건문자열 A, B간의 최소 편집 거리입출력 예시입력예시출력예시catcut1sundaysaturday3 ..

[문제 링크]https://www.acmicpc.net/problem/2579문제 설명계단 오르기 게임은 계단 아래 시점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다.과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다.1. 계단은 한 번에 한 계단 or 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면 이어서 다음계단이나, 다음다음계단을 밟은 수 있다.2. 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 포함되지 않음3...

문제 설명못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미한다.(즉, 오직 2, 3, 5를 약수로 가지는 합성수)1은 못생긴 수라고 가정하고, 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...} 순으로 이어지게 된다. 이 때, n번째 못생긴 수를 찾느 ㄴ프로그램을 작성하세요. 입력조건첫째 줄에 n출력조건n번째 못생긴 수 출력입출력 예시입력예시출력예시101244 문제 풀이다이나믹 프로그래밍 풀이못생긴 수에 각각 2의 배수, 3의 배수, 5의 배수를 곱한 값도 못생긴 수가 된다.예를 들면, 문제에서 1, 2, 3, 5 는 못생긴 수 임을 알 수 있다. 이 때 각 못생긴 수에 2의 배수, 3의 배수, 5의 배수를 구하면 다음과 같다.못생긴 수 배수한 값..

다이나믹 프로그래밍이란? 큰 문제를 작은 문제로 쪼개고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.다이나믹 프로그래밍을 구현하는 방법에는 작은 문제를 재귀적으로 호출하는 방식인 Top-Down(하향식)작은 문제부터 하나씩 해결해나가면서 답을 도출하는 방식인 Bottom-Up(상향식)예제 1) 1로 만들기정수 X가 주어지고 다음 연산을 적절히 사용해서 1을 만드려고 할 때, 연산을 사용하는 횟수의 최솟값을 출력하시오.- X가 5로 나누어 떨어지면, 5로 나눈다. - X가 3로 나누어 떨어지면, 3로 나눈다. - X가 2로 나누어 떨어지면, 2로 나눈다. - X에서 1을 뺀다. 문제 해설Bottom-Up 방식 사용문제의 규칙을 찾아보면 다음과 같다.f(1) = 0f(2) =..

문제 설명맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하세요.아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 or 대각선 오른쪽에 있는 것 중에서만 선택할 수 있습니다. 입력조건첫째 줄에 삼각형의 크기둘째 줄부터 n+1번째 줄까지 정수 삼각형출력조건합이 최대가 되는 경로에 있는 수의 합입출력 예시입력예시출력예시5 7 3 8 8 1 02 7 4 4 4 5 2 6 54 문제 풀이다이나믹 프로그래밍으로 풀이'금광' 문제와 비슷한 유형의 문제이다.정수삼각형의 수들을 배열에 저장하면, 윗층에서 현재 위치로 내려올 수 있는 경우는 2가지가 있다.(왼쪽 위 or 바로 위)이 두가지 경우 중에서 더..