https://www.acmicpc.net/problem/12605 12605번: 단어순서 뒤집기 스페이스로 띄어쓰기 된 단어들의 리스트가 주어질때, 단어들을 반대 순서로 뒤집어라. 각 라인은 w개의 영단어로 이루어져 있으며, 총 L개의 알파벳을 가진다. 각 행은 알파벳과 스페이스로만 www.acmicpc.net 문장을 입력받고, 단어 단위로 뒤집어서 출력하는 문제. 문장 전체를 입력받고, 공백을 기준으로 파싱하여 스택에 push하고 push가 끝난 후에, pop하면서 출력한다. C++에서 문자열을 파싱하는 방법을 몰랐는데, stringstream기능을 이용하여 할 수 있다는 것을 배웠다. (https://rank-brothers.com/831/cpp-string-tokenizing/) #include ..
https://www.acmicpc.net/problem/5637 5637번: 가장 긴 단어 단어는 알파벳(a-z, A-Z)과 하이픈(-)으로만 이루어져 있다. 단어와 다른 문자(마침표, 숫자, 심볼, 등등등...)로 이루어진 글이 주어졌을 때, 가장 긴 단어를 구하는 프로그램을 작성하시오. Apple의 www.acmicpc.net 입력받은 단어들 중에 제일 긴 단어를 출력하는 문제. 이때 단어는 알파벳과 하이픈만으로 구분하기 때문에 이에 유의해야한다. 공백을 기준으로 입력받고, 알파벳과 하이픈을 제거한 후에, 길이를 비교하여 풀었다. #include #include #include using namespace std; string preprocess(string str) { string result =..
https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 저번에는 n이 무지막지하게 컸지만, 이번에는 결과값을 그냥 출력해야 하는 문제. 무슨 말이냐 하면, 저번 2749번 문제는 값이 아무리 커도 결국 나머지값이 필요했기 때문에 출력하는데 별 문제가 없었지만, 이번에는 피보나치 수열 값을 출력해야 한다. 그런데 피보나치 수열은 값이 기하급수적으로 커진다. 당장 300정도만 해도 음..... 그만 알아보도록 하자...
https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net n이 정말 살벌한 문제. 그렇다고 n의 최댓값만큼 배열을 저장했다가는 램이 터질 문제. 이 문제를 어떻게 접근해야하나 싶어서 처음에는 일반항으로 접근해서 모듈러연산을 수행하려고 했지만, 나누려는 대상이 정수가 아니라서 실패했다. 그래서 어떻게 할까 하다가, 저번에 풀었던 피사노 주기 문제가 생각났다. (https://codejin.tistory.com/118) 피사노 주기의 성질에서 m = 10^n (n>2)일때 피사노 주기K(m)은 15 * 10^(n-1)이다. 이때 나누는 ..
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..
