Platinum18 BOJ 5719 : 거의 최단 경로 문제 링크 : https://www.acmicpc.net/problem/5719 이 문제는 BOJ 1948 임계경로와 매우 유사한 문제다. 임계경로는 그래프가 DAG 이고, 최장거리를 구하는 문제여서 위상정렬 DP 로 해결하지만, 이 문제는 그래프가 일반적인 방향그래프이며, 최단거리를 구하는 문제이기에 Dijkstra 가 필요하다. 우선 최단거리에 포함되는 간선을 모두 구해야하기에, Dijkstra 역추적이 필요하다. 나는 원래 임계경로 문제를 풀 때 역추적을 비효율적으로 했었다. N개의 노드마다, 자신을 갱신시킨 노드들의 목록을 vector 로 관리했었는데, 그럴 필요가 없었다. Dijkstra 를 다 돌리고 난 후 dist 값을 비교하면 직전 노드를 직접 저장할 필요가 없다. 예를 들어, 2 -> 5.. 2022. 8. 26. BOJ 1733 : 등번호 문제 링크 : https://www.acmicpc.net/problem/1733 N명의 사람이 앞 뒤에 숫자가 적힌 유니폼을 갖고 있다. 각자 앞 또는 뒤에 적힌 숫자를 골라 N명의 사람이 고른 숫자가 겹치지 않게 하는 해를 출력하면 되는 문제다. 처음에 문제를 보자마자 든 생각은 이게 왜 플레1 이나 하지? 였다. 그냥 이분매칭인데, 단순한 이분매칭은 플레4~5 이기 때문이다. 하지만 N 제한이 100만인 것을 알고 납득했다. 혹시 새로운 이분매칭 알고리즘을 배워야만 하나? 하고 검색하니 Hopcroft - Karp 가 있긴 했다. 그래도 O(N 루트 N) 이라 시간초과 뜰 것 같아 다른 해법을 고민하기 시작했다. 약간의 관찰을 통해 그래프 탐색 느낌이 난다는 것을 알게 되었다. 예를 들어 1번 학생이.. 2022. 8. 16. BOJ 24970 : 균형 수 문제 링크 : https://www.acmicpc.net/problem/24970 "균형 수"란, (앞쪽 절반의 각 자리 수 합) = (뒤쪽 절반의 각 자리 수 합) 이 되는 수를 말한다. 예를 들어 13504, 2415 가 균형수라고 할 수 있다. T(n) := n 자리의 균형수들의 총 합일때, T(1) + T(2) + ... + T(N) 을 315 으로 나눈 나머지를 구하면 된다. (N은 100 이하) 내가 좋아하는 유형의 DP 문제인데, 처음 생각한 것은 d[i][j], s[i][j] 두 개를 정의하는 것이었다. d[i][j] = 맨 앞에 0이 와도 되며, 각 자리 수의 합이 j 가 되는 i 자리 수의 개수 s[i][j] = 맨 앞에 0이 와도 되며, 각 자리 수의 합이 j 가 되는 i 자리 수의 .. 2022. 8. 15. 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. 이전 1 2 3 다음
