문제에서 말하는 오등큰수는 이 수가 나타난 수보다 더 많이 나타난 수 중 가장 가까운 오른쪽 수를 의미합니다. 특정 수의 오등큰수가 없을 수가 있습니다. 이런 경우 그 수의 오등큰수는 -1로 정해줍니다. 문제의 예제는 이렇습니다.
A = [1, 1, 2, 3, 4, 2, 1]
우선 F(Ai)는 빈도수라고 하여 차례대로 빈도수를 구하면 이렇게 되겠네요.
F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1
이렇게 빈도수가 구해지면 NGF라는 오등큰수를 구할 수 있습니다. NGF(1)을 구하는데, 1보다 빈도수가 큰 수는 없으므로 NGF(1) = -1이 됩니다. NGF(2) = 1이됩니다. 왜냐면 2보다 빈번하게 나타난 수는 1이고 이 수가 가장 가까운 오른쪽에 있는 수가 되기 때문이죠. 예제의 답은 그래서 아래와 같습니다.
-1 -1 1 2 2 1 -1
풀이
이 문제는 스택으로 풀 수 있습니다. 우선 F(Ai)를 구해야하는데요. 이건 간단합니다. 비어있는 배열 F에 입력받은 수를 index삼아서 하나씩 증가시키면 되기 때문입니다. 이제 F를 구했으면 스택을 이용해서 본격적으로 문제를 풀어봅시다.
아래의 블록은 F를 나타냅니다. 높을 수록 F가 높다는뜻입니다.
왼쪽의 빨간 블록의 오등큰수를 구하려면 오른쪽에서 찾아야합니다. 그런데 자신보다 큰 오등큰수가 두개가 있습니다. 4와 3이 있네요. 이때 빨간색의 오등큰수는 4가 됩니다. 이때 3은 이 다음 왼쪽 수의 오등큰수가 될 수 있을까요? 이미 4한테 막혀있고 4가 더 큰값이기 때문에 가능성이 없습니다. 그래서 3은 지워버립니다. 대신 4가 왼쪽의 오등큰수가 될 수 있는것을 알 수 있네요.
따라서 현재 자신보다 큰 값의 오등큰수가 존재하면 스택에 저장하고 작거나 같으면 스택에서 지워버리는 식으로 문제를 풀 수 있습니다.
코드
문제 해답에 대한 전체코드는 아래와 같습니다.
#include <cstdio>
#include <stack>
using namespace std;
int n;
int F[1000001], ans[1000001], nums[1000001];
stack<int> st;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &nums[i]);
F[nums[i]]++;
}
for (int i = n - 1; i >= 0; i--) {
int number = nums[i];
int height = F[number];
while (!st.empty()) {
int topNum = nums[st.top()];
int topHeight = F[topNum];
if (height >= topHeight) st.pop();
else break;
}
ans[i] = -1;
if (!st.empty()) ans[i] = nums[st.top()];
st.push(i);
}
for (int i = 0; i < n; i++)
printf("%d ", ans[i]);
printf("\n");
}
같은 글자를 짝지어 주는 문제입니다. 아치형으로 서로 짝을 지어주고 모든 짝을 지어줄 수 있다면 그 단어는 좋은 단어라고 합니다. 단, 아치형이 서로 겹치지 않게 짝을 이뤄줘야합니다. 아래의 그림을 보면 바로 이해가 가실겁니다.
다음의 경우에는 좋은 단어입니다. 아치형이 겹치지 않죠
좋은단어
아래의 경우는 아치가 겹치므로 좋은단어가 아닙니다.
안좋은 단어
풀이
이 문제의 힌트는 바로 스택을 활용한 괄호 짝 맞추기 문제입니다. 가장 최근에 나온 짝이 자신의 짝인지 확인하는 문제와 컨셉이 같은데요. 여기서 괄호( '(', ')' )만 살짝 'A','B'로 바꾼것일 뿐입니다.
ABBA를 예로 들겠습니다.
1. A는 스택이 이미 비어있으니 스택에 집어넣습니다. (현재 스택 - A)
2. B는 스택 꼭대기 글자가 A이므로 B는 스택이 저장합니다. (현재 스택 - A B)
3. B는 스택 top의 글자가 B이므로 이전의 B를 스택에서 pop합니다. (현재 스택 - A)
4. A는 현재 스택 top의 글자와 같으므로 A를 스택에서 pop합니다. (현재 스택 - ' ' )
코드
아래는 전체 문제 풀이 코드입니다.
#include <cstdio>
#include <stack>
#include <string.h>
using namespace std;
char str[100001];
int n;
int main() {
int ans = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%s", str);
stack<char> st;
int m = strlen(str);
for (int j = 0; j < m; j++) {
if (!st.empty()&&st.top()==str[j]) st.pop();
else st.push(str[j]);
}
if (st.empty()) ans++;
}
printf("%d\n", ans);
}
이 문제는 가중치가 주어진 트리에서 leaf과 leaf 사이, 혹은 루트와 leaf 사이의 모든 가중치의 합 중 가장 큰 값을 구하는 문제입니다.
예제에서 주어진 그래프에서는 45의 값으로 답이 됩니다. 빨간색 선을 따라가면 9 - 5 - 3 - 6 - 12의 노드를 지나게 되고 가중치 합은 45라는 것을 알 수 있습니다. 이 값보다 큰 값은 존재하지 않습니다.
이 문제는 트리를 사용하여 풀 수 있습니다. 트리의 잎부터 시작해 올라오면서 서브트리의 양쪽 잎까지의 가중치 합과 서브트리의 루트와 잎까지 합중 가장 큰 값으로 계속 업데이트를 하면 됩니다.
설명 및 전체 코드
입력받은 값으로 트리를 구성해야하는데, 이때 Node라는 구조체로 노드를 만들겠습니다. 이 Node 구조체는 자식 Node들을 가지고 있고, 부모로 향하는 weight값을 가지고 있는 구조체로 정의되어 있습니다. 노드의 자식은 여러개일 수 있으므로 vector를 사용했습니다.
typedef struct Node {
vector<Node*> children = vector<Node*>();
int weight;
};
기저사례로는 자식이 없을 경우 바로 부모로 향하는 weight를 return해줍니다. 더 이상 진행할 필요가 없으니까요. 그리고 자식이 한개일 경우에는 weight와 그 밑으로 향하는 큰 값중 하나를 더해서 반환해주면 됩니다.
if (root->children.size() == 0) return root->weight;
if (root->children.size() == 1)
return root->weight + traverse(root->children[0]);
그 외에는 자식이 둘 이상이겠죠. 양쪽으로 분기되는 값 중 가장 큰 값 두개를 선택해서 더해준 값을 현재까지 업데이트된 값하고 비교하여 둘 중 가장 큰 값으로 업데이트해줍니다. 현재까지 업데이트된 값을 value라고 임시로 정해줍시다.
이 과정을 루트로 올라올때까지 진행해주면 답을 구할 수 있습니다. 아래는 정답 코드입니다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
typedef struct Node {
vector<Node*> children = vector<Node*>();
int weight;
};
Node nodes[10001];
int value = 0;
int traverse(Node *root) {
//자식이 없는 경우 부모쪽으로 가는 간선의 값 return
if (root->children.size() == 0) return root->weight;
//자식이 하나일 경우 자신의 weight을 더해 return
if (root->children.size() == 1)
return root->weight + traverse(root->children[0]);
//여기서부터는 자식이 둘 이상
vector<int> weights = vector<int>(root->children.size());
//자식들 모두 다 돌때까지
for (int i = 0; i < root->children.size(); i++)
weights[i] = traverse(root->children[i]);
//오름차순으로 정렬
sort(weights.begin(), weights.end());
//가장 큰 값을 가진 두 값을 더해서 value와 비교하여 value업데이트
value = max(weights[root->children.size()-1]
+ weights[root->children.size()-2], value);
//현재의 weight와 다 더한값의 제일큰 weights값을 더하여 return
return root->weight+weights[root->children.size()-1];
}
int main() {
scanf("%d", &n);
nodes[1] = Node();
nodes[1].weight = 0;
n--;
for (int i = 0; i < n; i++) {
int from, to, weight;
scanf("%d %d %d", &from, &to, &weight);
nodes[to] = Node();
nodes[to].weight = weight;
nodes[from].children.push_back(&nodes[to]);
}
int ret = max(value, traverse(&nodes[1]));
printf("%d\n", ret);
}
여기서 가장 먼저 시작하는 회의를 선택해서는 이 답을 찾을 수 없습니다. 예를 들어 회의가 (0 5), (3 4), (4 5), (6 8), (5 10) 이렇게 5개가 예정이 되어있다고 가정하겠습니다. 가장 먼저 시작하는 회의를 고른다면 만약 (0 5), (5 10)이 됩니다.하지만 (3 4), (4 5), (6 8)로 3개로 더 많은 회의를 진행할 수 있지요.
혹은 가장 짧게 회의를 진행하는 순서대로 회의를 진행하면 답을 찾을 수 있을 것 같긴하지만 다음과 같은 상황((1 7), (5 9), (8 13)이 있는 회의)이 발생한다면 오답이 발생하게 됩니다.
greedy
(5 9)가 가장 짧은 회의로 그것을 먼저 선택했을때는 1개밖에 진행할 수가 없고, 나머지를 선택하면 2개를 진행할 수 있게 됩니다. 이것도 역시 해답은 아니군요.
결론은 항상 가장 먼저 끝나는 회의 먼저 배정해주면 됩니다. 그리고 겹치는 회의를 제거하면 되지요. 즉, 아래와 같은 순서대로 회의를 지정해주면 됩니다.
1. 현재 남아있는 회의들 중 가장 먼저 회의가 끝나는 것부터 출력하고 가장 마지막에 끝난 회의라고 하여 lastFinishedTime에 끝난 시간을 기록합니다.
2. 그리고 이 회의와 겹치지 않는 가장 먼저 끝나는 회의를 선택하여 출력합니다. 그러려면 lastFinishedTime보다 그 다음 진행할 회의의 시작 시간보다 작거나 같아야합니다.
3. 이 과정을 배열이 끝날때까지 반복합니다.
입력은 가장 먼저 끝나는 순서대로 주어지지 않을 수 있으니, 끝나는 순서로 정렬하는 과정이 필요합니다.
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N;
vector<pair<int, int> > arr;
int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
int start, end;
scanf("%d %d", &start, &end);
//정렬은 첫번째 기준으로 정렬이 되기 때문에 end, start 로 pair
arr.push_back({ end,start });
}
//끝나는 순서대로 정렬
sort(arr.begin(),arr.end());
int ret = 1;
int lastFinishedTime = arr[0].first;
for (int i = 1; i < arr.size(); i++) {
int nextStartTime = arr[i].second;
if (lastFinishedTime > nextStartTime) continue;
lastFinishedTime = arr[i].first;
ret++;
}
printf("%d\n", ret);
}
BOJ 1931 회의실 배정 문제를 풀어보았습니다. 이 문제는 탐욕 알고리즘과 정렬 알고리즘이 섞인 문제였습니다.
1박 2일의 상근이가 나무가 필요한데, 벌목하고 잘린 나무를 사용한다는 내용입니다. 이때 벌목할때 쓰는 목재절단기는 한번에 H만큼 높이까지 모든 나무를 한번에 자를 수 있다고 합니다. 환경을 생각하는 상근이는 나무가 최대한 잘려나가지 않고 필요한 나무를 얻어내는것이 목표입니다.
만약 나무 4개가 20m, 15m, 10m, 17m가 있고 상근이가 필요한 나무는 7m일때 목재절단기의 높이가 15m가 되면 첫번째 나무에서 5m, 네번째 나무에서 2m를 얻어낼 수있으므로 잘리는 높이를 15m로 정해주어야하죠. 필요한 나무를 다 채우면서 나무를 최대한 높게 자르려면 절단기의 높이를 어떻게 정해야할까요?
풀이
나무의 수 N과 구하고자 하는 상근이의 나무 M이 주어지고 범위가 1<= N <= 1,000,000, 1<= M <= 2,000,000,000입니다. 보통 이런식으로 말도 안되는 큰 값을 범위로 주면 log가 섞여있는 알고리즘으로 풀어야합니다. 떠올려볼 수 있는 알고리즘이 빠른 정렬 알고리즘, 이진탐색 등이 있겠네요.
우선 중간 정도의 높이 정해보고 만약 상근이가 가져갈 수 있는 양이면 점차적으로 높이를 높이는 방식으로 접근하면 됩니다.
어떤 높이 height가 주어졌을때 이 height로 잘린 트리의 남은 부분을 전부 합쳐 M 이상이면 이 height는 H의 조건을 만족하게 됩니다. 이 함수가 아래의 isPossible이지요.
bool isPossible(unsigned int height) {
unsigned int taken = 0;
for (int i = 0; i < N; i++) {
if (trees[i] >= height)
taken += (trees[i] - height);
if (taken >= M) return true;
}
return false;
}
그래서 만약 그 높이가 가능하다면 높이를 올립니다. 그리고 다시 가능한지 확인하죠. 아래의 코드는 이진탐색의 코드입니다.
isPossible에서 true가 반환되었다면 일단 답이 될 후보이며 ret에 그 값을 저장해놓습니다. 그리고 left의 값을 mid + 1로 증가시켜 자를 높이를 높게만들죠. isPossible이 false가 반환되었다는 것은 이 값은 답 후보가 아니라는 겁니다. 그래서 자를 높이를 아래로 조정합니다.
right는 입력에서 들어올 수 있는 가장 큰 값으로 지정을 했는데, 정석대로 풀려면 나무들을 순회하면서 가장 큰 나무의 높이가 right가 되어야겠죠? 하지만 이진탐색은 빠르니까 가장 큰 값을 지정해도 문제는 없습니다.
int solve() {
unsigned int left = 0, right = 1000000000;
unsigned int mid,ret;
while (left <= right) {
mid = (left + right) / 2;
if (isPossible(mid)) {
ret = mid;
left = mid + 1;
}
else {
right = mid - 1;
}
}
return ret;
}
그리고 이진 탐색에서 나무들은 모두 정렬된 상태여야합니다. 그래서 문제를 풀기 전에 sort로 정렬합니다. 아래는 전체 코드입니다.
#include <iostream>
using namespace std;
int N;
long long M;
long long trees[1000001];
bool isPossible(unsigned int height) {
unsigned int taken = 0;
for (int i = 0; i < N; i++) {
if (trees[i] >= height)
taken += (trees[i] - height);
if (taken >= M) return true;
}
return false;
}
int solve() {
unsigned int left = 0, right = 1000000000;
unsigned int mid,ret;
while (left <= right) {
mid = (left + right) / 2;
if (isPossible(mid)) {
ret = mid;
left = mid + 1;
}
else {
right = mid - 1;
}
}
return ret;
}
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++)
cin >> trees[i];
cout << solve() << endl;
}
위 풀이의 시간은 O(N log(M)) 입니다. isPossible은 모든 나무를 돌아가며 연산하기 때문에 N, 그리고 이진 탐색의 뼈대인 solve함수가 log M이 되죠.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
int n, m;
int mine[500001];
int binarySearch(int left, int right, int num) {
if (left == right) return mine[left] == num;
int mid = (left + right) / 2;
if (mine[mid] == num) return 1;
if (mine[mid] > num)
return binarySearch(left, mid, num);
return binarySearch(mid + 1, right, num);
}
int main() {
scanf("%d",&n);
for (int i = 0; i < n; i++)
scanf("%d",&mine[i]);
sort(mine, mine + n);
scanf("%d",&m);
for (int i = 0; i < m; i++) {
int card;
scanf("%d",&card);
printf("%d ",binarySearch(0,n-1,card));
}
printf("\n");
return 0;
}
탐색을 위해 문제의 입력을 갖고 있는 카드를 우선 정렬합니다. 위 코드가 해답인 코드입니다. 그리고 난 후 이진탐색으로 그 카드의 인덱스가 있는지 확인하는 방법으로 카드가 있는지 아닌지 확인할 수 있습니다.
위상 정렬은 무엇일까요? 여러 작업들이 있을때 특정 작업을 수행하기 전 진행되어야 할 작업들이 있을텐데요. 이 작업들을 순서에 맞게 정렬해주는 것이 바로 위상정렬이라고 합니다. 이때 각 작업들은 직전 작업에 의존하게 되죠. 예를 들어 C라는 작업을 끝내기 위해서는 A작업과 B작업이 끝나야지만 C작업을 시작할 수 있는데, C는 A와 B가 끝날때까지 일을 실행하지 못하므로 A와 B에게 의존하고 있다고 봐야겠죠.
위상정렬은 우리 삶에도 영향이 있습니다. 예를 들어 요리할때나 청소할때, 여러분이 좋아하는 게임을 할때도 일의 순서등 말이죠.
위상정렬은 깊이 우선 탐색(Depth First Search, DFS)로 풀 수 있는 대표적인 정렬 방법입니다. 여기서 그래프는 의존성 그래프(Dependency Graph)의 모양을 띄고 있어야하는데, 그 말은 각 정점(작업)의 의존 관계를 간선으로 나타낸 방향 그래프라는 의미입니다. 만일 작업 v는 u가 끝나야만 수행할 수 있다면(v가 u에 의존한다면), 그래프는 u->v로 향하는 간선을 포함하게 됩니다. 의존성 그래프에서는 사이클이 존재할 수 없습니다.
자, 여기 작업을 나타내는 의존성 그래프가 있습니다.
dependency graph
위상정렬 순서 단계별 알아보기
작업 순서)
B와 C는 A가 작업을 끝나야만 실행 가능
D는 B와 C가 작업을 끝나야만 실행 가능
E는 C가 끝나야만 실행 가능
F는 D와 E가 작업을 끝나야만 실행 가능
만약 여기서 F가 A로 향하는 간선이 있다면 어떻게 될까요? 그렇다는 의미는 A는 F 다음으로 수행가능 하다는 것인데, A는 이미 수행했기 때문에 모순입니다. 그렇기 때문에 의존성 그래프에는 사이클이 발생하지 않습니다. 이 그래프를 보기좋게 옆으로 돌려보도록 하겠습니다. 그러면 아래의 모양이 나오겠네요.
dependency graph2
DFS를 이용해서 이 그래프의 위상정렬을 하면 결과는 이렇습니다. A C E B D F
여기서 힌트는 DFS를 종료한 역순이라는 것이 위상정렬된 결과라는 점입니다. 글로는 이해가 어려울 수 있으니, 이제 DFS를 통해서 어떻게 이 그래프가 위상 정렬이 되는지 그 과정을 보도록 합시다. 그전에 DFS를 방문할 노드의 규칙을 다음과 같이 정합시다. 연결된 정점 중 알파벳 순서가 가장 낮은 정점부터 탐색하는 것으로요.
1. 들어오는 간선이 없는 A부터 DFS 탐색을 실시하면 아래의 그림과 같이 F에서 끝이 납니다. F는 이때 더 이상 나가는 간선이 없으니까 F는 종료가 됩니다. - 종료 순서 F
f finish
2. F가 반환되면 D가 다음 종료됩니다. 여기서 D에서 더 이상 방문할 정점이 없으니까요. - 종료 순서 F D
D finish
3. B역시 마찬가지로 종료됩니다. - 종료 순서 F D B
4. 이후 A는 종료되지 않습니다. 왜냐면 C와 연결된 정점이 있으니까요. 그래서 결국 E까지 DFS가 탐색을 하여 도달하게 됩니다. E는 더이상 방문할 노드가 없습니다. 그러니 종료하게 됩니다. - 종료 순서 F D B E
E finish
5. C는 D와 연결된 간선이 있는데 이전에 D는 방문 됐었죠? 그러니 C도 더 이상 방문할 정점이 없으니 종료됩니다. - 종료 순서 F D B E C
C finish
6. 이제 A는 더 이상 방문할 노드가 없으니 종료됩니다. 종료 순서 F D B E C A
A finish
DFS가 종료된 순서는 F D B E C A 인데, 이 순서를 역으로 취하면 A C E B D F 입니다. 어때요? 우리가 원하는 결과를 얻을 수 있죠?
그리고 아래의 코드는 위상정렬을 구현한 코드입니다.
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M;
vector<vector<int> > adj;
vector<bool> visited;
vector<int> order;
void dfs(int here) {
visited[here] = true;
for (int there = 0; there < adj.size(); there++) {
if (adj[here][there] && !visited[there])
dfs(there);
}
//위의 정점이 다 종료된 후에 이 곳의 정점(here)이 추가가 되어야함
order.push_back(here);
}
void topologicalSort() {
int n = adj.size();
visited = vector<bool>(N, false);
order.clear();
//들어오는 간선이 없을 경우가 있을 수 있으므로 모두 DFS 탐색
for (int i = 0;i<N;i++)
if (!visited[i]) dfs(i);
//종료된 순서를 거꾸로 만든다.
reverse(order.begin(), order.end());
}
void printOrder() {
for (int i = 0; i < order.size(); i++)
printf("%c ", order[i] + 'A');
printf("\n");
}
int main() {
printf("정점의 갯수 : ");
scanf("%d", &N);
printf("간선의 갯수 : ");
scanf("%d", &M);
visited = vector<bool>(N, false);
adj = vector<vector<int>>(N, vector<int>(N, 0));
for (int i = 0; i < M; i++) {
char from, to;
printf("정점1 -> 정점2 : ");
scanf(" %c %c", &from, &to);
adj[from-'A'][to-'A'] = 1;
}
topologicalSort();
printOrder();
}
topologicalSort안에 dfs를 전부 호출하는 이유는 아래의 그림과 같은 정점이 있을 수 있기 때문입니다. 여기서 G는 A와 같이 들어오는 간선(inboud-edge)이 없으므로 A부터 수행한 DFS에서는 G정점이 방문되지 않습니다. 그렇기 때문에 모든 정점을 방문하는 것입니다.
dfs를 전부 수행하는 이유
위의 코드를 실행한 결과를 보면 위상정렬이 잘 된 것임을 확인할 수 있습니다.
첫번째 그래프의 결과
그리고 제가 제시했던 바로 위의 그래프의 위상정렬 결과는 아래와 같습니다.
두번째 그래프의 결과
이상으로 위상정렬에 대해서 알아보았습니다. DFS의 응용이면서 결코 어렵지 않은 주제니까 원리와 코드는 알아두시면 좋겠습니다. 위의 코드는 구종만 저자님의 알고리즘 문제 해결 전략을 변형해서 만든 코드입니다.
그래프에서 정점의 짝을 이루게 해볼까요? 정점은 다른 정점과 짝이 될 수 있는데, 단 여기서 한 정점은 최대 한 정점과 짝을 이룰 수 있는 조건으로 말이죠. 정점이 모두 선택될 필요는 없습니다. 아래의 그래프가 그 예를 보여줍니다. 왼쪽은 1:1 매칭이 된 간선을 선택한 것이고 오른쪽은 1:1 매칭이 되지 않은 그래프입니다. 왼쪽의 그래프는 간선을 3개 갖는데 각 정점은 1:1로 짝을 이루고 있네요. 하지만 오른쪽 그래프에서 주황색 정점은 위, 아래 정점 2개와 짝을 이루고 있으니 1:1 매칭이 되었다고 볼 수 없습니다.
정점을 보기좋게 두 그룹으로 나누면 어떨까요? 왼쪽에 정점이 오른쪽에 정점과 연결될 수 있도록 보면 더 보기 편할 거 같습니다.
이처럼 그래프의 정점을 두 그룹으로 나눈 후 모든 간선이 서로 다른 그룹의 정점들을 연결할 수 있는 그래프를 이분 그래프라고 합니다. 여기서 가장 큰 매칭을 찾아내는 문제를 최대 매칭 문제(Maximum Matching)라고합니다. 간단하게 이분 매칭이라고 부릅니다.
이분 매칭을 네트워크 유량을 이용하여 풀게 됩니다. 그보다는 아주 간단하게 dfs를 이용해서 풀 수 있습니다. 이분 매칭을 구현한 코드가 아래에 있습니다. (이 코드는 구종만 님의 알고리즘 문제해결 전략의 코드입니다.)
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
const int MAX_N = 201;
int adj[MAX_N][MAX_N];
vector<bool> visited;
vector<int> partner;
int N, M;
bool dfs(int here) {
if (visited[here]) return false;
visited[here] = true;
for (int there = 1; there <= M; there++) {
if (adj[here][there]) {
//there의 짝이 정해지지 않았거나
//there의 짝이 다른짝과 매칭된다면 true반환
if (partner[there] == -1 || dfs(partner[there])) {
partner[there] = here;
return true;
}
}
}
return false;
}
int bipartiteMatch() {
int ret = 0;
for (int i = 1; i <= N; i++) {
visited = vector<bool>(N + 1, false);
if (dfs(i)) ret++;
}
return ret;
}
왼쪽의 정점은 A, 오른쪽의 정점은 B라고 칭한다면 partner라는 배열은 B와 짝이된 A정점을 뜻합니다. 초기화는 아래와 같이 -1로 초기화시킵니다. partner[b]가 -1이면 아직 짝이 정해지지 않은 정점을 의미합니다.
partner = vector<int>(M + 1, -1);
전체적으로 보면 왼쪽(here)에서 하나 씩 dfs를 탐색하는데요. dfs를 통해 짝을 찾을 수 있다면 매칭된 수를 하나 증가시킵니다. 코드와 글로는 이해가 어렵습니다. 그림이 있어야겠네요. 처음에 파란색 정점이 dfs를 수행합니다. 이때 조건문을 잘보세요. 설명을 편하게 하기 위해서 왼쪽 정점은 숫자, 오른쪽 정점은 알파벳으로 가정하도록 하겠습니다.
정점 1은 정점 a와 연결이 되고 있고(adj[1][a]), partner[a]의 짝은 아직 정해지지 않았으니, partner[a]=1이 되고 dfs는 true를 반환합니다. 그러니 짝을 하나 찾았네요.
이제 2번에서 dfs를 수행합니다. 연결된 간선의 정점이 a인데, a는 이미 짝이 있으나, a의 파트너인 1이 다른 짝과 매칭될 수 있는지(dfs(1))을 보는데요. 1은 다시 a로 가려고 하지만 이미 방문된 정점(visited[a]=true)이기 때문에 다른 연결된 c쪽으로 탐색합니다. c는 아직 짝이 정해지지 않았기 때문에 c의 파트너를 1로 정합니다. 그 결과 a의 파트너는 3이 될 수 있네요.
이제 다음 정점인 3에서 dfs를 시작합니다. 연결된 정점은 a와 c인데요. a는 이미 짝이 정해져있으나, partner[a]에서 dfs를 수행하면 다른 짝을 구할 수도 있으니 dfs(partner[a]) = dfs(1)를 수행합니다. dfs(1)은 dfs를 수행하지 않은 c로 탐색을 수행할텐데, 이때 c와 유일하게 연결된 정점 3은 이미 방문된 상태이므로 결국 다른 짝을 찾지 못했습니다.
이제 3의 다른 정점 c도 역시 같은 방법으로 경로를 찾는데 c는 이전에 방문되었던 상태라서 종료합니다. 결국 3에서 dfs를 수행한 결과 다른 짝을 찾지 못했네요.
이 문제는 위의 코드를 그대로 구현하여 풀 수 있습니다. N마리의 소와 M개의 축사가 있는데, 각 소들은 들어가길 희망하는 축사가 있어 그 외의 축사는 들여보낼 수 없습니다. 소가 희망하는 축사는 여러개가 될 수 있는데요. 이때 소를 최대한으로 들여보낼 수 있는 수를 구하는 것입니다. (1<= N,M <= 200)
첫줄에는 N,M을 입력으로 받고 그 다음부터 차례대로 N 줄까지 1번 소가 원하는 축사의 수, 축사의 번호를 차례대로 입력받습니다. 그때 입출력의 예는 아래와 같습니다.
입력
출력
5 5 2 2 5 3 2 3 4 2 1 5 3 1 2 5 1 2
4
이 문제를 해결할 수 있는 전체 코드는 아래와 같습니다.
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
/*이분매칭
소와 방을 1:1로 짝을 지을 수 있는 최대수를 반환
*/
const int MAX_N = 201;
int adj[MAX_N][MAX_N];
vector<bool> visited;
vector<int> partner;
int N, M;
bool dfs(int here) {
if (visited[here]) return false;
visited[here] = true;
for (int there = 1; there <= M; there++) {
if (adj[here][there]) {
//there의 짝이 정해지지 않았거나
//there의 짝이 다른짝과 매칭된다면 true반환
if (partner[there] == -1 || dfs(partner[there])) {
partner[there] = here;
return true;
}
}
}
return false;
}
int bipartiteMatch() {
int ret = 0;
for (int i = 1; i <= N; i++) {
visited = vector<bool>(N + 1, false);
if (dfs(i)) ret++;
}
return ret;
}
int main() {
cin >> N >> M;
partner = vector<int>(M + 1, -1);
for (int from = 1; from <= N; from++) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int to;
cin >> to;
adj[from][to] = 1;
}
}
cout << bipartiteMatch() << endl;
return 0;
}
설탕 3kg, 5kg 봉지가 있는데 특정 kg수를 봉지를 최대한 적게 사용하여 만드려고 할때 가장 적게 쓰는 봉지의 수를 구하는 문제입니다.
18kg를 3kg봉지와 5kg봉지를 사용하여 채우려면 3kg짜리 6개를 써서 18kg를 만들 수도 있습니다.
하지만 5kg 짜리 3개와 3kg짜리 1개를 사용하여 만들면 총 4개의 설탕봉지를 사용합니다. 그러니까 4가 답이되는 것입니다.
3kg와 5kg만 사용하므로 만들 수 없는 수도 존재합니다. 그럴때는 -1을 출력하는 문제입니다.
입력은 채우는 설탕의 kg수 N이 주어지고 N의 범위는 3이상 5000이하(3<= N <=5000)입니다.
몇가지 입력에 대한 출력을 먼저 보고 문제를 풀어보시고 풀이를 봐주세요.
INPUT
OUTPUT
19
5
20
4
91
19
4999
1001
7
-1
풀이1 - DP
두가지 풀이가 있습니다. 전형적인 DP방식의 풀이와 그리디한 방식으로 푸는 방법이지요. 첫번째 풀이는 DP를 사용한 풀이입니다.
만약 현재 i kg를 달성하려면 이 전에 계산한 (i-3)kg와 (i-5)kg 중 작은 것에 1을 더하면 현재 i kg을 채울 수 있는 최소의 봉지수가 나오겠네요.
dp[i] = min(dp[i-3] + 1, dp[i-5] +1)
그런데 만들 수 없는 수는 0이겠죠? 예를 들면 4는 절대로 3과 5를 조합하여 만들 수가 없는데요. 그러면 항상 0이 최소의 수가 되니까 조건을 달아야합니다.
만약 dp[i-3]에 0보다 큰 값이 있을때, dp[i-5]일때 0보다 큰 값이 있을때 만 계산하게 만드는 것입니다.
코드는 아래와 같습니다.
#include <iostream>
using namespace std;
int dp[5001]; //global 변수이기때문에 0으로 초기화된 배열
int main() {
int n;
cin >> n;
//3kg와 5kg를 만드는 가장 최소의 봉지수는 1
//따라서 dp[3]과 dp[5]는 무조건 1
dp[3] = dp[5] = 1;
//3과 5 다음인 6부터 for loop 순회
for (int i = 6; i <= n; i++) {
if (dp[i - 3]) dp[i] = dp[i - 3] + 1;
//이미 dp[i-3]에 값이 존재할때 dp[i]가 업데이트 됐었을 수 있다.
//만약 dp[i]에 값이 없다면 dp[i] = dp[i-5] +1 로 업데이트
if (dp[i - 5]) dp[i] = dp[i] ? min(dp[i] , dp[i - 5] + 1) : dp[i - 5] + 1;
}
cout << (dp[n] == 0 ? -1 : dp[n]) << endl;
return 0;
}
먼저 dp라는 배열을 0으로 셋팅해놓고 (전역변수이기 때문에 저절로 0으로 초기화됩니다.) dp[3] = dp[5]를 1로 만든 후에 앞서 설명한 것을 for문 안에 구현하면 됩니다.
풀이2 - Greedy
설탕이 25kg가 있다면 5kg로만 계속 사용하여 채우면 됩니다. 그러면 5개 봉지만 사용하면 되겠네요. 그렇다면 우리가 kg을 사용할 일이 굳이 있을까요? 우리가 5kg으로 모두 채울 수 있다는 것을 미리 알면 오히려 3kg를 사용하면 불리하다는 것을 알 수 있습니다. 그렇다면 5kg으로 나눠진다는 것만 알면 되지 않을까요? 이때 mod연산 %연산이 사용됩니다. %5 연산을 하여 0이 되지 않는다면 3kg를 봉지를 사용해야겠죠.
그리고 난 후 다시 5kg로 나눠 떨어지는지 확인합니다. 만약 나눠떨어지면 나눈 몫만큼의 5kg봉지가 사용되고 프로그램을 바로 종료시키면 되는 아이디어입니다.
전체 C++ 소스코드는 아래와 같습니다.
#include <iostream>
using namespace std;
int N;
int main() {
cin >> N;
int ans = 0;
while (N>=0) {
if (N % 5 == 0) { //가장 큰 수로 나누는게 가장 작은수랑 섞어서 나누는 것보다 유리
ans += (N / 5); //나눈 몫을 더한 것이 정답
cout << ans << endl;
return 0;
}
N -= 3; //3kg을 빼고
ans++; //가방 하나 늘어남
}
cout << -1 << endl;
}
두가지 방식의 풀이를 알아보았는데 저도 얼핏 dp만 생각하고 있었는데 다른 사람의 해답을 보니 이러한 방법이 있다는 것을 알았습니다. 역시 저빼고 다른 사람들은 똑똑한것 같습니다.
배열 첫번째 모양은 일자모양(l)이고, 두번째는 ㅗ모양입니다. 세번째 모양은 L자 모양이 되겠습니다. 이것을 사방으로 회전하다 보니까 2차원 배열이 한 줄에 최대 4개까지 나오며, 일자모양과 정사각형 모양 등 네 방향으로 회전할때 같은 모양이 나올 경우는 4개까지 나오지 않지요.
실제 문제를 푸는 코드는 아래에 있습니다.
static int maxValue(int y,int x){
int max=0;
for(int next=0;next<19;next++){
int r=shapes[next].length;
int c=shapes[next][0].length;
if(y+r>n||x+c>m) continue;
int sum=0;
for(int i=y;i<y+r;i++) for(int j=x;j<x+c;j++)
sum+=map[i][j]*shapes[next][i-y][j-x];
max=Math.max(max, sum);
}
return max;
}
인자로 받은 y와 x는 비교할 위치를 말합니다. y는 세로축, x는 가로축의 좌표라고 보면 됩니다.
우리는 회전해서 나온 각각의 모양 19개(3차원 배열속의 2차원 배열 갯수)를 위에서 만들었지 않았나요? 그러니 for문을 19번 반복을 하는 겁니다.
이 for문 안에 r과 c는 만들었던 모양의 가로 길이, 세로 길이를 나타냅니다. 만약 {{ 0,1,0 }, { 1,1,1 }}의 (ㅗ)모양이라면 r의 값은 2, c의 값은 3이 되는 겁니다. 이런 길이가 입력 받은 보드의 범위를 넘어가게 되면 구할 필요가 없어지지요.
그런 조건을 if문으로 거릅니다.
int r=shapes[next].length;
int c=shapes[next][0].length;
if(y+r>n||x+c>m) continue;
범위 안에 있다면 이제 더해주면 됩니다. 우리가 블록이 있는 경우에는 1을 저장했었죠? 블록이 없는 경우는 0을 저장했었습니다. 그래서 판의 숫자에 이 이차원 배열을 단지 곱해주면 됩니다. 이 값을 모두 더하는 것이죠.
sum+=map[i][j]*shapes[next][i-y][j-x];
이제 모든 판의 좌표를 돌면서 가장 큰 값을 구하면 그게 답이 되는 겁니다. 전체 코드는 아래에 있습니다.
import java.util.Scanner;
public class Main {
static int n,m;
static int [][]map;
static int [][][]shapes={
{{1,1,1,1}},{{1},{1},{1},{1}},
{{0,1,0},{1,1,1}},{{1,1,1},{0,1,0}},{{0,1},{1,1},{0,1}},{{1,0},{1,1},{1,0}},
{{1,1,1},{1,0,0}},{{0,0,1},{1,1,1}},{{1,1},{0,1},{0,1}},{{1,0},{1,0},{1,1}},
{{1,1,1},{0,0,1}},{{1,0,0},{1,1,1}},{{0,1},{0,1},{1,1}},{{1,1},{1,0},{1,0}},
{{1,1},{1,1}},
{{1,0},{1,1},{0,1}},{{0,1,1},{1,1,0}},
{{0,1},{1,1},{1,0}},{{1,1,0},{0,1,1}}
};
public static void main(String[] ar){
Scanner in=new Scanner(System.in);
n=in.nextInt(); m=in.nextInt();
map=new int[n][m];
for(int i=0;i<n;i++) for(int j=0;j<m;j++)
map[i][j]=in.nextInt();
int max=0;
for(int i=0;i<n;i++) for(int j=0;j<m;j++)
max=Math.max(maxValue(i,j), max);
System.out.println(max);
}
static int maxValue(int y,int x){
int max=0;
for(int next=0;next<19;next++){
int r=shapes[next].length;
int c=shapes[next][0].length;
if(y+r>n||x+c>m) continue;
int sum=0;
for(int i=y;i<y+r;i++) for(int j=x;j<x+c;j++)
sum+=map[i][j]*shapes[next][i-y][j-x];
max=Math.max(max, sum);
}
return max;
}
}
