- A가 B를 신뢰한다. => B를 해킹하면 A도 해킹할 수 있다. / A를 해킹하면 B는 해킹할 수 없다.
- M개의 A B 쌍이 주어지며, A가 B를 신뢰한다.
- 한 번에 가장 많은 컴퓨터를 해킹 할 수 있는 컴퓨터의 번호를 오름차순 출력
2. 접근방법
- 단뱡향 그래프
- 신뢰관계에 대해 int 더블배열을 쓰면 4 * 10,000 * 10,000 = 400,000,000byte = 400Mbyte로 메모리 초과
=> 더블 벡터로 입력 받음
- 하나의 컴퓨터에서 해킹 할 수 있는 모든 컴퓨터를 찾는다.
- 한 정점에서 시작하여 다시 그 정점을 방문하면 안되므로 체크 배열을 쓴다.
3. 시간복잡도
- 모든 정점의 갯수 N * 최대 쌍의 갯수 M = O(NM)
- NM = 10억 인데 5초 안에 들어오려나...3.8초 나옴
- SCC 라는 알고리즘을 쓰면 더 빨리 돌릴 수 있다는데 나중에 공부해야지
4. 회고
- 중간에 dp 처럼 아에 한번 방문한 정점은 다시는 방문하지 않아도 되지 않을까 해서 그렇게 했는데
이렇게 하면 체크가 없어서 그래프가 싸이클을 만들면 무한루프로 빠져들어감......
=> 그래프에서는 싸이클을 생각해보자
- 한 정점(1 번)에서 시작해서 방문했던 정점을 재 방문 하는 경우(1 -> 2 -> 1)만 막아야지
새로운 다른 정점(2 번)에서 시작해서 이전 정점에서 방문했던 정점(1 번에서 방문했던 정점들) 방문을 막으면 안됨
쌍방 연결이나, 한 노드를 여러 노드가 방문할 수 있기 때문
=> 체크 배열 초기화 !!!!!!!
- 컴퓨터의 번호는 1 부터 시작하므로 배열의 크기는 n + 1 !!!!!!!!!
for문 인덱스도 1 !!!!!!!
소스코드
#include<iostream>
#include<vector>
using namespace std;
int n, m;
int nodeNum[10001];
bool check[10001];
vector<vector<int> > tree;
int max(int a, int b){
return ((a > b) ? a : b);
}
int dfs(int node){
check[node] = true;
int ret = 0;
for (int i = 0; i < (int)tree[node].size(); i++)
if (!check[tree[node][i]])
ret += dfs(tree[node][i]) + 1;
return ret;
}
int main(void){
cin >> n >> m;
tree.resize(n + 1);
int a, b;
for (int i = 0; i < m; i++){
cin >> a >> b;
tree[b].push_back(a);
}
int maxV = 0;
for (int i = 1; i <= n; i++){
nodeNum[i] = dfs(i);
maxV = max(maxV, nodeNum[i]);
for (int j = 0; j <= n; j++)
check[j] = false;
}
for (int i = 1; i <= n; i++)
if (nodeNum[i] == maxV) cout << i << " ";
cout << "\n";
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
a[집 갯수] = 단지 갯수
for(int i = 0; i < n*n + 1; i++){
for(int j = 0; j < a[i]; j++){
cout << i << "\n";
}
}
18.2.7
소스코드 수정 - num이 필요없잖아.. 벡터를 쓰는데
dfs만 수정함
소스코드 : dfs
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<int> house;
char map[25][25];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int dfs(int row, int col){
map[row][col] = '0';
int ret = 1, nr, nc;
for (int i = 0; i < 4; i++){
nr = row + dx[i];
nc = col + dy[i];
if (0 <= nr && nr < n && 0 <= nc && nc < n && map[nr][nc] == '1')
ret += dfs(nr, nc);
}
return ret;
}
int main(void){
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> map[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (map[i][j] == '1')
house.push_back(dfs(i, j));
sort(house.begin(), house.end());
cout << house.size() << "\n";
for (int i = 0; i < house.size(); i++)
cout << house.at(i) << "\n";
return 0;
}
소스코드 : bfs
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int n, check[25][25];
char map[25][25];
vector<int> house;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int main(void){
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> map[i][j];
queue<pair<int, int>> q;
int num = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
int cnt = 0;
if (!check[i][j] && map[i][j] == '1'){
q.push(make_pair(i, j));
check[i][j] = true;
num++; cnt++;
while (!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
int nx, ny;
for (int k = 0; k < 4; k++){
nx = x + dx[k];
ny = y + dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n
&& !check[nx][ny] && map[nx][ny] == '1'){
check[nx][ny] = true;
cnt++;
q.push(make_pair(nx, ny));
}
}
}
house.push_back(cnt);
}
}
}
sort(house.begin(), house.end());
cout << num << "\n";
for (int i = 0; i < house.size(); i++)
cout << house.at(i) << "\n";
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
- 어떤 자연수 M => 세 자릿수 라면 100a + 10b + c => M + a + b + c = N 즉, M과 각 자릿수의 합을 분해합, M을 생성자, N을 분해합
- 1 <= N <= 1,000,000 인 자연수 N이 주어 졌을 때 가장 작은 생성자는?
2. 접근방법
- 생성자는 분해합을 넘을 수 없으므로 1 부터 N-1 까지의 모든 수를 다 해보자
- 좀 더 생각해보면 분해합 N이 만들어 질 수 있는 생성자의 최대 자릿수는 6자릿수
(생성자가 1,000,000 이면 분해합은 1,000,001 이므로 7 자릿수는 나올 수 없음)
각 자릿수의 최대 값은 9
즉, 생성자는 분해합 보다 54 이상 작을 수 없음.
N-54 부터 N-1 까지만 찾으면 됨.
가장 작은 수 부터 찾을 거니 처음 만나는 생성자가 최소값
3. 시간복잡도
- 두 가지 경우 모두 N
- 당연히 실제 시간은 전체 검색시 8ms / 55개 검사시 0ms
4. 회고
- 처음엔 다 했는데...
- 다른 사람의 소스 코드를 보고 깨달음
- 각 자릿수 합의 최대 범위
소스코드
#include<iostream>
using namespace std;
int main(void){
int n;
cin >> n;
for (int i = n - 54; i < n; i++){
int temp = i, sum = i;
while (temp){
sum += temp % 10;
temp /= 10;
}
if (sum == n){
cout << i << "\n";
return 0;
}
}
cout << '0' << "\n";
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
- 배열을 큐처럼 만들어서 출력 대상이 아니면 배열 뒤에 붙이는 방식인 경우 최소 100 * 101 / 2 = 5050 이상 사이즈가 필요
- 인덱스만 가지고 움직인다면 배열 사이즈는 N이면 됨
출력한 놈을 다시 출력하는 논리적 오류가 발생
이런거 신경 안쓸려면 index를 출력한놈은 건너 뛰게 만들어야함
- 문서 번호와 문서 중요도를 보관해야 함
- 배열로 구현 했을 때 한칸씩 당기지 않으면 출력 했는지 안했는지 체크가 필요
- Queue 자료구조를 쓴다면 front를 뺄 때, 다른 자료와의 중요도를 비교할 수 있는 수단이 필요함
하나씩 빼서 비교하던가 아니면 Priority_Queue나 중요도를 저장하고 있는 다른 배열과 비교가 필요
소스코드 : N^3
#include<iostream>
using namespace std;
int main(void){
int t;
cin >> t;
while (t--){
int n, m, q[101], check[101] = { 0 };
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> q[i];
int index = 0, cnt = 1;
while (cnt <= n){
if (index == n) index = 0;
int i = 0;
for (; i < n; i++){
if (!check[i] && q[index] < q[i])
break;
}
// !check[index]가 없다면 출력한 놈을 다시 출력하게 함
// 예제에서 정답은 맞아도 중간 값이 틀림 => 결국은 틀림
if (!check[index] && i == n){
check[index] = cnt;
cnt++;
}
index++;
}
cout << check[m] << "\n";
}
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
- 1번 몸무게 > 2번 몸무게 && 1번 키 > 2번 키 이면 1번이 2번 보다 덩치가 크다
- 나의 덩치 순위는 나보다 덩치큰 사람 + 1
- 2 ≤ n ≤ 50, 10 ≤ 몸무게, 키 ≤ 200
2. 접근방법
- 브루트 포스
- 한명을 기준으로 나머지(n-1)명의 덩치를 비교
3. 시간복잡도
- 한명을 기준으로 나머지(n-1)명의 덩치를 비교 : n-1
- 총 n명 이므로 : n * (n - 1) ≒ 2500
4. 회고
- 할게 없음
소스코드
#include<iostream>
using namespace std;
int n, h[51][2];
int main(void){
cin >> n;
for (int i = 0; i < n; i++)
cin >> h[i][0] >> h[i][1];
for (int i = 0; i < n; i++){
int cnt = 1;
for (int j = 0; j < n; j++){
// i == j인 경우는 몸무게와 키가 같기 때문에 등수에 영향이 없음
if (h[i][0] < h[j][0] && h[i][1] < h[j][1])
cnt++;
}
cout << cnt << " ";
}
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
#include<iostream>
using namespace std;
int K, S[14], P[6];
void dfs(int index, int in, int size){
if (size == 6){
for (int i = 0; i < 6; i++)
cout << P[i] << " ";
cout << "\n";
return;
}
for (int i = index; i < K; i++){
P[in] = S[i];
dfs(i + 1, in + 1, size + 1);
}
}
int main(void){
freopen("Text.txt", "r", stdin);
while ((cin >> K) && K != 0){
for (int i = 0; i < K; i++)
cin >> S[i];
dfs(0, 0, 0);
cout << "\n";
}
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
