프로그래밍/알고리즘

    BOJ 4963 · 섬의 개수

    알고리즘 분류 : DFS 섬의 개수를 세는 문제다. 섬은 인접한 땅으로 이루어져 있고, 인접의 기준은 센터를 중심으로 8방향(상하좌우대각선)으로 한 칸씩 떨어진 곳이다. 4방향 인접 문제에서 방향만 추가해서 구현하면 된다. 비슷한 문제는 BOJ 2667번 '단지번호붙이기'이다. C++ 소스코드 #include #include int w, h; int a[51][51]; bool check[51][51]; const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0}; const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1}; void dfs(int x, int y) { check[x][y] = true; for (int i=0; i

    BOJ 1707 · 이분 그래프

    알고리즘 분류 : DFS DFS를 이용하여 이분 그래프인지 아닌지 확인할 수 있다. 이분 그래프(Bipartite graph)란, 인접한 노드는 서로 다른 색의 노드로 구분되고, 그래프 내의 모든 노드를 두 가지 색으로만 칠할 수 있는 그래프를 말한다. DFS 탐색을 통해 아직 방문하지 않은 노드(0)를 방문한다. 방문할 때 어떤 색인지 표시해둔다. 이 코드에서는 2개의 그룹으로 나눈다고 가정하고, 1과 -1의 그룹으로 구분했다.다음 노드는 현재 그룹 번호에 -1을 곱해서 1과 -1을 교차하여 그룹 짓도록 했다.만약 다음 노드가 이미 방문한 노드라면, 현재 노드의 그룹 번호와 다음 노드의 번호가 같은지 확인한다.번호가 같으면 인접한 노드가 같은 그룹이므로, false를 리턴한다.DFS 탐색이 끝날 때 까..

    BOJ 11724 · 연결 요소의 개수

    알고리즘 분류 : DFS DFS를 통해 연결 그래프의 개수를 확인하면 된다. 방문 여부를 저장하는 check 배열을 따로 만들고, N개의 노드 개수만큼 루프를 돌면서 방문하지 않은 곳에 DFS를 돌리면 된다. 처음 DFS를 호출할 때 카운트를 하면 연결 요소의 개수를 셀 수 있다. C++ 소스코드 #include #include using namespace std; int n, m; vector a[1001]; bool check[1001]; void dfs(int now) { check[now] = true; for (int i=0; i

    BOJ 2667 · 단지번호붙이기

    알고리즘 분류 : DFS, BFS DFS/BFS 완전 탐색을 하여 풀 수 있는 문제다. 연결 그래프의 개수를 세는 문제와 비슷하다. 단지는 서로 이어져있으므로, 인접한 집(1)이 있는지 DFS로 탐색한다.DFS로 탐색하면서 집의 수를 센 후, 값을 0으로 변경한다.0은 집이 없거나, 이미 방문한 곳이므로 다시 방문하지 않는다.DFS 탐색이 끝나면, 단지(인접한 집의 그룹)는 모두 0이 되어 있다.N x N 지도를 처음부터 끝까지 탐색하면서 아직 방문하지 않은 곳이 있다면, DFS로 다시 탐색한다.DFS를 처음 시작한 횟수가, 단지의 수이다.각 단지내 집의 수를 오름차 순으로 정렬해야 하므로, 이를 저장하는 배열을 따로 만들고 정렬하여 출력한다. C++ 소스코드 (DFS) #include #include ..

    BOJ 6588 · 골드바흐의 추측

    알고리즘 분류 : 수학 골드바흐의 추측(Goldbach's conjecture)이란, 2보다 큰 모든 짝수는 두 개의 소수의 합으로 나타낼 수 있다는 추측을 말한다.우선 2부터 1,000,000까지의 모든 소수를 에라토스테네스의 체로 구한다. 참조입력 N에 대하여 위에서 구한 소수를 2부터 순서대로 A라고 정한다.B = N-A인 소수가 존재하는지 확인하기 위해서, 위에서 구한 소수의 집합에서 확인한다.존재하면, N = A + B를 출력하고 마친다. 참고사항10^18 이하의 숫자에 대해서는 골드바흐의 추측이 참인 것이 보증되므로, "Goldbach's conjecture is wrong."을 출력할 필요는 없다.에라토스테네스의 체를 통해 구한 소수를 별도의 배열로 생성하여 범위를 줄이면 시간을 줄일 수 있..

    BOJ 2960 · 에라토스테네스의 체

    알고리즘 분류 : 수학 에라토스테네스의 체를 이용하는 문제이다. 자세한 내용은 이곳을 참조.주어진 규칙에 따라 숫자를 지우면서, 숫자를 카운트하면 된다. C++ 소스코드 #include bool prime[1001]; int main() { int n, k; int cnt = 0; scanf("%d %d", &n, &k); for (int i=2; i

    BOJ 1929 · 소수 구하기

    알고리즘 분류 : 수학 특정 범위 내에 존재하는 소수를 모두 구하는 문제이다. 여러 개의 소수를 구하기 위해서는, 에라토스테네스의 체를 이용하면 효율적이다. 2부터 N까지 구하고자 하는 소수를 모두 나열한다.아직 지우지 않은 숫자 중, 가장 작은 숫자 P는 소수이다.P를 제외한 P의 배수를 모두 지운다.P보다 크고 루트 N보다 작거나 같은 숫자가 존재하는지 확인한다.존재하면 두 번째, 세 번째 과정을 반복한다.존재하지 않으면, 2부터 N사이에는 소수만 남아있다.M부터 N까지 존재하는 소수를 출력한다. C++ 소스코드 #include const int MAX = 1000000; bool prime[MAX+1]; int main() { int m, n; scanf("%d %d", &m, &n); prime[..

    BOJ 1978 · 소수 찾기

    알고리즘 분류 : 수학 소수(Prime number)란 1과 자기 자신의 숫자로만 나누어떨어지는 2 이상의 자연수를 말한다. 예를 들면 2는 1과 2로만 나눌 수 있으며, 5는 1과 5로만 나눌 수 있다. 6은 1, 2, 3, 6으로 나눌 수 있으므로, 소수가 아니다. 2 미만의 정수는 소수가 아니다.숫자 N이 소수인지 아닌지를 판별하기 위해서 2부터 N-1까지 나눠보면 된다. 한 번이라도 나누어떨어지는 수가 존재하면, 그 수는 소수가 아니다.N-1까지 확인하면 속도가 느리다. 루트 N까지만 확인해도 소수인지 아닌지 판별할 수 있다. C++ 소스코드 #include bool prime(int x) { if (x