프로그래밍
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
BOJ 7569 · 토마토
알고리즘 분류 : BFS 7576번 토마토 문제가 약간 변형된 문제다. 토마토 상자가 2차원에서 3차원으로 업그레이드되었다. 원래 문제는 범위가 1000 X 1000이었는데, 이번 문제는 100 X 100 X 100이다. 최대 10^6이므로 완전 탐색이 가능하다. 3차원 배열을 통한 BFS를 돌리면 된다.7576번 문제에 대한 해설과 코드는 이곳에서 참조. C++ 소스코드 #include #include using namespace std; struct tomato { int x, y, z; }; int m, n, h, ans; int a[101][101][101]; const int dx[] = {-1, 1, 0, 0, 0, 0}; const int dy[] = {0, 0, -1, 1, 0, 0}; c..
BOJ 7576 · 토마토
알고리즘 분류 : BFS 익은 토마토는 인접하면서 아직 익지 않은 토마토를 익게 만든다. 하루에 1칸 인접한 토마토만 익게 만들 때, 모두 익게 만드는 최소 일수를 구하는 문제이다. 다르게 말하면, 간선 길이가 1인 그래프에서 최단 거리를 구하는 문제와 비슷하다. 즉, BFS를 사용하면 된다. 우선 토마토 배열을 입력받는다. 1은 이미 익은 토마토이므로 입력받으면서 Queue에 집어 넣는다.토마토를 익힐 때, 인접한 4칸(상하좌우)을 확인해야 한다. 이때, 0인지 아닌지 확인하고, 0이면 익게 만든다.토마토 배열은 날짜 카운트 배열로 사용 가능하다. 처음부터 익은 토마토는 1, 다음 날 익은 토마토는 1+1, 그 다음 날은 2+1, ··· 순으로 1일씩 증가시킨다.BFS를 통해 인접한 토마토를 모두 익혔..
BOJ 2178 · 미로 탐색
알고리즘 분류 : BFS BFS를 통해 최단 거리를 구하는 문제이다. 먼저 N x M 크기의 배열에 값을 입력받는다.1은 이동 가능하고, 0은 이동 불가능하므로, BFS 탐색을 하면서 값이 0인 곳으로 이동하지 않도록 구현한다.현재 좌표가 N, M이면 탐색을 중지해도 되므로, break를 건다.출발 좌표가 (0,0)이면 (N-1, M-1)이 도착이고, (1, 1)에서 출발했으면 (N, M)이 도착이다.이동하면서 좌표가 배열 범위를 벗어나지 않도록 체크한다. C++ 소스코드 #include #include using namespace std; struct maze { int x, y; }; int n, m; int a[101][101]; int dist[101][101]; const int dx[] = {..
BOJ 1260 · DFS와 BFS
알고리즘 분류 : DFS, BFS DFS와 BFS의 기초를 다질 수 있는 문제이다. DFS(Depth-First Search)란 깊이 우선 탐색의 줄임말로, 그래프에서 완전 탐색을 할 때 깊이를 우선순위로 탐색하는 방법을 말한다. 스택(Stack) 자료구조에 방문한 노드를 저장하면서 깊이 우선 탐색을 진행한다. 스택 자료구조(반복문으로 구현) 대신 재귀로 구현할 수 있다. 재귀 함수로 구현하면 스택 메모리를 사용하므로, 메모리 오버헤드가 발생할 수 있다. 재귀를 통한 DFS 구현이 스택 자료구조를 통한 DFS 구현보다 좀 더 코드가 깔끔하고 구현이 용이한 편이다.BFS(Breadth-First Search)란 너비 우선 탐색의 줄임말로, 그래프에서 완전 탐색을 할 때 너비를 우선순위로 탐색하는 방법을 말..
BOJ 1735 · 분수 합
알고리즘 분류 : 수학 분수의 합은 유클리드 호제법을 이용하여 간단히 구현할 수 있다. 자세한 내용은 이곳을 참조. 먼저 두 분수를 더한다.분수1 = 분자1/분모1, 분수2 = 분자2/분모2 라고 할 때, 분수 합 = (분자1*분모2 + 분자2*분모1)/(분모1*분모2)합한 분수에 대한 기약 분수를 구한다.분자와 분모의 GCD를 구한 후, 분자 분모에 각각 나눈다. C++ 소스코드 #include int gcd(int x, int y) { while (y != 0) { int r = x%y; x = y; y = r; } return x; } int main() { int n1, d1, n2, d2; scanf("%d %d %d %d", &n1, &d1, &n2, &d2); int n = n1*d2 + n..
BOJ 9613 · GCD 합
알고리즘 분류 : 수학 최대공약수(GCD)는 유클리드 호제법을 이용하여 구할 수 있다. 자세한 내용은 이곳을 참조. n개의 숫자에서 가능한 모든 쌍에 대한 GCD를 구해야 하므로, 2중 for문을 통해 gcd 함수를 호출한다.각 숫자 쌍에서 구한 gcd를 모두 합하여 출력한다. C++ 소스코드 #include int gcd(int x, int y) { while (y != 0) { int r = x%y; x = y; y = r; } return x; } int main() { int t, n, a[100]; scanf("%d", &t); while (t--) { long long sum = 0; scanf("%d", &n); for (int i=0; i