본문 바로가기
반응형

피보나치 수열5

[C/C++] 백준 #2302 극장 좌석(동적 계획법) #2302 극장 좌석 문제는 수학적인 원리를 이해하면 풀기 편합니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 극장 좌석은 일렬로 최대 40개까지 있을 수 있습니다. 이 중 몇개의 좌석은 이미 고정석으로 채워져 있을 때, 1부터 N까지의 숫자를 채우는 경우의 수를 구하는 문제입니다. 단, 모든 숫자는 자신의 자리 번호와 그 옆자리로 이동을 할 수 있지만, 고정석으로는 이동할 수 없습니다. 극장 자리는 아래와 같이 표시될 수 있습니.. 2023. 4. 20.
[C/C++] 백준 #1904 01타일(피보나치 수열) 이번 문제는 복잡하게 썼지만, 결국 피보나치 수열을 구하는 문제입니다. 길이가 N인 01 타일의 이진수를 얻기 위해서는 길이가 N-1인 01 타일의 이진수에 1이 쓰인 타일을 붙이거나 길이가 N-2인 01 타일의 이진수에 00이 쓰인 타일을 붙여야 합니다. 이것을 식으로 표현하면, \[ d_{0} = 1 \] \[ d_{1} = 1 \] \[ d_{n} = d_{n-1} + d_{n-2} \] 점화식을 보면, 피보나치 수열임을 알 수 있습니다. 단지 시작점이 다른 피보나치 수열이죠. 피보나치 수열을 계산하는 방법은 단순하게 반복문을 돌리는 것이 편합니다. 재귀함수는 아주 시간이 많이 걸리고, 배열을 잡아서 하는 방법도 있지만, 전 그냥 편의상 두개의 변수만을 잡아서 사용했습니다. 제가 작성한 소스입니다... 2022. 11. 1.
[C/C++] 백준 #1646 피이보나치 트리(동적 계획법) 피이보나치 트리 문제는 일견 어려워보일 수 있지만, 조성 방법이 정해져 있기 때문에, 그것을 이용해서 푸시면 됩니다. 정답자가 현재 90명정도로 적은 편의 문제입니다. 구현 자체가 어려워서라기보다는 문제 자체가 어려워서인 듯 합니다. N이 주어졌을 때, 루트는 최고층(가장 높은 레이어)에 위치하며 가장 먼 노드까지는 N-1번이면 도착하게 됩니다. 왼쪽 트리는 N-2에 대한 루트이고, 오른쪽 트리는 N-1에 대한 트리입니다. 이것을 이용하면 전체 트리에 대한 노드의 갯수 \(ft_N\)을 구할 수 있습니다. \[ ft_0 = 1, ~ ft_1 = 1 \] \[ ft_n = ft_{n-2} + ft_{n-1} + 1 \] 위의 점화식을 이용하면 우리는 손쉽게 노드의 갯수를 구할 수가 있습니다. 이제 이것을 .. 2022. 9. 18.
25. 프로젝트 오일러 #25 : 1000자리 피보나치 수열항 구하기 C/C++ 언어를 배우다보면, 꼭 한번은 프로그램해보는 것이 있다면, 피보나치 수열일거라 생각합니다. 피보나치 수열은 재귀함수를 사용한 곳에서도 많이 나오지만, 동적 프로그램이 필요한 예로도 자주 사용됩니다. 피보나치 수열은 한쌍의 토끼의 개체수 증가라는 퀴즈 형태에서 출발한 것인데요. 꼭 토끼가 아니라도 대장균의 증식같은 데에서도 응용할 수 있습니다. 기하함수로 증가하는 곡선을 보이게 됩니다. 피보나치는 아주 간단한 점화식을 이용합니다. 점화식을 보면 아주 간단한 형태입니다. 전항과 전전항을 더한 값이 현재항의 값이 됩니다. 그래서 첫번째 항과 두번째 항이 초기값으로 주어져야 합니다. 첫번째 항은 1, 두번째 항은 1입니다. 자연수 범위안에서 피보나치 수열은 진행합니다. 확장해서 음수항을 만들기도 하지.. 2015. 2. 17.
프로젝트 오일러 #2 피보나치 수열의 짝수항 합 C/C++ 언어를 배우다보면, 꼭 한번은 프로그램해보는 것이 있다면, 피보나치 수열일거라 생각합니다. 피보나치 수열은 재귀함수를 사용한 곳에서도 많이 나오지만, 동적 프로그램이 필요한 예로도 자주 사용됩니다. 피보나치 수열은 한쌍의 토끼의 개체수 증가라는 퀴즈 형태에서 출발한 것인데요. 꼭 토끼가 아니라도 대장균의 증식같은 데에서도 응용할 수 있습니다. 기하함수로 증가하는 곡선을 보이게 됩니다. 피보나치는 아주 간단한 점화식을 이용합니다. \[ F_{n} = F_{n-1} + F_{n-2} \] 점화식을 보면 아주 간단한 형태입니다. 전항과 전전항을 더한 값이 현재항의 값이 됩니다. 그래서 첫번째 항과 두번째 항이 초기값으로 주어져야 합니다. 첫번째 항은 1, 두번째 항은 1입니다. 자연수 범위안에서 피.. 2014. 12. 19.
728x90