문제 https://www.acmicpc.net/problem/8895 8895번: 막대 배치 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 [백준] 고층 빌딩(1328) 문제와 완전히 동일한 풀이로 해결할 수 있다. dp[stick][l][r]를 stick 개수의 막대를 놓았을 때 왼쪽에서 l개, 오른쪽에서 r개가 보이는 경우의 수 라고하자. 모든 막대를 항상 가장 큰 막대부터 작은 막대의 순서대로 놓는다고 생각해보자. 지금까지 stick - 1개의 막대를 놓았다면 다음으로..

문제 https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 풀이 solved.ac 난이도: Platium5 [백준] 평범한 배낭(12865)의 다음 단계 문제로 같은 물건이 여러 개 있는 경우이다. 이 문제를 일반적인 배낭(Knapsack) 문제와 동일하게 해결하려 시간 복잡도가 O(N* K *M)이기 때문에 시간 초과가 발생한다. 따라서 다음과 같은 최적화가 필요하다. 물건의 개수를 2의 제곱수의 합으로 분..

문제 https://www.acmicpc.net/problem/2515 2515번: 전시장 첫째 줄에는 그림의 개수 N (1 ≤ N ≤ 300,000)과 판매가능 그림을 정의하는 1이상의 정수 S가 빈칸을 사이에 두고 주어진다. 다음 이어지는 N개의 줄 각각에는 한 그림의 높이와 가격을 나타내는 정 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 높이 순서로 정렬 후, 해당 그림이 선택될 수 있도록 하는 앞의 그림들 중 가장 높은 그림을 미리 저장해 두자. 이를 저장하는 이유는 다음과 같은 점화식을 구현하기 위해서 이다. dp[idx]를 idx번째 그림까지를 고려했을 때, 판매 가능한(선택된) 그림의 가격 합의 최대 값이라 고하자. dp[idx]를 구할 때 두 가지 경우를 고려해..

문제 https://algospot.com/judge/problem/read/PACKING algospot.com :: PACKING 여행 짐 싸기 문제 정보 문제 여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 algospot.com 풀이 종만북 난이도: 중 일반적인 배낭 문제(Knapsack)에서 추가적으로 어떤 물건을 선택했는지까지 출력해야 하는 문제이다. 배낭 문제는 DP의 대표적인 문제로, 구현 방법에는 재귀 함수를 통해 큰 문제에서 작은 문제로 내려가며 해결하는 Top-Down 방식과 작은 문제에서부터 차례로 답을 찾아 올라가는 Bottom-Up방식이 있다. 이번 문제는 Bottom-Up..

문제 https://www.acmicpc.net/problem/2570 2570번: 비숍2 첫째 줄에 정사각형 체스판의 크기 N이 주어진다. 둘째 줄에는 체스판 위에 놓인 장애물의 개수 M이 주어진다. N은 100이하의 자연수이고 M은 음이 아닌 정수이다. 이어 셋째 줄부터 한 줄에 하나 www.acmicpc.net 풀이 solved.ac 난이도: Platium 2 이분할 집합에 대해 곰곰이 생각해봐야 풀 수 있는 이분 매칭 문제. 한 좌표에 비숍을 놓으면 해당 비숍에 의해 더 이상 다른 말을 놓을 수 없는 두 대각선이 생긴다. 하지만 좌표와 두 대각선을 이분 매칭을 진행하는 것은 불가능하다. (하나의 좌표에 대각선을 두 개 매칭해 주어야하기 때문에) 따라서 방향이 다른 대각선끼리 집합을 만들어 이분 매..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 [네트워크 유량] Network Flow(최대 유량) 그래프에서 두 정점 사이에 얼마나 많은 유량(flow)을 보낼 수 있는지 계산하는 알고리즘을 네트워크 유량(Network Flow) 혹은 최대 유량(Maximum Flow) 알고리즘이 everenew.tistory.com 네트워크 유량, 최대유량 (Network Flow / Maximum Flow) ..

문제 https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 짝수와 홀수로 두 집합을 만들어 이분 매칭으로 해결하는 문제. 이분 매칭을 잘 모른다면 다음 기본 문제를 먼저 해결해보고 오자. [백준] No.2188 - 축사 배정 (C++, 이분 매칭) 두 자연수를 더하는 경우는 3가지로 분류할 수 있다. 1. 짝수 + 짝수 짝수끼리 더한 수는 짝수이기 때문..

문제 https://www.acmicpc.net/problem/9577 9577번: 토렌트 희원이가 사용하는 ACM토렌트는 하나의 파일을 공유받을 때 여러 조각으로 나누어, 조각을 지닌 시드가 접속하는 시간에 시드로 부터 일부 조각을 전송 받아 파일을 완성시키는 방법으로 파일이 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 두 집합의 대응 관계를 해결하는 이분 매칭 문제. 기본 적인 이분 매칭 문제를 해결하고 오면 이해하기 쉬울 것이다. [백준] 축사 배정(2188) 이번 문제에서 두 집합으로 선택되는 것은 시간(A set)과 조각(B set)이다. 파일이 어떤 시더에게 있는지는 상관없이, 접속 시간에 해당 파일을 다운로드할 수 있는 여부가 중요하기 때문이다. 따라서 시더..

문제 https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 이분 매칭 문제들은 최대 유량을 이용하면 간단히 해결할 수 있다. [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 이분 매칭 문제는 두 집합에서의 대응 관계를 해결할 수 있다. 대표적으로 작업 배분을 한다고 생각해보자. A집합(인원)이 할 수 있는 B집합(작업)들 중 하나 선택하여 배정받는다. 이때 최대한의 작업을 할 수..

문제 https://www.acmicpc.net/problem/11495 11495번: 격자 0 만들기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각 www.acmicpc.net 풀이 solved.ac 난이도: Platium 2 그래프 모델링이 필요한 최대 유량 문제. 문제의 설명에서는 연산을 한 번씩 진행하여 각 정수를 1씩 줄이지만 생각해보면 어떤 정수끼리 짝을 짓는 가는 중요하지 않다. 예제의 입력을 생각해보면 어떤 짝이든 짝지은 두 정수를 최대한 줄여주면 결과는 동일하다. 여기서 연산을 한번 진행할 때 전체 값의 합은 2씩 줄어드는..