[문제 링크]https://www.acmicpc.net/problem/18353문제 설명N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있고, 병사를 배치할 때는전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다.배치 과정에서는 특정 위치에 있는 병사를 열외시키는 방법을 이용하고, 남아있는 병사의 수가 최대가 되도록 하고자 한다.병사에 대한 정보가 주어졌을 때, 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력하는 프로그램을 작성하시오. 입력조건첫째 줄에 병사의 수 N둘째 줄에 각 병사의 전투력출력조건남아있는 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수 입출력 예시입력예시출력예시715 11 4 8 5 2 42 문제..

[문제 링크]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) =..