https://www.acmicpc.net/problem/1201 1201번: NMK 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net 1부터 N까지 수에 대해 가장 긴 증가하는 부분 수열 길이가 M, 가장 긴 감소하는 부분 수열 길이가 K가 되도록 수열을 만드는 문제입니다. M*K 만큼 0으로 초기화된 배열에 K 간격으로 1부터 M까지 수를 넣고, 역순으로 나머지 수 중 큰 수를 차례로 넣게 되면 M, K 조건을 모두 만족하게 됩니다. 예를 들어, 10, 5, 4와 같은 경우 0 0 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 로 이루어진 배열이 있고 0 0 0 1 0 0 0 2 0 0 0 3 0 0 0 4 10 9 8 5 0 0 0 1 0 0 0 2 0 0..
https://www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 오일러 파이 함수를 구하는 문제입니다. 오일러 파이 함수는 phi(n) = n * (1-1/p1) * ... * (1-1/pk) 입니다. (p1, p2, ..., pk : n의 소인수) 이를 이용해 n에 대한 소인수만 먼저 구한 뒤 공식을 그대로 적용하면 됩니다. 코드는 아래와 같습니다. #include #include #include using namespace std; long long n; vector factors; // 오일러 파이 함..
https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 가장 긴 증가하는 부분 수열을 DP가 아닌 이분탐색을 활용한 방법입니다. LIS[i] = 길이 i+1 인 증가하는 부분 수열들 중 가장 큰 값 중 가장 작은 값 이라고 하면, LIS[i] < LIS[i+1] 은 자명합니다. (가장 작은 값만 저장하게 되므로, LIS의 길이가 i+1로 증가했다는 것은 LIS[i] 보다 큰 값이 존재한다는 뜻) 따라서 LIS 는 오름차순..
백준 2086 피보나치 수의 합 C++
https://www.acmicpc.net/problem/2086 2086번: 피보나치 수의 합 제 1항과 제 2항을 1이라 하고, 제 3항부터는 앞의 두 항의 합을 취하는 수열을 피보나치(fibonacci) 수열이라고 한다. 예를 들어 제 3항은 2이며, 제 4항은 3이다. 피보나치 수열의 a번째 항부터 b번째 www.acmicpc.net a번째부터 b번째까지 피보나치 수열의 합을 구하는 문제입니다. 피보나치 수열의 합은 생각해본 적이 없었는데 식은 간단했습니다. F(1)=1, F(2)=1 인 피보나치 수열의 합은 다음과 같습니다. S(n) = F(1) + ... + F(n) = F(n+2) - 1 그리고 피보나치 수열은 아래와 같이 행렬로 표현이 가능합니다. 그러므로 거듭제곱 연산 시 900.... ..
https://www.acmicpc.net/problem/10220 10220번: Self Representing Seq 두 번째 예제의 경우 가능한 A는 (2,1,2,0,0) 한 개만 존재한다. 세 번째 예제의 경우 가능한 A는 (2,0,2,0), (1,2,1,0) 두 개 존재한다. www.acmicpc.net 처음에 문제가 무슨 말인가 싶었던 문제였습니다. 아무래도 플레 문제이다 보니 좀 어려운가 싶었는데 채점현황을 보니 다들 코드가 짧았습니다. 그 말은 뭔가 숨은 규칙이 있다는 뜻인거 같습니다. 1개씩 해보면, n=1 => 0 n=2 => 0 n=3 => 0 n=4 => 2 n=5 => 1 n=6 => 0 인 것은 쉽게 찾을 수 있고, n=7 => (3,2,1,1,0,0,0) 케이스 밖에 없고 n=..