commit;

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 2020/07/11 - [Unity & C#] - 2748번: 피보나치 수 2 - 동적계획법 2748번과 비슷한 피보나치 문제고, 동적계획법으로 분류되어 있다. 아래와 같은 기본적인 피보나치 함수로 피보나치 수를 구할 때, 호출되는 Fibonacci(0)과 Fibonacci(1)의 횟수를 구해야 한다. def Fibonacci(n): if n == 0: print ("0") return 0 elif n == 1: print ("1") return 1 else: return Fibonacci(n..

https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)�� www.acmicpc.net 동적계획법(Dynamic Programmin)이란 복잡한 문제를 작은 단위로 분할하여 풀고 최종적으로 그것을 결합해 해겨하는 방법을 말한다. 동적계획법의 핵심은 메모이제이션(Memoization)이다. 동일한 계산이 중복되는 문제에서 한 번 계산한 결과는 저장해 둔다. 그리고 다음 번 동일한 계산이 필요할 때 연산하지 않고, 저장해둔 이전 결과에 접근해 사..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이번엔 Hash Table을 이용해 간단히 풀어보자. Hash Table은 Key에 Value가 저장되는 자료형이다. Python에선 Dictionary가 해당된다. # NumberCard2.py - HashTable def HashTable(): cardsDic = {} for i in cards:# Dictionary에 Key를 카드 번호, Value를 카드 ..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 분류는 일단 이분탐색으로 되어있지만 Hash Table 구조(Key, Value Pair)를 사용하여 해결할 수도 있다. 이분탐색(또는 이진탐색, Binary Search)은 오름차순으로 정렬되어 있는 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 정렬된 리스트에만 사용할 수 있지만, 매번 검색 범위가 반으로 줄기 때문에 O(logN)의 시간복잡도를 갖는..