mojo's Blog

문제 링크 => 4779번: 칸토어 집합 (acmicpc.net) 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 분할정복 문제이다. 가운데 부분을 3^(N-1) 만큼 빈칸을 출력하게 하고 양 옆을 f(n-1) 을 재귀적으로 호출하도록 하면 정답이다. 풀이 code #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #define INF 1000..

문제 링크 => 10090번: Counting Inversions (acmicpc.net) 10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net A permutation of integers from 1 to n is a sequ..

문제 링크 => 11440번: 피보나치 수의 제곱의 합 (acmicpc.net) 11440번: 피보나치 수의 제곱의 합 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 수학 + 분할 정복을 이용한 거듭제곱의 문제이다. 이문제는 2086번: 피보나치 수의 합 (acmicpc.net) 이걸 해결한다면 굉장히 쉬운 문제이다. 생각보다 이문제는 규칙성이 너무 쉽게 발견되서 금방 해결한 문제이기도 하다. 다음과 같이 규칙성을 찾아보도록 한다. (이때 Fibo(1)^2 = 1, Fibo(2)^2 = 1, Fibo(3)^2 = 4, Fibo(4)^2 = 9, Fibo(5)^2 = 25, Fibo(6)^2 = 64, Fibo(7)^..

문제 링크 => 2086번: 피보나치 수의 합 (acmicpc.net) 2086번: 피보나치 수의 합 첫째 줄에 a와 b(1≤a≤b≤9,000,000,000,000,000,000)이 주어진다. www.acmicpc.net 수학 + 분할 정복을 이용한 거듭제곱 문제이다. a, b값이 10^18 이라는 점을 고려했을때 logN 을 이용해야 한다는 것을 파악할 수 있다. 그래서 Fibo(n) 값을 어떻게 표현해야 효율적인지에 대해서 노가다를 좀 하더니 이러한 결과가 나왔다. Fibo(1) = 1 Fibo(2) = 1 Fibo(3) = 1^2 + 1^2 = 2 ( Fibo(1)^2 + Fibo(2)^2 ) Fibo(4) = 2^2 - 1^2 = 3 ( Fibo(3)^2 - Fibo(1)^2 ) Fibo(5) =..

문제 링크 => 5525번: IOIOI (acmicpc.net) 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 문자열 관련 문제이다. 이문제의 핵심은 시간복잡도 O(N) 으로 해결하도록 하는것이다. 문자열의 index = 0 부터 접근한다고 할 때, 'I' 를 발견하는 경우에 대해 살펴보도록 한다. (이때, 'O', 'I' 가 iterate 하는 것을 판별하기 위한 변수 j 와 IOI, IOIOI, IOIOIOI, ... 를 판별하기 위한 ..

문제 링크 => 7662번: 이중 우선순위 큐 (acmicpc.net) 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 이 문제는 multiset을 이용해서 푸는 문제이다. multiset은 원소들의 중복을 허용하며 정렬, 삭제, 삽입 등 이러한 operation을 O(logN) 만큼 빠르게 진행 해준다는 점에서 유용하다. ( 원소들이 Tree 구조로 되어있어서 시간복잡도가 logN 임을 알 수 있다 ) 이 문제를 통해 multiset 에 대한 사용법을 익히면 좋을듯 하다. 풀이 Code => #defin..