본문 바로가기

전체

BOJ 17144 · 미세먼지 안녕! 알고리즘 분류 : 시뮬레이션 문제에 주어진 조건을 그대로 구현하는 문제다. 크게 두 단계로 나눠서 설계해야 한다. 첫 번째, 미세먼지가 확산되는 과정, 두 번째 공기청정기의 바람이 순환하는 과정이다. 1. 모든 미세먼지는 5 이상의 양이 남아있으면, 상하좌우로 확산할 수 있다.확산할 때 상하좌우에 이미 먼지가 있는 경우가 있으므로, 별도의 배열을 만들어서 확산되는 먼지의 양을 저장해야 한다. 값을 바로 업데이트하면 다음 먼지 확산에 영향을 주기 때문에, 이 과정이 필요하다.현재 먼지의 양을 5로 나눈 후, 그 양을 상하좌우 칸에 더한다. 위에서 만든 별도의 배열 B에 더한다.모든 과정이 끝나면, 원래 먼지 배열 A에 확산 배열 B 값을 업데이트한다. 2. 미세먼지가 바람 방향에 따라 순환한다.입력받을 때..
BOJ 17143 · 낚시왕 알고리즘 분류 : 시뮬레이션 문제에 주어진 조건을 그대로 구현해야 하는 문제다. 크게 두 단계로 나눠서 설계해야 한다. 첫 번째, 낚시왕이 움직인 후 상어를 낚는 과정, 두 번째, 모든 상어가 제각기 움직이면서 서로를 잡아먹는 과정이다. 1. 낚시왕은 매 턴마다 한 칸 움직인 후, 상어 한 마리를 낚는다.먼저 낚시왕이 한 칸 앞으로 이동한다. 낚시왕은 최대 R(열의 개수)번 움직일 수 있다.도착한 열에서 땅에 가장 가까운 상어 한 마리를 낚는다. 땅에 가장 가까운 상어는 0에 가까운 행(C)에 위치한다. 2. 상어가 제각기 주어진 속도와 방향에 따라 움직이고, 자신보다 작은 상어를 잡아먹는다.상어의 속도는 움직일 수 있는 칸의 개수를 의미한다. 가장자리에 도달하면 방향을 바꿔서 남은 횟수만큼 움직여야 한..
BOJ 17142 · 연구소 3 알고리즘 분류 : BFS, 브루트 포스 연구소에 바이러스를 퍼트리는 데 걸리는 최소 시간을 구하는 문제다. 바이러스를 놓을 수 있는 경우를 모두 만든 후, 각 케이스에 대해 BFS로 바이러스를 퍼트려서 최솟값을 구하면 된다. BOJ 17141번 '연구소 2'와 거의 동일한 문제이다. 일부 값만 수정하면 된다. 연구소의 사이즈는 N이며, 바이러스의 개수는 M이다.바이러스를 놓을 수 있는 칸(2)의 좌표를 별도의 리스트 V에 저장한다.빈칸(0)의 개수를 모두 세고, 이를 K라 하자. 이 값은 바이러스를 퍼트려야 하는 칸의 총개수가 된다.조합(combination) 방법을 통해 M개의 바이러스를 바이러스 칸(2)에 둔다. 이때 리스트 V를 활용하여, 바이러스를 놓은 칸의 좌표를 큐에 모두 집어넣는다.BFS를 ..
BOJ 17141 · 연구소 2 알고리즘 분류 : BFS, 브루트 포스 연구소에 바이러스를 퍼트리는 데 걸리는 최소 시간을 구하는 문제다. 바이러스를 놓을 수 있는 경우를 모두 만든 후, 각 케이스에 대해 BFS로 바이러스를 퍼트려서 최솟값을 구하면 된다. 연구소의 사이즈는 N이며, 바이러스의 개수는 M이다.바이러스를 놓을 수 있는 칸(2)의 좌표를 별도의 리스트 V에 저장한다.빈칸(0)의 개수를 모두 세고, 여기에 바이러스를 놓을 수 있는 칸(2)의 개수를 더한 후, M을 뺀다. 이 값은 바이러스를 퍼트려야 하는 칸의 총개수가 된다. 이를 K라 하자.조합(combination) 방법을 통해 M개의 바이러스를 바이러스 칸(2)에 둔다. 이때 리스트 V를 활용하여, 바이러스를 놓은 칸의 좌표를 큐에 모두 집어넣는다.BFS를 통해 바이러스..
BOJ 17140 · 이차원 배열과 연산 알고리즘 분류 : 시뮬레이션 문제에 주어진 조건을 그대로 구현하는 문제다. 여러 개의 변수를 가진 구조체(또는 벡터)를 정렬해야 한다. 연산자 오버로딩을 통해 우선순위를 구현하거나, STL pair를 사용하면 된다. 정렬 대신, 우선순위 큐를 사용할 수 있다. 행의 최대 사이즈를 N, 열의 최대 사이즈를 M이라고 하자.이 문제는 N >= M일 때 각 행을 정렬하고, N < M일 때 각 열을 정렬한다.정렬의 우선순위는 1) 수의 등장 횟수, 2) 해당 숫자이며, 오름차순으로 정렬한다.수의 등장 횟수는 별도의 카운터 배열을 만들어서 해당 숫자가 얼마나 등장하는지 센다.배열에 값이 들어갈 때는 숫자가 먼저 들어가며, 그다음으로 수의 등장 횟수가 들어간다.정렬 연산이 수행되면, 행 또는 열이 커질 수 있다. 커..
BOJ 17069 · 파이프 옮기기 2 알고리즘 분류 : 다이나믹 프로그래밍 파이프를 옮겨서 한쪽 끝을 (N, N)으로 이동시키는 방법의 개수를 구해야 한다. BOJ 17070번 '파이프 옮기기 1'이 업그레이드된 문제이다. N의 범위가 최대 32로 증가했다. 하지만 시간제한은 0.5초로 줄어들었으므로, 백트래킹으로 구현할 수 없다. 때문에 이 문제는 DP를 이용하여 구현해야 한다. DP로 구현하면 1번 문제도 해결할 수 있다. 파이프의 상태는 3가지로 나눌 수 있다. 1. 가로로 놓여있는 상태 (0) : 가로(0) → 가로(0) 또는 대각선(2)2. 세로로 놓여있는 상태 (1) : 세로(1) → 세로(1) 또는 대각선(2)3. 대각선으로 놓여있는 상태 (2) : 대각선(2) → 가로(0) 또는 세로(1) 또는 대각선(2) D[M][X][Y]..
BOJ 16985 · Maaaaaaaaaze 알고리즘 분류 : BFS, 브루트 포스 3차원 미로를 탈출하는 것을 구현해야 한다. 단순한 3차원 BFS는, BOJ 7569번 '토마토'처럼 구현하면 된다. 하지만, 이 문제는 각 층의 미로가 회전하고, 각 층마다 섞여서 까다롭다. 미로를 제대로 만드는 것이 중요하다. 미로 맵을 나타낼 3차원 배열의 인덱스는 [층 번호] [X좌표] [Y좌표] 이다.각 층을 섞는 것을 순열을 통해 만든다. 별도의 인덱스[0~4]를 만들어서 층을 나타내고, 이를 순열로 섞으면 된다.층을 섞은 후, 각 층을 회전해야 한다. 별도의 회전 함수를 만들고, 5중 for문 또는 재귀를 통해 각 층을 순차적으로 회전시킨다.첫 층의 출발 칸(0, 0, 0)이 이동할 수 있는 칸[1]인 경우에만 다음 층을 섞는다. 이동할 수 없는 칸[0..
BOJ 1149 · RGB거리 알고리즘 분류 : 다이나믹 프로그래밍 RGB 거리의 각 집에 색칠하는 비용을 구해야 한다. DP로 구현하여 색칠할 때 드는 최소 비용을 구하면 된다. D[N][M] : N번째 집을 M으로 칠할 때 드는 최소 비용 (M은 색깔 0~2)D[N][0] : N번째 집을 빨간색(0)으로 칠할 때 드는 최소 비용D[N][1] : N번째 집을 초록색(1)으로 칠할 때 드는 최소 비용D[N][2] : N번째 집을 파란색(2)으로 칠할 때 드는 최소 비용D[1][0] = P[1][0], D[1][1] = P[1][1], D[1][2] = P[1][2] C++ 소스코드 #include #include using namespace std; int n, d[1001][3], p[1001][3]; void solve() { f..
BOJ 1012 · 유기농 배추 알고리즘 분류 : DFS 배추 밭에 놓아야 하는 배추흰지렁이의 마릿수를 구해야 한다. 배추흰지렁이는 하나의 배추 그룹에 한 마리만 놓으면, 최소 마릿수가 된다. 즉, 이 문제는 배추 그룹의 수를 세는 플러드 필 문제이다. 배추가 인접한 상하좌우로 연결되면, 이것은 하나의 배추 그룹이 된다. 우선 N*M 사이즈의 배열 A를 만들고 모든 좌표를 0으로 둔다.입력으로 주어지는 배추의 좌표 (X, Y)를 배열 A에 1로 둔다.N*M 사이즈의 맵을 DFS를 통해 모든 곳을 방문할 때까지 완전 탐색한다.DFS로 다음 좌표를 이동할 때, 배추(1)로만 이동한다.테스트케이스가 여러 개 주어지므로, 초기화가 매번 필요하다. C++ 소스코드 #include #include int m, n, k, ans; int a[51]..
BOJ 17070 · 파이프 옮기기 1 알고리즘 분류 : 백트래킹 파이프를 옮겨서 한쪽 끝을 (N, N)으로 이동시키는 방법의 개수를 구해야 한다. 파이프는 2칸을 차지하지만, 파이프의 끝만 고려하면 된다. 파이프의 상태는 3가지로 나눌 수 있다. 1. 가로로 놓여있는 상태 (0) : 가로(0) → 가로(0) 또는 대각선(2)2. 세로로 놓여있는 상태 (1) : 세로(1) → 세로(1) 또는 대각선(2)3. 대각선으로 놓여있는 상태 (2) : 대각선(2) → 가로(0) 또는 세로(1) 또는 대각선(2)가로(0)에서 세로(1)로 곧바로 이동할 수 없고, 세로(1)에서 가로(0)로 곧바로 이동할 수 없다. 재귀 함수의 인자는 (X 좌표, Y 좌표, 파이프 상태) 이다.현재 파이프 상태에 따라서 다음 이동의 파이프 상태를 위의 3가지 조건에 따라 ..
BOJ 2156 · 포도주 시식 알고리즘 분류 : 다이나믹 프로그래밍 N개의 포도주 잔이 있을 때, 최대로 마실 수 있는 포도주의 양을 구해야 한다. DP를 이용하여 포도주 마시는 규칙에 따라 구현하면 된다. 포도주는 연속으로 3잔 이상 마실 수 없다. 즉, 연속하여 마실 수 있는 포도주는 최대 2잔이다.D[N] : N 번째 잔의 포도주를 마셨을 때, 최대로 마실 수 있는 포도주의 양 D[N]은 3가지 경우의 수로 나눌 수 있으며, 3가지 값 중 가장 큰 값이 D[N]이 된다.1. N 번째 잔을 마시지 않은 경우 : D[N-1]2. N 번째 잔이 연속 1잔째 마신 경우 : D[N-2] + P[N] (N-1 번째 잔은 마시지 않아야 한다.)3. N 번째 잔이 연속 2잔째 마신 경우 : D[N-3] + P[N-1] + P[N-1] (N-2..
BOJ 17135 · 캐슬 디펜스 알고리즘 분류 : 브루트 포스, 시뮬레이션 궁수를 성에 적절히 배치하여 적을 최대한 많이 죽이도록 구현하는 문제다. 가능한 궁수의 배치를 모두 만들고, 각 배치에서 적을 얼마나 쏴 죽일 수 있는지 카운트하면 된다. N*M 사이즈의 맵에서 궁수는 N+1번째 줄에 3명이 배치된다.궁수가 서로 겹치지 않도록, 3중 for문 또는 재귀를 통해 각각 배치한다. 조합 방식으로 구현하면 된다.그리고 배치한 위치의 인덱스를 별도로 저장한다. 아래의 코드에서는 archer 배열에 Y좌표(열 인덱스)가 저장되어 있다.각 배치에서 궁수로부터 적이 얼마나 떨어져 있는지 계산하고, 각 적을 죽여야 한다. 1. 궁수의 위치를 (N, K)라고 하고, 적의 위치를 (i, j)라고 하자. 단, (0≤i<N, 0≤j<M) 이다.2. 궁..