피보나치
-
백준 2302번 극장 좌석 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 2. 25. 22:59
이번 글은 백준 알고리즘 2302번 "극장 좌석" 문제를 다뤄본다.이 문제의 키워드는 동적계획법(DP), 피보나치, 곱의 법칙이다.문제를 보자. 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 써 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다. 그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉..
-
백준 1003번 피보나치 함수 :: 마이구미알고리즘 풀이/수학 2016. 6. 15. 22:07
이번 글은 백준 알고리즘 문제 1003번 "피보나치 함수"에 대해 다뤄본다.피보나치 수는 너무도 대중적이기에 많이 들어보았으리라 생각한다.' 0 1 1 2 3 5 8 13 21 34 55.......' 일단 문제를 보자. n번째 피보나치 수를 구하는 과정에서 재귀를 통해 돌아갈 때 n이 0일 때와 1일 때의 경우가 얼마나 되는지 카운트를 구하는 문제이다. 먼저 순수한 방법으로 풀어보자.위 그림에 있는 소스를 활용해서 0일때 1일때 카운트 변수 만들어서 if문 들어가면 ++해주면 된다. 이렇게 하더라도 사실상 원하는 결과값이 나온다.알고리즘 문제에는 시간 제한이 있다.그 말은 막 짜면 안되고, 문제가 원하는 로직은 꼭 존재한다.그걸 캐치하여 최소한의 시간으로 돌아가도록 소스를 짜야한다. (속도를 고려하는 ..