CS STUDY

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 처음에 숫자를 일일히 써가면서 규칙을 찾는데 엄청 고생했는데 다음과 같이 풀이하는 방법이 더 효율적이다. 위 표는 마지막 자리 숫자가 무엇일때 생성될수 있는 가지수를 적어놓은 것이다. 예를 들어 dp[2][1]은 21 이렇게 하나밖에 존재 하지 않고 dp[2][3]은 23,43 두개가 존재한다. 위처럼 작성해 놓으니 규칙을 쉽게 발견할수 있는데 빨간 화살표처럼 왼쪽 오른쪽 대각선 원소의 합이다. 생각해보면 당연한게 5가 맨 뒷자리에 오려면 앞에 4나 6이 와야 하기 때문에 4나 6이 오는 경우의 수를 모두 합해..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 이러한 유형의 문제는 가능한 조건을 미리 정리해놓고 풀이하는게 더 좋은 방법인것 같다. 특히 첫번째 부터 규칙을 찾으려고 하면 번거롭기 때문에 적당히 i값을 0이 아닌 4,5 정도의 값을 설정하고(규칙에 따라 유동적으로) 앞의 원소들을 체크하면서 풀이해야한다. 위 문제의 조건을 바탕으로 가능한 경우는 3가지가 있다. 1. i 번째 포도주를 마시면서 i-2번째 포도주까지 마셔온 경우 (arr[i] +..

https://leetcode.com/problems/fibonacci-number/ Fibonacci Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 재귀 구조 브루트 포스 class Solution: def fib(self, n: int) -> int: if N int: if n int: self.dp[1]=1 for i in range(2,n+1): self.dp[i] = self.dp[i-1] + self.dp[i-2] return s..

다이나믹 프로그래밍 방법론 피보나치 수열의 예제 코드를 보면 상향식과 하향식의 구분이 금방 이해 된다.