프로그래밍/알고리즘
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..