알고리즘
(C++) 백준 7569번 - 토마토
문제 링크 : https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 토마토(백준 7576번)의 3차원 버전이다. 2차원과 동일하게 진행하되 체크를 6개의 방향으로 진행하도록 BFS를 구현하면 된다. #include #include #include using namespace std; int dx[6] = {1,0,0,-1,0,0}; int dy[6] = {0,1,0,0,-1,0}; int dz[6] = {0,0,1,0,0..
(C++) 백준 10026번 - 적록색약
문제 링크 : https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 백준 1926번 그림 문제와 거의 동일한 문제이다. BFS를 이용하여 풀이를 하였다. 색약이 아닌 사람들은 1926번에서 풀이한 그대로 하면 되고, 색약인 사람들의 경우에만 R과 G를 동일한 색인 것처럼 풀이하면 된다. //boj 10026 성공 #include #include #include #define X first #define Y second using name..
(C++) 백준 1074번 - Z
풀이 재귀를 이용하여 풀이하였다. 2의 거듭제곱으로 커져가기 때문에 한 변의 길이가 2, 4, 8, 16, ... 순으로 증가한다. 그렇기 때문에 한 변이 2일 때를 재귀를 종료하는 base condition으로 두고, 사각형들을 4개로 분할하여(한 변의 길이를 2배씩 줄여) 나가면서 풀었다. #include using namespace std; int calZ(int n, int r, int c){ if(n == 1){ // 2 * 2 일 때 if(r == 0 and c == 0) return 0; else if(r == 0 and c == 1) return 1; else if(r == 1 and c == 0) return 2; else return 3; } int half = (1= half and ..
(C++) 백준 11729번 - 하노이 탑 이동 순서
문제 링크 : https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이 재귀 문제의 대명사격인 하노이 탑 문제이다. s에서 l로 n개를 이동하려면 다음과 같은 과정을 거치면 된다. 1. 제일 아래에 있는 가장 큰 판을 제외한 n-1개의 판을 s에서 6-s-l로 이동시킨다. 2. 제일 큰 판을 s에서 l로 이동시킨다. 3. 1에서 6-s-l로 이동한 n-1개의 판을 l로 이동시킨다. 이 과정을 재귀로 반복하여 문제를 풀이하였다. #inc..
(C++) 백준 1629번 - 곱셈
문제 링크 : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 재귀를 활용하여 풀이하였다. "n의 k승을 알면, n의 2k승과 n의 2k+1승을 알 수 있다."는 사실과 "(a x b) % k = (a % k) x (b % k)"라는 사실을 활용하여 풀이를 진행하였다. #include using namespace std; using ll = long long; int power(ll a, ll b, ll c){ if(b == 0) return 1; // 모든 수의 0승은 1 if(b == 1) retur..
(C++) 백준 1697번 - 숨바꼭질
문제 링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 응용한 문제로 실버 1 문제치곤 어렵지 않게 해결할 수 있다. 다만 조건에 수빈이와 동생이 같은 위치에 있을 순 없다는 말이 없으므로 같은 위치에 존재하면 그냥 0을 출력하고 종료할 수 있도록 해야 한다. #include #include #include #define X first #define Y second using namespace s..
(C++) 백준 4179번 - 불!
문제 링크 : https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 풀이 BFS를 응용한 문제로, 불에 대한 BFS와 지훈이에 대한 BFS를 동시에 사용하는 방법으로 풀이하면 된다. 골드 4 문제답게 조건들을 설정하는 것이 매우 복잡했다. #include #include #include #define X first #define Y second using namespace std; int dx[4] = {1,0,-1,0}; int d..
(C++) 백준 7576번 - 토마토
문제 링크 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 BFS를 이용한 거리 문제와 비슷하게 풀이하면 된다. 거리를 토마토가 익는 데 걸리는 시간의 길이라고 생각하고 풀면 어렵지 않게 해결할 수 있다. 문제 해결 시 중요한 점은 시작점이 될 수 있는 후보들, 즉 익은 토마토들의 위치를 먼저 파악 후에 이들을 Queue에 넣고 시작해야 한다는 점이다. #include #include #include #define X ..
(C++) 백준 2178번 - 미로 탐색
문제 링크 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 BFS를 사용하여 풀이하였다. 다른 BFS 문제를 풀어보았다면 실버 1 문제라기엔 크게 어렵지 않은 문제이다. 오히려 공백없이 들어오는 숫자들을 어떻게 한 자리씩 입력받아 저장할지를 더 많이 고민하였다. #include #include #include #define X first #define Y second using namespace std; int dx[4] = {1,0,-1,0}; int dy[4] =..
(C++) 백준 1926번 - 그림
문제 링크 : https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 BFS를 사용하여 풀이하면 되는 문제이다. 그림의 시작점을 찾기 위해 전체적으로 이중 for문으로 스캔하면서 아직 방문하지 않은 시작점을 찾는다. 그 후 BFS를 사용하여 인접 칸들을 순회하면서 그림의 크기를 알아내었다. #include #include #include #define X first #define Y second using namespace std; int dx[4] ..