1. 스타트/링크 축구
https://www.acmicpc.net/problem/14889
구현
- N명을 /2를 하여 축구팀을 짜는데, 각 인원은 다른 인원이 있을때 파워가 증가한다.
- 따라서 팀끼리 파워가 최대한 비슷하게 뽑는게 목표.
- NM문제처럼 팀원을 무작위로 뽑은 뒤,
반씩 갈라서 arr의 합들을 구하고 차를 비교하려고 하였다.- 하지만 안된다. 시간복잡도를 매우 줄여야만 했다.
- N/2까지만 구한다. 그렇게 되면, 나머지로 팀을 짜면 된다.
그 나머지 인지 아닌지는 visited를 통해서 false로 알 수 있다.- int num을 사용하여 순서가 바뀐 수열을 무시한다.
1234던지 4213이던지 같은 팀이 맞기 때문에, 해당 경우를 제거.
문제점
1. 브루트포스에 N=20이라 시간복잡도가 널널할 줄 알았는데,
생각보다 최대한 경우의 수를 줄여야만 풀 수 있었다.
2. 추가로 for문으로 index를 접근하는 부분에서 헷갈릴만 할 것 같다.
지금은 안 헷갈림
#include <iostream>
#include <vector>
using namespace std;
int N;
bool visited[21];
int arr[21][21];
vector<int> v;
int result=987654321;
void DFS(int num)
{
if(v.size()==N/2)
{
// v속 원소의 값은 상관이 없다. visited만 체크
int s_result=0, l_result=0;
for(int i=1;i<=N;i++)
{
for(int j=1; j<=N;j++)
{
if(visited[i]==true&&visited[j]==true)
{
s_result += arr[i][j];
}
if(visited[i]==false&&visited[j]==false)
{
l_result += arr[i][j];
}
}
}
result = min(result, abs(s_result-l_result));
}
else
{
for(int i=num;i<=N;i++) // num~N까지로 수정
{
if(!visited[i])
{
visited[i] = true;
v.push_back(i);
DFS(i);
v.pop_back();
visited[i] = false;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
cin >> arr[i][j];
}
}
DFS(1); // 시작이 1이어야 함
cout << result;
return 0;
}2. 스타트/링크 축구 +
https://www.acmicpc.net/problem/15661
구현
- 기존 스타트/링크 축구 문제에서
이번에는 N이 반드시 짝수도 아니고, 팀도 정확히 반이 아니어도 된다.- 따라서 팀을 정할 때마다, result를 체크해야만 한다.
- 그러기 위해선 else문을 제거해야만 한다. (주석참고)
- 추가로 시간복잡도를 더 줄이기 위해서 아래 구문을 추가했다.
if(v.size()>N/2) return;
주석참고.
문제점
1. 시간복잡도를 줄일 수 있는 방법이 더 있다.
DFS(i)이렇게 넣을 때, i대신, i+1을 넣으면 된다.- v.size()가 1인 경우는 어떠한 시너지도 받을 수 없다.
따라서 1명인 팀인 경우에 무조건 합은 0이고, N은 4이상이고, 시너지는 1보다 크기 때문에,
v.size()가 1인 경우는 무시해도 상관없다.고 생각했는데
왜 안되는 걸까?
1/3인 경우가 2/2인 경우보다 시너지 차가 작은 경우가 존재하는건가?
#include <iostream>
#include <vector>
using namespace std;
int N;
bool visited[21];
int arr[21][21];
vector<int> v;
int result=987654321;
void DFS(int num)
{
// N/2이상을 비교할 필요가 없는게, 한쪽을 구하면 나머지가 정해지기 때문.
// 그러니까 12/3 인 경우와, 3/12 인 경우가 같아서 구하는게 의미없다.
if(v.size()>N/2)
{
return;
}
if(v.size()>=1)
{
// v 속 원소의 값은 상관이 없다. visited만 체크
int s_result=0, l_result=0;
for(int i=1;i<=N;i++)
{
for(int j=1; j<=N;j++)
{
if(visited[i]==true&&visited[j]==true)
{
s_result += arr[i][j];
}
if(visited[i]==false&&visited[j]==false)
{
l_result += arr[i][j];
}
}
}
//cout << s_result << " : " << l_result <<"\n";
result = min(result, abs(s_result-l_result));
}
//else // 이게 존재한다면, if문을 끝으로 result를 구하고 DFS가 return되어
// 다음 원소를 추가하지 않았을 것이다.
{
for(int i=num;i<=N;i++) // num~N까지로 수정
{
if(!visited[i])
{
visited[i] = true;
v.push_back(i);
DFS(i);
v.pop_back();
visited[i] = false;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
cin >> arr[i][j];
}
}
DFS(1); // 시작이 1이어야 함
cout << result;
return 0;
}3. 부등호
https://www.acmicpc.net/problem/2529
구현
- 부등호에 따라
다음 수에 더 큰 수를 고를지, 작은 수를 고를지 정하면 되었다.- 문제가 되는 부분은 비교와 출력부분이었다.
- stoi를 사용했더니 문제 / stoll을 사용하니 해결
(그냥 무조건 왠만하면 long long을 사용하자)- 그리고 출력도 숫자로 하기보다 string으로 만들어서 하는게
맨 앞의 0도 출력해야하기 때문에 더 편할 것이라고 판단해서 사용하였다.
문제점
- int는 문제가 많이 된다. long long 사용하자.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int N;
char sim[12] = {0, };
bool visited[12];
vector<char> v;
string max_num="0", min_num="90000000000";
void DFS(int n, int num)
{
if(v.size()==N+1)
{
string s;
for(int i=0;i<v.size();i++)
{
s+=v[i];
}
//cout << "String is : " << s << "\n";
if(stoll(max_num) < stoll(s))
{
max_num = s;
}
if(stoll(min_num) > stoll(s))
{
min_num = s;
}
}
else
{
if(sim[n]=='<')
{
for(int i=num;i<10;i++)
{
if(!visited[i])
{
visited[i] = true;
v.push_back(i + '0');
DFS(n+1, i);
v.pop_back();
visited[i] = false;
}
}
}
else if(sim[n]=='>')
{
for(int i=num;i>=0;i--)
{
if(!visited[i])
{
visited[i] = true;
v.push_back(i + '0');
DFS(n+1, i);
v.pop_back();
visited[i] = false;
}
}
}
else // 시작
{
for(int i=num;i<10;i++)
{
if(!visited[i])
{
visited[i] = true;
v.push_back(i + '0');
DFS(n+1, i);
v.pop_back();
visited[i] = false;
}
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for(int i=1;i<=N;i++)
{
cin >> sim[i];
}
DFS(0,0);
cout << max_num << "\n" << min_num;
return 0;
}4. 집합
https://www.acmicpc.net/problem/11723
구현
- 집합을 구현하는 게 맞긴 한데,
CPP STL의 Set처럼 자동정렬 되지도 않고,
살짝 하위호환 집합 느낌이었다.- 그냥 bool S[]를 사용하여, 해당 원소가 있는지 확인하고,
중복안되게 작업만 하면 끝.
#include <iostream>
using namespace std;
int idx = 0;
bool S[21]={0,};
void add(int n)
{
if(!S[n])
{
S[n] = true;
}
}
void remove(int n)
{
if(S[n])
{
S[n] = false;
}
}
void check(int n)
{
if(S[n])
{
cout << "1\n";
}
else
{
cout << "0\n";
}
}
void toggle(int n)
{
if(S[n])
{
S[n] = false;
}
else
{
S[n] = true;
}
}
void all()
{
for(int i=1;i<=20;i++)
{
S[i] = true;
}
}
void empty()
{
for(int i=1;i<=20;i++)
{
S[i] = false;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--)
{
string s;
cin >> s;
if (s == "add")
{
int n;
cin >> n;
add(n);
}
else if (s == "remove")
{
int n;
cin >> n;
remove(n);
}
else if (s == "check")
{
int n;
cin >> n;
check(n);
}
else if (s == "toggle")
{
int n;
cin >> n;
toggle(n);
}
else if (s == "all")
{
all();
}
else if (s == "empty")
{
empty();
}
}
return 0;
}5. 부분 수열 합
https://www.acmicpc.net/problem/1182
구현
- 주어진 수열에서 주어진 합을 만드는 경우의 개수를 찾는 문제.
- NM문제에 else를 주석처리하면 되는 문제.
- size()>=1이면 바로 result를 비교한다.
- 다시한번 보자면, N이 20이하기 때문에 NM방식을 사용가능
문제점
- v의 값을 그대로 사용하지 말 것.
#include <iostream>
#include <vector>
using namespace std;
int answer=0;
int N, S;
int arr[21];
bool visited[21] = {0, };
vector<int> v;
void DFS(int num)
{
if(v.size()>=1)
{
int result = 0;
for(int i=0;i<v.size();i++)
{
result += arr[v[i]];
}
if(result == S)
{
answer++;
}
}
//else
{
for(int i=num;i<N;i++)
{
if(!visited[i])
{
visited[i] = true;
v.push_back(i);
DFS(i);
v.pop_back();
visited[i] = false;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> S;
for(int i=0;i<N;i++)
{
cin >> arr[i];
}
DFS(0);
cout << answer;
return 0;
}6. 트리 순회
https://www.acmicpc.net/problem/1991
구현
- 출력하는 순서만 바꾸어 전위, 중위, 후위 순회를 구현하였다.
map<char, pair<char, char>> tree를 이용하여
본인과, 자식 2개를 가지도록 구성하였다.- 배열을 이용한다면,
루트 노드 인덱스 = 0 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 2
문제점
1. 그냥 암기 ㄱ
#include <iostream>
#include <map>
using namespace std;
int N;
char leftChild, node, rightChild;
map<char, pair<char, char>> tree;
void preorder(char node) {
cout << node;
if (tree[node].first != '.') {
preorder(tree[node].first);
}
if (tree[node].second != '.') {
preorder(tree[node].second);
}
}
void inorder(char node) {
if (tree[node].first != '.') {
inorder(tree[node].first);
}
cout << node;
if (tree[node].second != '.') {
inorder(tree[node].second);
}
}
void postorder(char node) {
if (tree[node].first != '.') {
postorder(tree[node].first);
}
if (tree[node].second != '.') {
postorder(tree[node].second);
}
cout << node;
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> node >> leftChild >> rightChild;
tree[node] = make_pair(leftChild, rightChild);
}
preorder('A');
cout << '\n';
inorder('A');
cout << '\n';
postorder('A');
}7. 트리의 부모 찾기
https://www.acmicpc.net/problem/11725
구현
- 이전에 BFS로 구현했었다.
- 주석 참고
문제점
1. BFS가 헷갈릴 때 쯤이다.
복습 다시 해보자.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
vector<int> connection[N + 1];
int visited[N + 1] = {
0,
};
int from, to;
for (int i = 0; i < N - 1; i++)
{
cin >> from;
cin >> to;
connection[from].push_back(to);
connection[to].push_back(from);
}
// BFS
queue<int> childNode;
childNode.push(1); // 1부터 시작
// 자식 노드를 타고 타고 돌면서, 본인으로 parent를 수정
// 1부터 시작해서 레벨당 판별하기 떄문에, connection이 자식 부모
// 상관없이 입력되었다고 해도, 항상 부모가 먼저 나오게 된다.
while (!childNode.empty())
{
int parent = childNode.front();
childNode.pop();
for(int i=0;i<connection[parent].size();i++) // 해당 노드와 연결된 노드 순회
{
int child = connection[parent][i]; // connection에서 parent->i인 것을 child로 둔다.
if(!visited[child])
{
visited[child] = parent; // visited[child]로 부모를 입력
childNode.push(child);
}
}
}
for (int i = 2; i < N + 1; i++) //2~N 인덱스
{
cout << visited[i] << "\n"; // 모든 부모를 출력
}
return 0;
}8. ABCDE 친구
https://www.acmicpc.net/problem/13023
BFS / DFS 날을 하루 잡자
Time Waits for No One