https://www.acmicpc.net/problem/9471 9471번: 피사노 주기 첫째 줄에 테스트 케이스의 개수 P가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. www.acmicpc.net 피보나치 수열을 자연수 K로 나눈 나머지를 수열로 볼 때, 이 수열에 주기성이 생긴다, 이때의 주기를 피사노 주기라고 한다. 편의를 위해 피보나치 수열을 K로 나눈 나머지로 이루어진 수열을 피사노 수열이라고 하겠다. 이 문제는 규칙성을 찾아야 한다. 피사노 주기의 성질을 다 무시하고 K를 2, 3, 4, 5, .......로 늘려가면서 피사노 수열을 써보면 규칙이 보이게 되는데, 피사노 수열의 N번째 항이 0이고 N+1번째 항이 ..
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 저번에는 피보나치 수열의 일반항으로 풀어보았다. (https://codejin.tistory.com/116) 이번에는 다른 방법으로 풀어보자. 이번에는 dp로 풀어보았다. 그중에서도 메모이제이션을 통해 접근해보았다. 메모이제이션이란 컴퓨터프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그..
https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수열 기본문제. 숫자가 크지는 않지만, 45에 근접할수록 시간이 꽤 걸리기 때문에 다른 방식으로 풀어보자. 이번 문제는 피보나치 수열의 일반항으로 접근해보았다. 피보나치 수열의 일반항은 다음과 같다. #include #include #define ULL unsigned long long #define A (1 + sqrt(5)) / 2 #define B (..
https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 시간제한이 0.25초이므로 일반적인 재귀나 반복으로 접근하면 틀리는 문제. dp로 접근해야한다. n번째의 피보나치 수열을 fib(n)이라고 하자. 그렇다면 fib(0)의 경우는 0을 한번 호출하므로 1 0이 될 것이다. fib(1)은 1을 한번 호출하므로 0 1이 될 것이다. 이 둘을 기본 틀로 잡자. fib(2)는 1과 0을 호출하므로 1 1이 되고, 이것은 fib(1)과 fib(0)이 호출한 횟수의 총합과 같다. fib(3)은 fib(2)와 fib(1)을 호출하고 fib(2)는 다시 fib..
https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 단순히 계속 곱했다가는 오버플로우되는 문제. 하지만 모듈러 연산을 적용한다고 해도, 일반적인 반복문으로 접근한다면 시간제한에 걸린다 O(n)이니까. 결국 이 문제의 핵심은 숫자가 오버플로우되지 않도록 모듈러연산을 계속해서 적용한다. O(n)으로 접근해서는 안된다. 모듈러 연산은 https://codejin.tistory.com/68를 참조하자. 이를 통해 다 곱하고 나누는 것이 아니라, 나머지를 계속 곱하면서 최종적인 값을 찾아야 한다. 그러면 오버플로우는 해결..
https://programmers.co.kr/learn/courses/30/lessons/12932?language=cpp 코딩테스트 연습 - 자연수 뒤집어 배열로 만들기 자연수 n을 뒤집어 각 자리 숫자를 원소로 가지는 배열 형태로 리턴해주세요. 예를들어 n이 12345이면 [5,4,3,2,1]을 리턴합니다. 제한 조건 n은 10,000,000,000이하인 자연수입니다. 입출력 예 n return 12345 programmers.co.kr 자연수를 뒤집은 배열을 반환하는 문제. 10으로 나눈 나머지를 순차적으로 배열에 넣는다. #include using namespace std; vector solution(long long n) { vector answer; while (n) { answer.pus..
https://programmers.co.kr/learn/courses/30/lessons/76501?language=cpp 코딩테스트 연습 - 음양 더하기 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 re programmers.co.kr 정수의 절댓값과 부호가 따로 주어지는 문제. signs에 따라 뺄지 더할지 결정한다. #include using namespace std; int solution(vector absolutes, vector signs) { int answer = 0; for (int i = 0; i < absolutes.size()..
https://programmers.co.kr/learn/courses/30/lessons/12947 코딩테스트 연습 - 하샤드 수 양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다. 자연수 x를 입력받아 x가 하 programmers.co.kr 자기 자신의 자릿수의 총합이 자기 자신을 나누어 떨어지게 하는 숫자를 하샤드 수라고 한다. 숫자를 자릿수로 분리하여 합하고 나누어 떨어지는지 반환한다. #include #include using namespace std; bool solution(int x) { int copy = x; vector v; while(copy) { v.p..
