이 포스트에서는 프로그래밍 사이트 백준 Online Judge의 Solved.ac 기준 난이도 Silver II에 해당하는 문제인 1260번 : DFS와 BFS, 11047번 : 동전 0, 1929번 : 소수 구하기를 풀이하도록 하겠습니다.
1260번 : DFS와 BFS
문제 이름 그대로 DFS와 BFS를 구현하는 문제입니다.
DFS는 Depth First Search의 약자로써 깊이 우선 탐색을 의미하고, 이동할 수 있는 노드로 최대한 깊게 이동하며 탐색하는 방법입니다.
BFS는 Breadth First Search의 약자로써 너비 우선 탐색을 의미하고, 이동할 수 있는 노드를 먼저 한 번씩 방문한 뒤 더 이상 인접한 노드가 없으면 그제서야 인접한 노드로 이동해서 탐색하는 방법입니다.
#include<stdio.h>
int N, graph[1001][1001] = {0, }, visit[1001] = {0, }, queue[1001];
void dfs(int V) {
visit[V] = 1;
printf("%d ", V);
for(int i=1; i<=N; i++) if(graph[V][i] && !visit[i]) dfs(i);
}
void bfs(int V) {
int front = 0, rear = 1, pop;
visit[V] = 1;
printf("%d ", V);
queue[0] = V;
while(front < rear) {
pop = queue[front++];
for(int i=1; i<=N; i++)
if(graph[pop][i] && !visit[i]) {
visit[i] = 1;
printf("%d ", i);
queue[rear++] = i;
}
}
}
int main() {
int M, V, x, y;
scanf("%d %d %d", &N, &M, &V);
for(int i=0; i<M; i++) {
scanf("%d %d", &x, &y);
graph[x][y] = 1;
graph[y][x] = 1;
}
visit[V] = 1;
dfs(V);
for(int i=1; i<=N; i++) visit[i] = 0;
visit[V] = 1;
printf("\n");
bfs(V);
}
dfs의 경우 재귀함수를 이용해서 visit이 표기되지 않은 노드로 끝까지 이동할 수 있습니다.
bfs의 경우 큐를 이용해서 rear쪽으로는 노드들이 발견되는 즉시 추가해주고, front쪽에서는 하나씩 pop을 해주면서 다음에 이동할 노드로 지정해줍니다.
dfs는 재귀함수, bfs는 큐를 이용한다는 특성만 알면 어렵지 않게 구현할 수 있습니다.
11047번 : 동전 0
동전이 N가지 종류가 있을 때, 가치의 합을 K로 만들기 위해 필요한 최소 동전의 수를 구하는 문제입니다.
이러한 방식의 문제들은 모두 그리디 알고리즘 문제로, 가장 큰 것이나 작은 것부터 크기순으로 최대한 처리하면서 넘어가는 방식의 풀이가 필요합니다.
#include<stdio.h>
int main() {
int N, K, coin[11], count = 0;
scanf("%d %d", &N, &K);
for(int i=1; i<=N; i++) scanf("%d", &coin[i]);
for(int i=N; i>0; i--) {
while(K > 0) {
K -= coin[i];
count++;
}
if(K < 0) {
K += coin[i];
count--;
}
}
printf("%d", count);
}
이 문제의 경우에는 금액이 가장 큰 동전부터 사용해나가면서 최대한 적은 수의 동전으로 금액을 모두 채울 수 있게 하는 것이 포인트입니다.
다만 동전 금액만큼 뺐는데 K 값을 초과할 수 있으므로 그럴 때는 count를 다시 1 차감하고 동전 금액만큼을 다시 더해주는 연산을 취해주면 됩니다.
변수 범위가 크지 않아서 반복문을 이중으로 사용해도 제한 시간을 넘어가지 않습니다.
1929번 : 소수 구하기
문제가 단순한데 정답률을 보니 쉽지 않아 보이는 문제입니다.
M 이상 N 이하의 소수를 모두 출력하는 문제로, 시간 제한이 엄격할 것으로 보입니다.
#include<stdio.h>
int main() {
int M, N, check;
scanf("%d %d", &M, &N);
for(int i=M; i<=N; i++) {
check = 1;
for(int j=2; j*j<=i; j++) if(i%j == 0) check = 0;
if(check) printf("%d\n", i);
}
}
처음에는 위의 방법(접은 글의 코드)으로 시도했는데 더 빠른 시간 안에 해결해야 함을 알게 되었습니다.
그래서 결국 어쩔 수 없이 에라토스테네스의 체를 이용해야 했습니다.
문제 조건을 잘 보면 N의 최댓값이 100만이기 때문에 각 수에 대응되는 배열을 만들 수 있습니다.
그래서 배열을 선언해서 에라토스테네스의 체를 이용해 풀이해보도록 하겠습니다.
#include<stdio.h>
int arr[1000005] = {1, 1, };
int main() {
int M, N;
scanf("%d %d", &M, &N);
for(int i=2; i*i<=N; i++)
for(int j=2; i*j<=N; j++) arr[i*j] = 1;
for(int i=M; i<=N; i++) if(!arr[i]) printf("%d\n", i);
}
위와 같이 주어진 수의 약수를 발견할 때마다 그 약수의 배수들을 모두 지워버림으로써 소수만 빠르게 남기는 방법을 에라토스테네스의 체라고 합니다.
이 방법을 이용하면 소수만 찾아내는 과정을 빠른 시간 안에 수행할 수 있습니다.
다만 배열을 이용하기 때문에 예를 들어 수의 범위가 1000만을 넘어가면 사용하기가 힘들어진다는 특징이 있습니다.