본문 바로가기

코딩 테스트/Dynamic Programming

 (4)
[프로그래머스] 멀리 뛰기(Lv 2) with Kotlin 문제 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다. 풀이 과정 1칸 : 1가지 2칸 : 2가지 1 1 2 3칸 : 3가지 1 1 1 1 2 2 1 4칸 : 5가지 위의 예제 5칸 : 8가지 1 1 1 1 1 2 1 1 1..
[프로그래머스] 피보나치 수(Lv 2) with Kotlin 문제 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요. 풀이 과정 피보나치 수는 다이나믹 프로그래밍의 대표적인 문제이므로 DP를 사용하여 해결한다. 코드 class Solution { fun solution(n: Int): Int { val dp = Array(n+1)..
[프로그래머스] 멀리 뛰기 with Kotlin 문제 한 번에 1칸 또는 2칸 뛸 수 있으며, 칸이 N으로 주어졌을 때 N까지 뛸 수 있는 모든 경우의 수의 개수를 반환하는 문제 풀이 과정 1칸 : 1 2칸 : 2 3칸 : 3 4칸 : 5 5칸 : 8 다음과 같은 규칙으로 증가하는 피보나치 수이므로 다이나믹 프로그래밍을 사용하여 해결할 수 있다. 코드 class Solution { fun solution(n: Int): Long { if(n == 1) return 1 val dp = Array(n){0} dp[0] = 1 dp[1] = 2 for(i in 2 until n){ dp[i] = (dp[i-1] + dp[i-2]) % 1234567 } return dp[n-1].toLong() } }
[프로그래머스] 피보나치 수 with Kotlin 문제 n번째 피보나치 수의 값에 1234567을 나눈 나머지 값을 구하는 문제 제한 사항 2

티스토리툴바