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..
https://programmers.co.kr/learn/courses/30/lessons/12901?language=cpp 코딩테스트 연습 - 2016년 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까 programmers.co.kr 주어진 날찌의 요일을 반환하는 문제. 일, 월, 화 ....., 토요일과 월별로 최대 일수를 배열에 저장한 후에, 1월 1일로부터 며칠이 지났는지 변환하여 월, 일을 일수로 바꾼 후에, 7로 나눈 나머지가 요일이 되므로 이를 출력한다. 이때 1월 1일이 금요일인걸 고려해야한다. #include usi..
https://programmers.co.kr/learn/courses/30/lessons/42748?language=cpp 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 전체 배열을 주어주고, 구간을 잘라 정렬하고, 거기서 k번째 수를 찾는 문제. 구간을 복사하여, 주어진대로 한다. #include #include using namespace std; vector solution(vector array, vector commands) { vector answer; vector::iterator commandIter = commands.begin(); vector copyA..
