https://www.acmicpc.net/problem/8595 8595번: 히든 넘버 첫째 줄에 단어의 길이 n (1 ≤ n ≤ 5,000,000)이 주어진다. 둘째 줄에는 단어가 주어진다. 단어는 알파벳 대/소문자와 숫자(0-9)로 이루어져 있다. www.acmicpc.net 문자열속에서 숫자만 걸러내어 총합을 출력하는 문제. 그냥 아무생각없이 풀었다가 자꾸 틀렸다고 나와서 당황했다. 틀린 이유는 숫자의 범위인데, 정말 극단적인 상황을 예시로 들어보면, 999999a999999a9999......가 계속되어 제한길이인 5백만자가 들어온다고 가정하자. 이떄 99999는 약 71만번 등장하게 되는데, 999999 * 71만 = 약 7.1천억이므로, int형 범위를 넘어선다. 따라서 int형이 아닌 lo..
https://www.acmicpc.net/problem/9093 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net 문장을 입력받고, 각 단어를 뒤집어 출력하는 문제. 문자를 입력받은 후에 공백을 기준으로 파싱하고 뒤집어 출력한다. #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; string str; string token;..
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로 풀어보았다. 그중에서도 메모이제이션을 통해 접근해보았다. 메모이제이션이란 컴퓨터프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그..
