'fibonacci sequence' 태그의 글 목록
본문 바로가기
728x90

fibonacci sequence3

Dynamic programming (동적 계획) // Dynamic programming What is Dynamic programming? 이란, 문제의 입력사례를 분할하여 문제를 푸는 것이다. 흔히들 'DP'라고 많이 한다. 이 점은 분할정복과 비슷하지만, 분할정복은 Top-down(하향식) 접근방법이고 은 Bottom-up(상향식) 접근방법이다. 또한 의 특징은 이미 계산된 부분 문제가 다시 발생하면 또 계산을 하는 것이 아닌 이전의 계산값을 참조한다는 것이다. Example 우리는 의 예시로 를 들 수 있다. 좌측 삽입한 링크에 들어가면 을 사용하여 를 구현한 예시를 볼 수 있다. "Top-down(하향식) 접근방법 이란?" * 큰 문제에서 작은 부분문제를 재귀적으로 호출하여 리턴 되는 값을 이용하여 큰 문제를 해결하는 방식 "Bottom-up.. 2020. 11. 9.
Fibonacci sequence (피보나치 수열) // Fibonacci sequence What is Fibonacci sequence? 란, 임의의 항의 값이 이전의 두 항의 값을 더한 값을 가지는 수열을 의미한다. 이를 점화식으로 표현하면 아래와 같다. An = 1 , ( n > n; // *********** Dynamic programming *********** Fibonacci_dynamic[0] = 0; Fibonacci_dynamic[1] = 1; for (int i = 2; i > num; cout 2020. 11. 6.
백준 No.1904 [01타일] // Baekjoon Online Judge No.1904 [01 타일] How to solve 복잡할 것 같아 보이지만 N에 1, 2, 3 ... 8 까지만 대입 해보아도 결국 피보나치수열을 이룬다는 것을 알 수 있다. 하지만 이 문제에서 고려해야하는 점이 두 가지 있다. 1. 피보나치 수열을 구하는 함수를 구현할 때 1,000,000번째 항까지 구해야 하므로 Time out 이 생기지 않을 방법으로 함수를 구현하여야 한다. 2. 아무리 unsigned long long 자료형을 가진다고 해도 1,000,000번째 피보나치수는 overflow를 발생시킨다. "1. 피보나치 수열을 구하는 함수를 구현할 때 1,000,000번째 항까지 구해야 하므로 Time out 이 생기지 않을 방법으로 함수를 구현하여.. 2020. 11. 6.
728x90