반응형 Dynamic Programming2 [알고리즘] 백준. #1904 01타일 동적 계획법 파트의 또 하나의 문제이다. 알고리즘 수업을 수강한 아는 형의 말이 떠올랐다. 알고리즘은 결국 '점화식'만 잘 짜면 되는거야.. 알고리즘을 잘 알지 못하는 나로서는 이게 맞는 말인지 아닌지 감이 잘 오지 않는다 하하.. 근데 적어도 동적 계획법에 한해서는 점화식만 잘 짜도 반은 먹고 들어가는 거 같다. 이번 문제는 이렇다. 00과 1이라는 타일이 있는데 n이라는 수가 주어졌을 때 이 두 종류의 타일을 이어 붙일 수 있는 경우의 수를 말한다. 00은 타일 2개가 붙어있는 꼴이다. 표로 정리해 보면 다음과 같다. n 1 2 3 4 타일 연속체 1 00, 11 001, 100, 111 0011, 1001, 1111, 0000, 1100 붙일 수 있는 타일 종류의 수 1 2 3 5 뭔가 패턴이 보일.. 2020. 6. 8. [알고리즘] 백준. 2748, 1003 피보나치(동적 계획법) Dynamic programming 파트 중 피보나치 수열에 관한 두 문제이다. 피보나치 수열에 대해 간단히 설명하자면, n번째 피보나치 수는 n-1번째 피보나치 수와 n-2번째 피보나치 수의 합이다. 여기서 n은 2이상의 자연수이고, 초깃값이 n=0, n=1일 때 각각 0, 1로 주어진다. 다음은 n과 이에 대응되는 피보나치 수이다. n 0 1 2 3 4 5 ... 피보나치 수 0 1 1 2 3 5 파이썬으로 구현했는데, 재귀함수 형태로 구현했을 때, pypy3으로 채점을 했는데도 속도가 느렸다. 따라서 다른 방식을 써보기로 했다. 먼저 2748번이다. 입력을 받는데, 90이하의 자연수를 입력값으로 받고 해당 수에 해당하는 피보나치 수를 출력해주면 된다. 필자는 재귀 함수 대신 파이썬의 리스트를 이용해.. 2020. 6. 6. 반응형 이전 1 다음
