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=..
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 오랜만에 문제를 풀어보았습니다. (사실 그 전에 푼 거 틀린 거 다시 풀기....) 주어진 그래프에서 경로의 최소 값 중 최대값을 구하면 됩니다. 여러 방법이 있지만 가장 쉽게 떠오르는 다익스트라를 이용해서 풀었습니다. 다익스트라가 경로를 탐색하면서 기존 결과보다 좋으면 업데이트를 반복하는 것이므로, 일반적인 다익스트라처럼 합을 계산하는 ..
https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 그냥 간단한 외판원 문제입니다. 외판원 문제가 오랜만에 보여서 풀어보았는데 틀렸다고 해서 다른 외판원 문제 풀었던 코드로 넣으니 정답이 나왔습니다. (왜지???? 전혀 다른 점이 없었는데??? 눈을 잘 비벼보자.....) 특별한 조건은 없고, weight 가 항상 양수인 조건만 있습니다. 외판원이 노드를 방문하는 과정에서 dp[i][j] = i 번 노드..