문제 링크 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 저번에 풀이를 올렸던 LIS 2번 문제를 응용해서 풀 수 있는 문제입니다! 열심히 풀어봅시다~ 풀이 LIS(DP+이분탐색)을 내림차순으로 풀이하면 됩니다. 내림차순으로 풀이 후에, 열외할 병사를 출력하기 위해 내림차순으로 저장한 배열(seq)의 크기를 n에서 빼주었습니다. 전에 썼던 LIS 2번 문제 와 흐름이 거의 동일하니, 자세한 풀이는 링크를 참고해주세요! 풀이코드 #include using namespace std; #de..
Study
문제 링크 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로 상하좌우로 퍼지게 하면서, 방문배열에 거리를 적어둡니다..
문제 링크 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 간단하게 소수 복습을 할 수 있는 문제입니다! 사실 오랜만에 소수 문제를 풀려니, 에라토스테네스의 체를 까먹어버려서(...) 전에 풀었던 소수 문제를 참고해서 문제를 풀었습니다. 복습이 되서 좋았습니다. 풀이 간단하게 소수(정수론) + 투포인터로 풀이가 가능합니다. MAX(`4000000`)까지의 소수를 모두 구해줍니다. 투포인터를 활용해서 부분합을 구한 뒤, 제시된 N과 부분합이 일치한다면 결과값+1 을 해줍니다. 풀이코드 C++ 풀이코드 #include using namespace std; #define endl "\n" const int MAX = 4000001; ..
문제 링크 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 그리디 문제집의 문제들을 살펴보다가, 재밌어 보이는 문제가 있어서 풀어보게 됐습니다. 처음에는 BFS로 풀면 되겠지하고 BFS로 풀어봤는데 모든 경우의 수를 탐색하는 것은 아니어서 틀렸습니다. 질문 게시판을 참고하니 DFS로 풀었다는 글이 다수여서 DFS로 풀었더니 시간초과가 발생했고, vst 배열로 오른쪽 끝까지 갈 수 없는 길을 다시 가지 않도록 최적화했더니 겨우 통과가 되었습니다. 배낭문제같은 그리디 문제만 접하다가 이런 DFS를 활용한 그리디 문제를 접하게 되..
문제 링크 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 제가 요즘 자신없어하는 알고리즘 종류가 그리디 문제입니다. 그래서 그리디 문제를 여러개 풀며 공부하던 도중, 재밌는 문제를 하나 발견해서 풀이를 올려보겠습니다! 풀이 모노톤 스택을 이용해서 그리디로 풀면 됩니다. 모노톤 스택을 한마디로 말하자면, 스택 원소들을 오름차순 또는 내림차순으로 유지시키는 스택입니다. 이 성질을 이용해서, 다음과 같은 과정으로 문제를 풀이했습니다. true면 결과값에 포함하지 않을 chk 배열을 선언합니다. 예를 들면, [1, 2, 3, 4] 이라는 배열이 있고, chk 배열이 [true, true, f..
문제 링크 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 오랜만에 다익스트라 문제를 풀어봤습니다! 알고리즘이 어떻게 돌아가는지는 알긴했는데 오랜만이라 까먹어서(...) 다익스트라 알고리즘만 구글링으로 참고했습니다. 이번 문제는 (다익스트라만 알면) 그렇게 어렵지는 않았고, 아이디어만 잘 생각하면 풀 수 있는 문제여서 기분 좋게 코딩할 수 있었습니다. 풀이 1부터 N까지 갈 때, 두 점(v1, v2)을 반드시 지나는 최단경로의 길이를 코딩하면 됩니다. 필자의 처음 ..
