mojo's Blog

문제 링크 => 1786번: 찾기 (acmicpc.net) 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net KMP 문제이다. KMP 란 Knuth Moriss Prett 의 약자로 긴 문자열 사이에 특정 문자열을 O(N+M) 만에 찾아내는 알고리즘이다. (긴 문자열 N, 특정 문자열 M) 접근하기에 앞서 Prefix, Suffix 에 대해 간단하게 알아보고 KMP 알고리즘 접근 방법에 대해 알아보도록 한다. 문자열 "abcde" 가 존재한다고 할 때 Prefix : a / ab / abc / abcd /..

를 priority_queue에 push 한다고 했을 때, pop을 10번 한 결과가 value 값이 가장 크도록 하면서 동일한 경우에 index 값이 작도록 하는 결과가 10개 저장하도록 하는 것을 구현해보겠습니다. 일단 value 값이 가장 크도록 하기 위해 최대 Heap 으로 구현했습니다. (Root의 index는 0으로 설정하였음) 최대 Heap 의 Push 하는 함수 int heapSize; int index[100000], Heap[100000], A[10], B[10]; void heap_Push(int i, int value) { Heap[i] = value; index[i] = i; // Heap 구현 int cur = i; while (cur != 0 && Heap[cur] > Heap..

문자열 공백 포함해서 받는 코드는 다음과 같다 string str; getline(cin, str); 위 방법을 이용해서 split 하도록 하는 코드는 다음과 같다 string str; getline(cin, str); istringstream ss(str); string stringBuffer; vector str_V; str_V.clear(); while (getline(ss, stringBuffer, ' ')) { str_V.push_back(stringBuffer); }

문제 링크 => https://www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 이항 계수 (N K) 를 구하는 문제이다. N, K 값의 범위가 최소 1에서부터 최대 4,000,000 으로 주어지며 테스트케이스는 최대 100,000까지 주어진다. 이항 계수 (N K) = N! / (N-K)!K! 에 대해서 Factorial를 구하는 방법을 생각해보면 O(N) 이 걸리는데 테스트케이스가 최대 100,000까지 주어졌으므로 O(NM), 즉, 시간초과가 난다. 따라서 F..

문제 링크 => https://www.acmicpc.net/problem/20412 20412번: 추첨상 사수 대작전! (Hard) 한 줄에 걸쳐 준표가 좋아하는 소수 m, 참가자들이 정한 Seed, 시연으로 공개된 X1, X2 이 주어진다. 항상 가능한 상황만 입력으로 주어진다. www.acmicpc.net 정수론 문제이다. 이 문제는 특별하게 m값이 소수로 주어지고 나머지 Seed, X1, X2 값은 0보다 크고 m 보다 작은 값으로 주어진다. 이때 a, c를 구하기 위해서 문제에서 주어진 식을 이용해서 a, c를 구해낼 수 있다. X1 = (a * Seed + c) (mod m) X2 = (a * X1 + c) (mod m) 위 식에서 아랫식을 윗 식을 빼주면 다음과 같은 결과를 얻는다. X2 - ..

문제 링크 => https://www.acmicpc.net/problem/14565 14565번: 역원(Inverse) 구하기 집합 Zn을 0부터 n-1까지의 정수 집합이라고 하자. Zn ∋ a, b, c 일 때, (a+b) mod n = 0이면 b는 a의 덧셈역이라고 하고 (a*c) mod n = 1이면 c는 a의 곱셈역이라고 한다. 정수 N, A가 주어졌을 때 Zn에서의 A의 www.acmicpc.net N과 A이 주어질 때, 덧셈에 대한 역원과 곱셈에 대한 역원을 구하는 문제이다. 덧셈의 역원 => A + x = 0 (mod N) 이므로 x = N - A 이다. 이때, 1 Ax = 1 (mod N) 인데 x를 구하는건 쉽지 않다. 따라서 Extended Euclidean Algorithm 을 이용해..