[백준(baekjoon) 11047] 동전 0 문제 백준 11047 N개의 종류의 동전의 가치 Ai가 주어질 때 (각 종류의 동전은 무한히 많다.) 동전 들을 사용해 K원을 만들려고 한다. 이때, 필요한 동전 종류 개수의 최소 값은? 주의 : A1 = 1은 Default이며, i > 1을 만족하는 Ai = Ai-1의 배수이다. 해결 처음에는 DP를 사용해야 하나 했다. N = 3, K = 2000, A1 = 100, A2 = 500, A3 = 800의 경우 정답은 A2 * 4 = 2000이 되기 때문에. 하지만, 역시 문제는 자세히 읽어야 한다…! i > 1을 만족하는 Ai = Ai-1의 배수이다. 이 부분에 의해서 그리디 알고리즘으로 문제를 해결할 수 있다. 가장 큰 동전 종류부터 확인, 차액을 구하여..

문제 백준 1912 n(1…100,000)과 n의 크기를 가진 수열이 주어질 때, 연속된 숫자들의 합 중 최대 값을 출력하라. 예시 : {10, -4, 3, 1, 5, 6, -35, 12, 21, -1}일 때, 12+21인 33이 정답이 된다. 해결 간단하게 앞에서 부터 시작해서 각 값으로 끝나는 연속된 수열의 최대 합을 구하면 된다. 자신으로 시작하는 경우 이전 연속 수열에 자신을 포함하는 경우 이렇게 두 가지의 경우로 나눌 수 있으므로, 두 값을 비교해서 큰 값을 저장하면 된다. 시간복잡도는 O(N)이다. 알고리즘 DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다. DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자. 구현 java Top-down 방식 1.imp..

[백준(baekjoon) 11054] 가장 긴 바이토닉 부분 수열 문제 백준 11054 n(1…1,000)과 n의 크기를 가진 수열이 주어질 때, 바이토닉 부분 수열 중 가장 긴 길이를 출력. 바이토닉 수열 : S1 Sk+1 > … SN-1 > SN을 만족하는 수열 예시 : {10, 20, 30, 25, 20}, {10, 20, 30, 40}, {50, 40, 25, 10} 주의 : 증가, 감소 수열도 바이토닉 수열에 속한다. 해결 가장 긴 증가하는 부분과 매우 유사한 문제이다. 2중 for문의 형태이고, 시간 복잡도는 O(n^2)이다. 최대 1000 * 1000 = 1,000,000이 되고, 1초(1억)을 넘지 않는다. 여기서 다른 점은, 증가하는 부분과 감소하는 ..

[백준(baekjoon) 11722] 가장 긴 감소하는 부분 수열 문제 백준 11722 n(1…1,000)과 n의 크기를 가진 수열이 주어질 때, 수열에서 감소하는 부분 수열 중 가장 긴 길이를 출력. 예시 : A = {10, 30, 10, 20, 20, 10} 인 경우, A = {30, 20, 10} 이고 길이는 3이다. 해결 가장 긴 증가하는 부분과 매우 유사한 문제이다. 2중 for문의 형태이고, 시간 복잡도는 O(n^2)이다. 최대 1000 * 1000 = 1,000,000이 되고, 1초(1억)을 넘지 않는다. 알고리즘 DP로 풀었고, bottom-up 방식으로만 풀었다. DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자. 구현 java Bottom-Up 방식 1.import java.u..

문제 백준 11055 n(1…1,000)과 n의 크기를 가진 수열이 주어질 때, 수열에서 증가하는 부분 수열 중 가장 큰 합을 출력. 예시 : A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우, A = {1, 2, 50, 60} 이고 합은 113이다. 해결 가장 긴 증가하는 부분과 매우 유사한 문제이다. 이것도 마찬가지로! 2중 for문의 형태이고, 시간 복잡도는 O(n^2)이다. 최대 1000 * 1000 = 1,000,000이 되고, 1초(1억)을 넘지 않는다. 그러므로 일일이 구한 후 MAX 값을 찾아내면 끝! 알고리즘 DP로 풀었고, bottom-up 방식으로만 풀었다. DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자. 구현 java Bottom-Up 방식 ..

[백준(baekjoon) 11053] 가장 긴 증가하는 부분 수열 문제 백준 11053 n(1…1,000)과 n의 크기를 가진 수열이 주어질 때, 수열에서 증가하는 부분 수열 중 가장 긴 길이를 출력. 예시 : A = {10, 20, 10, 30, 20, 50} 인 경우, A = {10, 20, 30, 50} 이고 길이는 4이다. 해결 최소 길이 = 시작 값으로 끝나는 길이(초기) = 1이다. for(i = 1...n-1)문을 돌며 각 값으로 끝나는 부분 수열의 최대 길이를 차례대로 구해 저장한다. 이를 maxLength[i]라고 표현하겠다. 해당 값(input[i])으로 끝나는 증가하는 부분 수열은, 이전의 부분 수열 중 마지막 값이 자신보다 작은 경우 자신을 추가할 수 있다. 즉, 이러한 경우 길이는..