전체 글 (104) 썸네일형 리스트형 5525 IOIOI www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 처음엔 그냥 naive하게 매번 부분 문자열을 만들어서 비교했더니 역시 시간초과.. O(n^2) 그래서 처음에 'I'를 찾은 다음, 2칸씩 보고 "OI"를 세면서 문자열 P를 찾는다. 이때 본 2칸은 다시보지 않는다. "OI"를 n개 찾으면 결과값 +1, 그리고 찾은 "OI"개수를 1개 빼고 다시 2칸씩 보면서 찾는다. 이런식으로 해결하면 O(n) 으로 해결할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1.. 1992 쿼드트리 www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 알고리즘 문제해결전략 책에 소개된 알고스팟 문제와 유사한 문제이다. damper.tistory.com/4 [ALGOSPOT] QUADTREE 출처 : algospot.com/judge/problem/read/QUADTREE 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분.. damper.ti.. 1718 암호 www.acmicpc.net/problem/1718 1718번: 암호 Vigenere cipher이라는 암호화 방법은 암호화하려는 문장 (평문)의 단어와 암호화 키를 숫자로 바꾼 다음, 평문의 단어에 해당하는 숫자에 암호 키에 해당하는 숫자를 더하는 방식이다. 이 방법을 변 www.acmicpc.net 문제에서 원하는 그대로 했다. 평문에다가 키의 알파벳 순서를 빼고 만약 'a' 밑으로 가면 알파벳 개수인 26을 더해줍니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; #define swap(a,b) (a)^=(b)^=(a)^=(b) #define endl '\n' typedef lo.. 7662 이중 우선순위 큐 www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 처음에 이 문제를 접했을 때에는 문제이름이 이중 우선순위 큐여서 우선순위가 다른 priority_queue를 2개 선언해서 두개로 돌렸는데 다시 생각해보니 말도 안되는 방법이었다... 그래서 map을 사용해서 value 값을 counting 용도로 쓰면서 naive하게 진행. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28.. [ALGOSPOT] FENCE algospot.com/judge/problem/read/FENCE algospot.com :: FENCE 울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체 algospot.com 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, .. 카라추바 곱셈 알고리즘 알고리즘 문제해결전략 183p에 소개된 카라추바 곰셈 알고리즘입니다. 2N자리수인 a와 b를 다음과 같이 정의한다고 하자. $$a = a_{1} \times 10^{N}+a_{0}$$ $$ b = b_{1} \times 10^{N}+b_{0}$$ a x b 는 다음과 같이 표현할 수 있다. $$a \times b \\ = ( a_{1}\times 10^{N} +a_{0}) \times (b_{1} \times 10^{N} + b_{0}) \\ = a_{1} \times b_{1} \times 10^{2N} + (a_{1} \times b_{0} + a_{0} \times b_{1})\times10^{N}+a_{0}\times b_{0}$$ 그렇다면 계산을 위해 다음과 같이 곱셈을 기준으로 4가지 조각으로.. 1541 잃어버린 괄호 www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 가장 처음과 마지막은 숫자이고, 두 개 이상의 연산자는 나타나지 않는다. 그럼 숫자가 N개라면 연산자는 N-1개이다. 숫자는 vector에, 연산자는 queue에 저장하고 숫자를 한칸씩 가면서 계산한다. 최솟값을 만들기 위해 '-'연산자 뒤에 나오는 '+'연산자에 해당하는 숫자들을 모두 더하여 한번에 뺀다. 경우의 수는 다음과 같다. - queue에서 '-'가 나온 경우, 빼기 위해 저장되어있는 값을 결과.. 11687 팩토리얼 0의 개수 www.acmicpc.net/problem/11687 11687번: 팩토리얼 0의 개수 첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다. www.acmicpc.net N!에서 가장 끝 0의 개수를 세려면 2 * 5의 수를 세면 된다. N!을 소인수분해 했을 때, 2의 개수와 5의 개수를 생각한다면 min(2의 개수, 5의 개수) 가 M인 N! 중 N의 최소값을 찾으면 된다. 2의 개수는 N이 짝수일 때마다 1개 이상 생기고, 5의 개수는 N이 5의 배수일 때마다 1개 이상 생기므로 2의 개수는 항상 5의 개수보다 크거나 같다. 그러므로 5의 개수만 신경쓰자. 그러면 N!에서 5의 개수는 몇개일까? 5의 배수의 개수 + 25의 배수의 개수 + 125의 배수의 개수 + 625의 배수의 개수... 이전 1 ··· 8 9 10 11 12 13 다음
