알고리즘

    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

    BOJ 1934 · 최소공배수

    알고리즘 분류 : 수학 최소공배수는 유클리드 호제법을 이용하여 구현할 수 있다. 자세한 내용은 이곳을 참조. 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, a, b; scanf("%d", &t); while (t--) { scanf("%d %d", &a, &b); printf("%d\n", (a*b)/gcd(a,b)); } return 0; } Python 3 소스코드 def gcd(x, y): while y is not 0: r = x%y x = y y = r return x for _ in range(int(input())): a, b..

    BOJ 2609 · 최대공약수와 최소공배수

    알고리즘 분류 : 수학 최대공약수(GCD; greatest common divisor)는 유클리드 호제법(Euclidean algorithm)을 이용하여 구현할 수 있다.r은 x를 y로 나눈 나머지 (r = x%y) GCD(x, y) = GCD(y, r) 를 r이 0이 될 때까지 반복적으로 수행r이 0일 때, y는 최대공약수이다. 최소공배수(LCM; least common multiple)는 미리 구한 최대공약수를 이용하여 구현할 수 있다.g = GCD(x, y)LCM = (x*y)/g C++ 소스코드 #include using namespace std; int gcd(int x, int y) { while (y != 0) { int r = x%y; x = y; y = r; } return x; } in..