Ama_gramer

📖문제01타일  ❓구상패턴의 개수를 파악하는 문제는 작은 규모의 패턴을 파악해서 해결하기 좋은 동적 프로그래밍(Dynamic Programming)계획법으로 풀기 적합한 문제이다.일반적인 이진법이라면 N이 1일때 0과 1을 만들 수 있기 때문에 2가 나와야하지만, 이 문제의 조건을 살펴보면 아래와 같다.1. 이진법을 구성할 때 1과 00의 조합으로만 구성을 해야한다.2. 0은 01 혹은 10 처럼 사용할 수 없고 0이 2개가 붙어있어야한다.주어진 N에 따라 표현될 수 있는 이진법의 종류를 알아보면 패턴을 파악할 수 있을것으로 기대된다. 🎲 패턴N이 1일때 부터 7일때 까지의 패턴을 파악한 결과 피보나치 수열처럼 dp[i] = dp[i-1] + dp[i-2] 의 패턴을 가지고 있음을 알 수 있다.이 것..

동적계획법, DP(Dynamic Programming)동적계획법은 한번 처리한 데이터에 다시 접근할 때마다 다시 계산하는 것이 아닌, 저장해둠으로 다음 처리에서 다시 활용 할 수 있게 해주는 알고리즘 패러다임이다.최적화 이론의 한 기술이며, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.- MDN 동적계획법이라고 하면 어떤 패러다임인지 바로 알아차리기 어려운데, 이는 쉽게 생각하자면 "기억하며 풀기" 라고 하면 조금 더 이해하기 쉬울 것 같다.동적계획법, DP(Dynamic Programming) 패러다임 조건 및 구조동적 계획법 조건동적계획법을 적용하기 위해 필요한 조건에는 크게 4가지가 있다.중복되는 하위 문제하위의 문제가 재..