가장 긴 증가하는 부분 수열1 초256 MB169140679584509838.082%문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.예제 입력 1 복사610 20 10 30 20 50예제 출력 1 복사4가장 긴 증가하는 부분 수열(LIS, Longest Incr..

동적 프로그래밍(Dynamic Programming, DP) 알고리즘은 문제를 작은 하위 문제들로 나누어 해결한 다음, 그 결과를 결합하여 원래의 문제를 해결하는 기법입니다. DP는 주로 다음 두 가지 특징을 가진 문제에 사용됩니다:중복되는 하위 문제:동일한 하위 문제가 여러 번 반복해서 계산되는 경우.최적 부분 구조:문제의 최적 해가 하위 문제들의 최적 해로 구성될 수 있는 경우.DP 알고리즘은 크게 두 가지 방식으로 구현됩니다:탑다운(메모이제이션, Memoization):재귀를 사용하여 문제를 푸는 방식입니다.이미 계산된 하위 문제의 결과를 저장해두고, 동일한 하위 문제가 다시 등장할 때 저장된 값을 재사용합니다.이 방식은 재귀 호출로 인해 스택 오버플로우가 발생할 수 있으므로 주의가 필요합니다.바텀..

우유 축제 1 초256 MB76094512400361.115%문제영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다.입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다.맨 처음에는 딸기우유를 한 팩 마신다.딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다.초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다.바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다. 영학이는 우유 축제가 열리고 있는 우유거리에 왔다. 우유 거리에는 우유 가게들이 일렬로 늘어서 있다.영학이는 우유 거리의 시작부터 끝까지 걸으면서 우유를 사먹고자 한다.각각의 우유 가게는 딸기, 초코, 바나나 중 한 종류의 우유만을 취급한다.각각의 우유 가게 앞에서, 영학이는 우유를 사마시거나, 사마시지 않는다.우유거리..

한조서열정리하고옴ㅋㅋ2 초256 MB115764740383740.638%문제“반갑다. 내 이름은 반고흐#31555! 조선 최고의 활잡이지. 오늘도 난 금강산 위에서 적들을 노리고 있지. 내 앞에 있는 적들이라면 누구도 놓치지 않아! 좋아, 이제 곧 월식이 시작되는군. 월식이 시작되면 용이 적들을 집어삼킬 것이다. 잘 봐두어라! 마장동 활잡이 반고흐#31555님의 실력을-!”반고흐#31555는 자기 뒤쪽 봉우리에 덩기#3958이 있음을 전혀 모르고 있었다. 덩기#3958도 반고흐#31555와 마찬가지로 월식이 시작되면 용을 불러내어 눈앞에 있는 다른 활잡이들을 모두 처치할 생각이다. 사실, 반고흐#31555와 덩기#3958 뿐만 아니라 금강 산맥의 N개 봉우리에 있는 모든 활잡이들이 같은 생각을 가지고 있..

거스름돈1 초128 MB45753299952555965.531%문제타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.입력입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.출력제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.예제 입력 1 복사380예제 출력 1 복사4예제 입력 2 복사1예제 출력 2 복사15코드package 거스름돈;import java.io.Bu..

A → B2 초512 MB55712229191817439.686%문제정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.2를 곱한다.1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.입력첫째 줄에 A, B (1 ≤ A 출력A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.예제 입력 1 복사2 162예제 출력 1 복사52 → 4 → 8 → 81 → 162예제 입력 2 복사4 42예제 출력 2 복사-1예제 입력 3 복사100 40021예제 출력 3 복사5100 → 200 → 2001 → 4002 → 40021접근법이 문제는 정수 A를 B로 바꾸기 위해 가능한 두 가지 연산을 이용하여 최단 경로..

동전 01 초256 MB149950803616135552.637%문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)출력첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.예제 입력 1 복사10 4200151050100500100050001000050000예제 출력 1 복사6예제 입력 ..

1. 그리디 알고리즘(탐욕법, Greedy Algorithm) 이란?그리디 알고리즘은 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로, 각 단계에서 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘입니다. 이때 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 근사한 값을 목표로 합니다. 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 사용됩니다.예시 문제노드에서 가장 합이 높은 방법을 선택하는 방법을 생각해봅니다. 이 경우, 그리디 알고리즘은 기준 없이 선택하는 대신, 상황에서 가장 높은 수를 선택하는 방식으로 노드를 선택합니다.2. 그리디 알고리즘 주요 속성그..