DP

💻 Problem문제 보러 가기 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. 💡 Approachdp 배열에서 index는 현재 금액이고 value는 N가지 동전으로 현재 금액을 만들 수 있는 방법의 수이다. 예를 들어, 2원과 4원으로 8원을 만든다고 하겠다.N=2, coins=[2, 4], M=8우리가 간단히 생각해 본다면 2+2+2+2, 2+2+4, 4+4 세 가지 ..

💻 Problem문제 보러 가기 45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 💡 Approach이게 실버 문제라니! DP 너무 어려웡ㅠ처음 접근할 때는 수의 첫 번째 자리를 기준으로 생각했다.맨 처음에는 9개의 숫자가 올 수 있고.. 그다음 자리는 2개의 숫자가 올 수 있고..0이나 9일 때를 고려해야 하고.. 너무....복잡햇......... 이 글을 보고 이해할 수 있었다.음음.. 가장 끝 자리에 오는 숫자를 기준으로 했어야 하는 거구나 i는 자릿수이고 j는 끝자리 숫자이다.예를 들어, i=2, j=4, dp[2][4]=2이면 두 자릿수..

💻 Problem문제 보러 가기 효빈이는 어떤 수열에서 군계일학 수열을 뽑아내고자 한다. 단, 뽑은 항의 순서는 기존 수열에서의 순서를 유지해야 한다. 군계일학 수열은 각 항이 서로 연속적인 수열을 의미한다. 정확한 정의는 다음과 같다.수열 중에 어떤 임의의 항 i에 대해서, ai=a1+(i-1)을 만족해야 한다.길이가 N이고 정수로 이루어진 수열이 주어진다. 효빈이는 가장 긴 군계일학 수열을 가져가서 김승호 선생님께 자랑하려고 한다. 효빈이가 뽑아낼 수 있는 가장 긴 군계일학 수열의 크기를 출력하라. 💡 Approach문제에서 a[i] = a[1] + (i - 1)를 만족해야 한다고 나와있다.이 식은 등차가 1인 등차수열이다.즉, a[i] = a[i - 1] + 1을 만족하면 된다. 해당 문제의 시..

💻 Problem문제 보러 가기 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1 ^ 2의 합이다; 또한 4 ^ 2 + 3 ^ 2 + 1 ^ 2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125 ^ 2 + 6 ^ 2 + 1 ^ 2 + 1 ^ 2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105 ^ 2 + 15 ^ 2 + 8 ^ 2 + 5 ^ 2.자연수 n이 주어..

💻 Problem문제 보러 가기  N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.  💡 Approach이 문제의 시간 제한은 0.25초이다.1초가 약 1억이니 0.25초면 약 25,000,000이다.피보나치의 기본 재귀 코드는 시간복잡도가 2^n이기에 재귀로 풀면 안 된다. 피보나치 수열은 n이 2 이상일 때, f(n) = f(n-1) + f(n-2) 이다.재귀로 풀면 f(n)을 구할 때, f(n-1)을 구하기 위해 f(n-2)를 계산했음에도 f(n-2)를 다시 구해서 f(n-1)과 더해야 한다. 사진으로 보면 이해하기 더 쉽다.위 사진에서 f(5)를 구하려고 할 때, 중복 계산이 여러 번 발생하는 것을 확인할 수 있다. DP..