BOJ27 BOJ 3265 : 수열로 수열 구하기 문제 링크 : https://www.acmicpc.net/problem/3265 생각의 흐름이 정해로 가는 것이 체감이 되어 재밌었던 문제. 처음에 생각했던 아이디어는 B 수열의 인접한 두 수의 관계에 주목하고 이분매칭을 하는 거였다. 하지만 간선이 너무 많았고 정점도 10만개라 1초에 나올 수 없었다. 그러다 계속 생각을 해봤는데, 결국 1을 어떻게 활용하느냐가 관건 같았다. 위 그림처럼 B[i] = 1, B[j] = 1 이고 그 사이는 전부 0 인 상황을 보자. i + 1 ~ j 까지의 숫자들은 결국 A[i+1] ~ A[j] 범위에 갇히게 된다. 갇힌 다음에, A[i+1] ~ A[j] 에는 j 부터 (i+1) 까지 숫자들을 내림차순으로 박아주면 된다. 그러면 절대 B[i+1 ~ j-1] 범위에서 1 .. 2022. 8. 15. BOJ 6991 : 계통 트리 문제 링크 : https://www.acmicpc.net/problem/6991 그래프 이론 문제 중에서 꽤 잘 만들었다고 생각하는 문제. 트리가 주어졌을 때, 거리가 3 이내인 두 노드는 "계통 그래프" 에서 연결된다. 문제는 "계통 그래프" 가 주어졌을 때, 이 "계통 그래프"가 나오는 원래의 트리를 찾는 것이다. 핵심은 트리의 형제 노드들(sibling nodes)이다. 같은 부모를 공유하는 형제 노드는 그들끼리 완전 그래프를 이룬다. 형제들 중 어떤 두 노드를 잡아도 계통 그래프에서 연결된다는 것이다. 조금만 더 생각해보면, "자기 자신도 포함하는" 인접리스트를 구성했을 때 형제 노드들은 그 구성이 완전히 일치한다. 따라서, 우리는 인접리스트를 구성한 후 그 연결상태가 완전히 동일한 노드들끼리 묶.. 2022. 8. 14. BOJ 2855 : 흥미로운 수열 문제 링크 : https://www.acmicpc.net/problem/2855 흥미로운 수열은 길이가 항상 2K 꼴의 짝수다. 앞 K 개와 뒷 K 개 수의 합이 둘 다 S 이하면 흥미로운 수열이다. 길이 N짜리 수열과 S가 주어졌을 때, 연속부분수열 중 가장 긴 흥미로운 수열의 길이를 출력하면 된다. 딱 봐도 이진탐색인데, 정당성이 없었다. A[1] ~ A[K] // A[K+1] ~ A[2K] 가 흥미로운 수열이 아니었다고 해도 A[1] ~ A[K+1] // A[K+2] ~ A[2K+2] 가 흥미로운 수열이 될 수 있기 때문이다. (A[K+1] 이 엄청 큰 수고 A[2K+1] + A[2K+2] 가 엄청 작으면 가능하다) 그러다 문득 가운데를 고정해놓으면 이진탐색의 정당성이 부여된다는 것을 깨달았다. A.. 2022. 8. 14. BOJ 2787 : 흔한 수열 문제 문제 링크 : https://www.acmicpc.net/problem/2787 1 x y v - x번째 수부터, y번째 수 중 제일 큰 값은 v 2 x y v - x번째 수부터, y번째 수 중 제일 작은 값은 v 이런 식으로 수열에 관한 정보를 주면 이들을 만족하는 수열을 찾아서 출력하면 된다. 수열의 정보에 관한 문제가 대부분 펜윅트리로 풀려서 그쪽으로 생각을 해봤는데 잘 안 됐다. 그러다가 N 제한이 200 인 것이 이상해서 생각해봤는데 이분매칭이 떠올랐다. 2 ~ 10 번째 수의 최댓값이 15 라면, 2 ~ 10 번째의 각 칸들을 1 ~ 15 와 연결해주고 매칭하면 된다. 하지만, 이 방법은 문제가 있다. 매칭은 정상적으로 되지만, 2 ~ 10 번째 수의 최댓값이 15 면 15가 무조건 존재한다는.. 2022. 8. 14. BOJ 7765 : Supersquare 문제 링크 : http://acmicpc.net/problem/7765 500이하의 자연수 N을 입력받으면, 2N 자리 제곱수를 출력하면 된다. 단, 앞 N자리와 뒤 N자리 또한 제곱수여야 한다. 지금 내가 서술하는 풀이가 정해라면 그리 좋은 문제 같진 않다... Naive 하게 코드를 돌려보면서 규칙을 찾아봤는데 꽤 오래걸렸다. 규칙 찾고 정리하는데 3일 정도 걸렸다. 3일 내내 잡고 있었던 건 아니지만 꽤 어려웠던 건 확실. N이 짝수일 때 (N = 2n + 2 형태) ( 5 * 10(2n+1) - 10(n+1) + 1 )2 를 전개하면 앞 (2n+2) 자리는 (5 * 10n - 1)2 이고 뒤 (2n+2) 자리는 (10(n+1) - 1)2 이다. 이걸 한번에 발견한 것은 아니고 물론 Naive 하게.. 2022. 8. 14. BOJ 24545 : Y 문제 링크 : https://www.acmicpc.net/problem/24545 전형적인 Tree DP 문제이다. 나는 D1, D2, D 세 가지 다이나믹 배열을 정의하여 해결했다. D1[i] := i 번 노드가 꼭대기인 단일 체인의 최대 길이 D2[i] := i 번 노드가 꼭대기인 Y 트리의 최대 크기 ( V 모양도 포함 ) D[i] := i 번 노드가 루트인 서브트리에서의 Y 트리의 최대 크기 이제 DP 식만 잘 세워주면 된다. D1[i] 는 ( 자식들의 D1 들 중 max 값 ) + 1 이다. D2[i] 는 ( 자식들의 D2 들 중 max 값) + 1 과, ( 자식들의 D1 들 중 큰 것 2개의 합 ) + 1 중 큰 값이다. 그럼 D[i]는 어떻게 하면 될까? 1. 서로 다른 두 자식들의 D1 +.. 2022. 8. 14. 이전 1 2 3 4 5 다음
