문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사실 알고리즘 문제를 하루에 한 문제 이상 풀고 있는데, 포스팅을 하지 않았습니다. 왜냐면,, 요새 스프링 공부를 열심히 하다보니... 포스팅을 하지 않는 대신 스프링 공부에 집중해야겠다고 생각했어요! 😅 10월 초 연휴를 아주 재밌게 즐기고 오고 나서, 문득 오늘 푼 알고리즘 문제라도 포스팅해보자! 하고 생각이 들어서 포스팅하게 되었습니다! 풀이 2차원 바텀업 DP로 풀이했습니다. 이 문제는 사실 전에 풀었던 2096번: 내려가기 문제와 유사한 풀이로 가능합니다. 문제의 내용처럼 경로 중 거쳐간 ..
DP
문제 링크 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net 요새 DP 문제에 빠져 있습니다.... 바텀업 DP부터 트리DP까지 공부하고 있는 도중, 예전에 외판원 순회 문제를 풀면서 접하게 되었던 비트마스크를 이용한 DP 문제를 우연히 보게 되었습니다! 이번 문제는 비트를 어떻게 이용하는지만 블로그를 참고했고, 문제풀이는 스스로 생각해서 풀(어서 뿌듯했)었습니다. 같이 풀이를 살펴보시죠! 😄 풀이 비트마스크를 이용한 DP로 풀이하면 됩니다. 이 문제를 풀 수 있으면, 외판원 순회 문제도 도전해 ..
문제 링크 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 저번주에 트리를 공부하다가 트리DP라는 친구를 만났는데 참 만만치 않았습니다. 😂 그래서 DP를 공부해야겠다 생각했고, DP 관련해서 열심히 공부해보고자 이번 문제를 풀어보게 되었습니다! 풀이 N의 크기가 크기 때문에, DP를 이용해서 풀어야 합니다. 종만북(알고리즘 문제 해결 전략)에 의하면, N의 크기가 150만이면 \(O(N\log{N})\)정도에서 커버가 가능하다고 합니다. 다시말해, \(O(N\log{N})\)이하..
문제 링크 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 어제 쓴 포스팅(행렬 곱셈 순서)에 이어서, 비슷한 유형의 문제가 있기에 풀어봤습니다. 유형은 똑같은데 다른 점이 딱 하나 있었습니다. 저는 그 다른 점을 찾지 못해서 결국 구글링을 통해 알아냈습니다..... 자세한 설명을 해주신 블로그 글의 주인분께 감사의 인사를 드립니다. 풀이 트리형태 DP + 누적합 DP를 사용하여 풀이하면 됩니다. 트리형태 DP라는 의미는 어제 쓴 포스팅(행렬 곱셈 순서)를 참고해 주시면 될 듯합니다. 전에 푼 문제와 ..
문제 링크 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 주말을 이용해서 이 문제를 풀기로 했는데... DP를 잘 못 하는 저로서는 좀 쉽지 않았습니다. 그래서 chatGPT에게 힌트를 물어보니 DP 구성 방법에 대한 힌트를 잘 설명해 줬고, 그것을 기반으로 문제를 풀 수 있었습니다. 제가 푼 방식을 필기해 둘 겸해서 블로그에 작성해봅니다. 풀이 DP 풀이를 하면 됩니다. 이 문제에서 정말 다행인 것은 항상 순서대로 곱셈을 할 수 있는 크기의 입력만 주어진다는 것입니다. 문제에서 주어진 예시에 따..
문제 링크 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..
문제 링크 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)\))으로 메모라이즈하며 ..
문제 링크 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 서론 요즘들어 DP 문제를 풀지 않아서 푸는 방법을 잊고 살고 있었습니다. 백준 문제집을 훑어보다가 좋은 DP문제가 있기에 풀어보게 되었습니다. 😄 풀이 문제에서 친절하게 그림으로 설명하듯이, 2*3칸의 구성을 잘 이용해야 합니다. 단순한 DP 풀이를 한 다음, 문제에서 주어진 메모리 제한이 \(4MB\) 여서 메모이제이션 배열의 크기가 일정 이상 커지면 메모리 초과가 발생하기 때문에 메모리 최적화 과정을 거쳐야 문제를 풀이할 수 있게 됩니다. DP 풀이 과정을 우..
