전체 글

문제 링크 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 어제 풀어봤던 11053번: 가장 긴 증가하는 부분 수열 문제에 이어서 2번째 문제입니다. 이전 문제는 \(O(N^2)\) 의 시간복잡도로 풀 수 있었지만, 이번 문제부터는 \(O(N \log N)\) 의 시간복잡도로 해결해야합니다! 차근차근 해결방법을 설명하며 풀이해보겠습니다. 풀이 LIS문제를 DP+이분탐색으로 풀이하면 됩니다. 이 문제에서는 이전 문제와는 다르게, N의 범위가 100만까지로 무지막지하게 큽니다. N의 크기가 크기 때문에, \(O(N..

문제 링크 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 오랜만에 DP 문제를 들고 왔습니다! 이 문제는 그 이름도 유명한 가장 긴(최장) 증가 부분 수열 (LIS: Longest Increasing Subsequence) 입니다. 이 문제는 시리즈(1번부터 5번)가 있으며, 나무위키에 등재되어 있을 정도로 잘 알려져 있습니다. 문제를 차근차근 살펴보며 풀이해봅시다! 풀이 DP를 이중선형시간(\(O(N^2)\))으로 메모라이즈하며 ..

문제 링크 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 예전에 분리집합(union-find)을 배우고 나서, 분리집합을 응용한 알고리즘인 최소 스패닝 트리를 공부해야지~ 하고 생각했다가 미루고 미뤄서(...) 최근에 공부하게 됐습니다. 기본적인 최소 스패닝 트리 문제를 한번 풀어보겠습니다. 풀이 최소 스패닝 트리(분리 집합) 알고리즘 으로 푸는 문제입니다. 문제가 복잡해 보이지만, 간단한 해결방법이 존재합니다. 문제에서는 다음과 같은 조건을 제시했습니다. 마을의 이장은..

문제 링크 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 요즘 위상정렬에 관한 문제들을 풀고 있는데, 간단한 문제 하나를 소개해드리려고 합니다. 풀이 위상정렬 + 우선순위큐(최소힙)로 풀이하면 됩니다. 일반적인 위상정렬(`indegree` 배열 활용)을 만듭니다. 보통 위상정렬은 `queue` 를 사용하지만, 이 문제에서는 최소 힙 우선순위큐를 사용합니다. 문제에서 주어진대로, "가능하면 쉬운 문제(1번부터)"와 "먼저 푸는 것이 좋은 문제"를 풀어야하기 때문에 최소 힙을 사용..

문제 링크 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net BFS 응용 문제 중 하나입니다. 처음에 '상범이가 어떻게 이동하지?' 라는 생각으로 시간이 좀 걸렸습니다. 백트래킹, 최단거리 등을 생각하면서 고민했는데, 결국엔 BFS로 다 해결할 수 있었습니다. 풀이 불과 상범이의 queue를 각각 만들어서 서로의 거리를 비교하면 됩니다. 불의 Queue와 Vst(방문배열), 상범이의 Queue와 Vst(방문배열)을 각각 만들어서 큐에 넣어줍니다. 불은 간단하게 BFS로 상하좌우로 퍼지게 하면서, 방문배열에 거리를 적어둡니다..