들어가기에 앞서
이번 주는 순열과 조합 관련 알고리즘 문제들을 풀었다. 그리고 브루트포스 알고리즘 쪽 문제도 풀었다. 완전 탐색이다보니 아이디어만 잘 떠올린다면 큰 어려움은 없었던 것 같다!
스터디 진행하면서 아이디어를 공유하다보니, 내가 특이하게 푼 부분도 보이고 조금 지적받은 부분도 있어 공유하여 본다.
백준 5568
카드를 뽑는데 순서가 중요하기 때문에 순열을 구현하여야한다.
카드를 k장 뽑기까지 어떤 숫자들을 뽑았는지 배열에 담아두고, k장 뽑는게 완료되면 현재 뽑은 숫자들을 이용해 숫자를 만든다.
예를 들어, 1, 2, 3을 뽑았다면 1 + 20 + 300과 같이 조합할 수 있다. 자릿 수가 증가하는 것을 따져야한다.
문제는 두 자릿수가 존재한다는 것이다. 따라서 뽑은 숫자 중에 두 자릿수가 있다면 위의 그림에서와 같이 자릿수를 +2 올리면 된다.
예를 들어, 1, 12, 3을 뽑았다면 1 + 120 + 3000과 같이 숫자를 조합할 수 있다.
숫자의 조합이 완료되면 만들어진 숫자들을 저장하는 배열에 저장한다. 이 때, 지금 만들어진 숫자가 이미 배열에 들어가있다면 넣지 않는다.
코드는 아래와 같다.
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int n, k;
int num[10];
bool visit[10] = { false, };
vector<int> per;
vector<int> numbers;
void permutation(int depth) {
if (depth == k) {
int number = 0;
int cnt = 0;
for (int i = 0; i < per.size(); i++) {
number += (per[i] * (int)pow(10, cnt));
if (per[i] > 9)
cnt += 2;
else
cnt++;
}
if (find(numbers.begin(), numbers.end(), number) == numbers.end())
numbers.push_back(number);
}
else {
for (int i = 0; i < n; i++) {
if (!visit[i]) {
visit[i] = true;
per.push_back(num[i]);
permutation(depth + 1);
visit[i] = false;
per.pop_back();
}
}
}
}
int main() {
cin >> n;
cin >> k;
for (int i = 0; i < n; i++) {
cin >> num[i];
}
permutation(0);
cout << numbers.size() << '\n';
return 0;
}백준 12101
특정 숫자를 1, 2, 3을 더하여 만들고, 사전 순으로 정렬한 뒤, i번째에 있는 조합을 출력한다.
뽑았던 카드를 또 뽑을 수 있고, 순서가 있으므로 중복 순열로 생각할 수 있다.
원리는 그림에서 설명이 다 되어있다!!
코드는 아래와 같다.
#include <iostream>
#include <vector>
using namespace std;
int n, k;
vector<int> per;
vector<vector<int>> answer;
void permutation(int sum) {
if (sum == n) {
answer.push_back(per);
}
else {
for (int i = 1; i < 4; i++) {
if (sum + i <= n) {
per.push_back(i);
permutation(sum + i);
per.pop_back();
}
}
}
}
int main() {
cin >> n >> k;
permutation(0);
int cnt = answer.size();
if (k - 1 < cnt) {
int arr_size = answer[k - 1].size();
for (int i = 0; i < arr_size - 1; i++) {
cout << answer[k - 1][i] << "+";
}
cout << answer[k - 1][arr_size - 1] << "\n";
}
else {
cout << -1 << '\n';
}
return 0;
}백준 5639
이 문제가 조금 어려웠다. 먼저 나는 이진트리를 만들어야지만 후순위 출력을 할 수 있을 것이라고 생각했다.
처음에 조금 문제가 있었던게, 노드가 최대 10000개 주어진다고 하길래, 배열이 10000개만큼 있으면 이진트리를 표현할 수 있겠다고 생각했는데, 사실 트리의 레벨당 하나의 노드만 존재하는 형태로 노드가 10000개 있으면 트리의 레벨이 10000까지 가므로 총 노드 수는 2^10000-1개가 된다. 즉, 이렇게는 구현할 수 없다.
다음으로 생각한 것은 특정 노드의 키 값이 어떤 노드를 자식으로 가지고 있는지를 저장하고 있으면 되겠다고 생각하였다. 노드의 최대 키 값이 10^6이므로 배열을 10^6 x 2 사이즈로 생성한다. 왜 x2가 필요하냐면 0번째는 왼쪽 자식 1번째는 오른쪽 자식을 표현하기 위해서이 다.
그림에서와 같이 2가 1과 3 노드와 연결을 가질 때 Arr[2] = <1, 3>의 값을 가지고 있으면 된다.
입력으로 주어진 제일 첫번째 수가 트리의 루트이므로 루트를 표시해두고 이진트리를 생성해 나간다. 입력되는 키는 루트를 기준으로 왼쪽 또는 오른쪽에 위치할 수 있다.
그런데 이미 루트의 왼쪽에 자식이 존재한다면, 이제 자식과 비교를 하여 자식의 왼쪽 자식인지 오른쪽 자식인지를 따지는 식으로 자신의 자리를 찾아나가게 된다.
예를 들어, arr[2] = <1, 3>인 상황에서 4가 입력으로 들어온다면
루트인 2를 기준으로 루트보다 크므로 오른쪽 자식자리에 위치해야하는데, 이미 오른쪽 자식이 존재하기 때문에, 오른쪽 자식인 3과 비교를 시작한다.
오른쪽 자식 3보다 입력된 4는 크기 때문에 오른쪽 자식 자리에 위치할 수 있는데, 3의 오른쪽 자식은 존재하지 않기 때문에 4는 3의 오른쪽 자식이 된다. 따라서 arr[3] = <0, 4>의 형태로 저장이 될 것이다.
이와 같은 방식으로 입력된 모든 노드를 트리로 바꾼다.
트리가 완성되면 DFS를 이용해서 왼쪽 자식, 오른쪽 자식 탐색 후 루트를 출력하는 식으로 후 순위 출력 결과를 완성하게 된다.
코드는 다음과 같다.
#include <iostream>
#include <vector>
using namespace std;
int tree[1000000][2] = { 0, };
int root;
void make_tree(int ip, int head) {
int lchild = tree[head][0];
int rchild = tree[head][1];
// head를 루트로 하는 서브트리에서 input이 헤드보다 작고, 헤드 노드의 왼쪽 자식이 없는 경우
if (ip < head && lchild == 0)
tree[head][0] = ip;
// head를 루트로 하는 서브트리에서 input이 헤드보다 크고, 헤드 노드의 오른쪽 자식이 없는 경우
else if (ip > head && rchild == 0)
tree[head][1] = ip;
// head를 루트로 하는 서브트리에서 input이 헤드보다 작은 경우, 왼쪽 자식 노드를 루트로 하는 서브트리로 이동
else if (ip < head)
make_tree(ip, lchild);
// head를 루트로 하는 서브트리에서 input이 헤드보다 큰 경우, 오른쪽 자식 노드를 루트로 하는 서브트리로 이동
else if (ip > head)
make_tree(ip, rchild);
}
void post_order(int head) {
int lchild = tree[head][0];
int rchild = tree[head][1];
if (lchild > 0)
post_order(lchild);
if (rchild > 0)
post_order(rchild);
cout << head << "\n";
}
int main() {
int input;
int head;
cin >> root;
head = root;
while (cin >> input) {
make_tree(input, root);
}
post_order(root);
return 0;
}이 풀이의 경우 배열을 많이 많이 만들어야하므로 메모리를 많이 잡아먹는다.
더 좋은 풀이가 있는데, 바로 입력받은 정보를 토대로 바로 후순위 출력을 할 수 있다.
이런 생각은 어떻게 떠올리는지 모르겠다...
일단 이진트리부터 만들려고 생각한 나 반성해!!!
백준 18428
오히려 이 문제는 골드5급의 문제임에도 불구하고 아주 손쉽게 풀 수 있었다.
입력받을 때, 선생님, 학생, 그리고 빈 공간의 좌표를 저장해둔다.
빈공간에 장애물을 설치한다. 이 때 순서는 상관없으므로 결국 조합이 된다.
장애물 설치가 완료되면 학생이 숨을 수 있는지 확인한다.
학생이 숨을 수 있으려면 학생을 기준으로 상하좌우 탐색을 할 때, 선생님보다 장애물을 먼저 마주치거나 아예 복도 끝에 도달하면 된다.
모든 학생이 숨을 수 있으면 YES를 출력한다.
단순히, 조합만 잘 떠올릴 수 있다면 쉽게 풀 수 있는 문제였다. 복도의 사이즈도 작았기 때문에 전부 다 설치하면 되겠네라고 바로 떠올릴 수 있었던 것 같다.
코드는 아래와 같다.
#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;
int N;
char map[6][6];
vector<pair<int, int>> space;
vector<pair<int, int>> students;
vector<pair<int, int>> teachers;
vector<int> comb;
bool answer = false;
bool check_hide(int x, int y) {
bool check = true;
// 학생 기준 좌측 탐색
for (int i = y - 1; i >= 0; i--) {
if (map[x][i] == 'O') {
break;
}
else if (map[x][i] == 'T') {
check = false;
break;
}
}
if (check == false)
return false;
// 학생 기준 우측 탐색
for (int i = y + 1; i < N; i++) {
if (map[x][i] == 'O') {
break;
}
else if (map[x][i] == 'T') {
check = false;
break;
}
}
if (check == false)
return false;
// 학생 기준 상단 탐색
for (int i = x - 1; i >= 0; i--) {
if (map[i][y] == 'O')
break;
if (map[i][y] == 'T') {
check = false;
break;
}
}
if (check == false)
return false;
// 학생 기준 하단 탐색
for (int i = x + 1; i < N; i++) {
if (map[i][y] == 'O')
break;
if (map[i][y] == 'T') {
check = false;
break;
}
}
if (check == false)
return false;
return true;
}
void check() {
int cnt = 0;
for (int i = 0; i < students.size(); i++) {
int sx = students[i].first;
int sy = students[i].second;
bool hide = check_hide(sx, sy);
if (hide == true)
cnt++;
}
if (cnt == students.size())
answer = true;
}
void combination(int pos, int depth) {
if (depth == 3) {
// 선생님과 장애물을 설치하고, 학생들이 다 숨을 수 있는지 체크
memset(map, 'X', sizeof(map));
for (int i = 0; i < teachers.size(); i++) {
map[teachers[i].first][teachers[i].second] = 'T';
}
for (int i = 0; i < comb.size(); i++) {
map[space[comb[i]].first][space[comb[i]].second] = 'O';
}
check();
}
else {
for (int i = pos; i < space.size(); i++) {
comb.push_back(i);
combination(i + 1, depth + 1);
comb.pop_back();
}
}
}
int main() {
cin >> N;
char input;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> input;
if (input == 'X')
space.push_back(make_pair(i, j));
else if (input == 'S')
students.push_back(make_pair(i, j));
else
teachers.push_back(make_pair(i, j));
}
}
combination(0, 0);
if (answer)
cout << "YES" << '\n';
else
cout << "NO" << '\n';
return 0;
}이 코드의 아쉬운 점은 장애물을 설치하고 학생이 숨을 수 있는지 보다는 선생님의 눈에 학생이 들어오는지를 탐색하면 더 좋았을 것 같다. 왜냐하면 문제의 조건 상 학생의 수는 30명까지인데 선생님의 수는 5명까지이므로 선생님이 학생들을 볼 수 있는지 없는지를 탐색하는 것이 더 효과적이다!!
소감
확실히 다양한 생각들을 스터디를 통해 듣다보니, 시야가 넓어지는 것 같았다.
그리고 아이디어 피드백이나 코드 피드백도 주고받으니까 반성의 시간을 잠깐 가질 수 있었다??
한 분은 깃에 코드를 올릴 때도 주차별로 이슈를 열고, 발표 및 피드백 이후에 이슈를 종료하고 해당 주차를 메인 브랜치에 병합하는 식으로 계획하고 있다고 했다.
나도 4주차 스터디에서는 그런 식으로 진행해보려고 한다. 아직 깃을 잘 쓰지는 못하기 때문에 이런 식으로 관리할 수 있다는 것을 배워가는 것 같다 ㅎㅎ
