https://www.acmicpc.net/problem/9417 9417번: 최대 GCD 첫째 줄에 테스트 케이스의 개수 N (1 < N < 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 양의 정수 M (1 < M < 100)개가 주어진다. 모든 수는 -231보다 크거나 같고, 231 -1보다 작거나 www.acmicpc.net n개의 자연수를 입력받고, 두 수의 쌍중에서, 가장 큰 최대공약수를 출력하는 문제. 문자열로 받은 후에, 공백을 기준으로 문자열을 분리한 후에, 브루트포스로 가장 큰 최대공약수를 찾는다. #include #include #include #include using namespace std; int gcd (int a, int b) { return !b ? a..
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 =..
1학년 2학기, 텀프로젝트도 끝나가고 기말고사도 끝나갈 무렵,백준과 프로그래머스만 풀고 있다가 1학년을 대상으로 하는(21학번) 파이썬 공모전을 연다는 안내를 받고 참여했다. 파이썬 기능을 많이 한정한데다가, 수업과 교재에서 알려주는 테크닉만으로 만들어야 하기 때문에, 이걸로 뭘 만들까 고민하다가 아무래도 처음 쓴 turtle보다는 몇번 써보고 했던 tkinter로 만들기로 했다. 모듈은 정했고, 이제 주제를 정해야 했는데, 사실 주제 정하는데 시간을 정말 많이 쓴 것 같다. 주변에서도 아이디어를 계속 받으면서, 결국 2048! 게임을 만들어 보기로 했다. 이 게임은 고등학교때 핸드폰 바뀌고(왜 남아있는지는 모르지만 갤럭시 S1) 그나마 멀쩡하게 돌아가는 게임이었다. 고등학생때, 통학하면서 버스에서 음악..
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)이다. 이때 나누는 ..
