선릉역 1번 출구

problem. 0으로 시작x, 1은 연속으로 들어갈 수 없음 key point 1 2 1 10 0으로 시작할 수 없으니 길이가 1인 경우는 1뿐이다. 그리고 길이가 2인 경우는 1뒤에 1이 연속으로 올 수 없기 때문에 10뿐이다. 핵심 포인트는 1뒤에는 1이 올 수 없으니 길이가 n이면서 마지막 숫자가 1인 경우는 n-1에서 마지막 숫자가 0으로 끝나는 수와 같다. 0의 경우는 1, 0 뒤에 모두 올 수 있기 때문에 이전 n-1의 sum()값이다. 그럼 이제 배열은 선언해주어야 하는데 type이 0, 1 2개이기 때문에 dp[n + 1][2]으로 선언을 해준다. n = int(input()) dp = [[0 for _ in range(2)] for _ in range(n + 1)] dp[1][1] = ..

problem. 계단 수 = 인접한 수가 1씩 차이가 나는 수임. (a-b) = ±1이라는 말, 길이가 n인 계단 수의 갯수를 구하는 문제 ※ 0으로 시작 x 그러나 10은 가능 key point 1 2 1, 2, 3, 4, 5, 6, 7, 8, 9 = 9개 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 = 17개 [1, 1, 2, 2, 2, 2, 2, 2, 2, 1] 1 -> 2로 갈 때 특별한 규칙은 맨 마지막 숫자의 경우 0, 9 -> 1, 8의 갯수에 영향을 받고, 나머지 1, 2, 3, 4, 5, 6, 7, 8은 이전 배열의 ±1한 값들의 덧셈이라는 것이다. 0 = d..

Problem. 1, 2, 3으로 표현하되 두 번 연속 사용 x key point 1 2 3 1 2 1, 2 2, 1 3 기본 셋팅 값이 된다. 4 5 6 1, 3(o) 2, 2(x) 1, 2, 1(o) 2, 1, 1(x) 3, 1(o) 2, 3(o) 1, 2, 2(x) 2, 1, 2(o) 3, 2(o) 1, 3, 1(o) 2, 2, 1(o) 1, 2, 1, 1(x) 2, 1, 1, 1(x) 3, 1, 1(x) pass 표현할 수 있는 숫자가 1, 2, 3 총 3개이기 때문에 n 번째 숫자의 값을 찾기 위해서는 n-1, n-2, n-3을 보면 된다. 더 자세하게는 n-1은 +1이 될 값들의 list이기 때문에 1로 끝나지 않는 숫자들의 개수를 알아야하고 같은 논리로 n-2는 2로 끝나지 않는 숫자들의 개..

동적 계획법이라고 불리는 다이나믹 프로그래밍에 대해서 알아보자. 동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법으로, 부분 문제 반복과 최적 부분 구조를 가지고 있는 문제를 일반적인 방법에 비해 적은 시간안에 풀 때 사용한다. 기본 structure는 앞서 말한 것처럼 문제를 여러 하위 문제로 나눠 풀고, 그것을 결합해 최종적인 답을 도출해내는 것이다. 이 방법을 사용하면 계산횟수를 획기적으로 줄일 수 있어 하위 문제의 수가 많을 때 유용하다. 이 과정에서 메모이제이션(memoization)이라는 기술이 사용된다. +메모이제이션: 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장해 동일한 계산의 반복 수행을 제거해 프로그램 실행 속도를 빠르게 하..