프로그래밍/알고리즘
BOJ 2638 · 치즈
알고리즘 분류 : BFS 치즈가 완전히 녹기까지 걸리는 시간을 구하는 문제다. 치즈는 한 칸에 놓이며, 인접한 칸에 외부 공기(0)가 2칸 이상 있다면, 녹는다. 내부 공기는 치즈에 영향을 주지 않으므로 유의해야 한다. 입력으로 주어지는 맵은 가장자리가 항상 외부 공기(0)로 주어진다.따라서 (0, 0)이 항상 공기 칸이므로, BFS의 시작을 (0, 0)으로 한다.인접한 상하좌우 칸이 공기(0)라면, 이동한다.인접한 칸이 치즈(1)라면, 치즈를 1만큼 증가시킨다.BFS 탐색이 완료되면, 치즈는 1 이상의 값으로 된다.이때, 치즈 값이 3 이상이라면, 2번 이상 외부 공기에 닿은 것이므로, 치즈를 녹여서 공기 칸(0)으로 만든다.치즈 값이 2라면, 외부 공기에 한 번만 닿은 것이므로, 1로 다시 되돌려 놓..
BOJ 9376 · 탈옥
알고리즘 분류 : BFS 두 죄수를 감옥에서 탈옥시킬 때, 열어야 하는 문의 최소 개수를 구하는 문제다. 죄수가 2명이고, 각 죄수는 문을 공유하며, 한 번만 문을 열어야 하기 때문에 까다롭다. 때문에 이 문제는 다른 방식으로 생각해야 한다. 1. 첫 번째 죄수부터 출발하여 문을 여는 경우2. 두 번째 죄수부터 출발하여 문을 여는 경우 위 두 가지로 나눠서 생각하면, 어떤 위치(X, Y)에서 함께 만나서 도착점(0, 0)으로 간다고 볼 수 있다. 도착점이 (0, 0)인 이유는 맵의 가장자리로 탈출해야 하기 때문이다.어떤 위치에서 도착점까지 가는 경우는 맵의 사이즈 만큼 존재한다. 이를 반대로 생각하면, 도착점(0, 0)에서 어떤 위치(X, Y)로 오는 경우로 볼 수 있다. 때문에, 이를 3가지의 경우로 ..
BOJ 2251 · 물통
알고리즘 분류 : BFS 부어서 만들 수 있는 물통의 경우의 수를 모두 만들고, 첫 번째 물통이 비어 있을 때 세 번째 물통에 담겨있는 물의 양을 구해야 한다. BFS를 통해 물을 옮기면서 경우의 수를 만들 수 있다. 물통이 총 3개이지만, 2개로 해결할 수 있다.물통에서 물을 옮길 때, 물의 양은 변하지 않으므로, 물통의 상태 변화를 첫 번째 물통과 두 번째 물통만 나타내도 된다.세 번째 물통에 있는 물의 양은 C-X-Y로 나타낼 수 있다.물 옮기는 방법은 총 6가지이다. X→Y, X→Z, Y→X, Y→Z, Z→X, Z→Y이다.첫 번째 물통이 비어있으면, 정답 리스트에 세 번째 물통에 남아있는 물의 양을 저장한다.탐색이 끝나면, 정답 리스트를 정렬하고 출력한다. C++ 소스코드 #include #inc..
BOJ 1525 · 퍼즐
알고리즘 분류 : BFS 3x3 표에서 퍼즐을 맞춰야 하는 문제다. 빈칸(0)을 옮겨서 정렬된 123456780으로 퍼즐을 맞춰야 한다. BFS로 퍼즐을 한 칸 옮기면서, 매번 퍼즐 상태를 저장해야 한다. 메모리 제한이 32 MB이기 때문에, 9자리의 수를 한 번에 저장할 수는 없다. 이 때문에 map 자료구조를 사용해야 한다. 입력받을 때, 빈 칸(0)을 숫자 9로 치환한다. 그 후, 입력받은 9개의 수를 9자리 수로 변환한다.퍼즐 상태를 저장할 dist를 map 자료구조로 선언한다. 은 자료형이며, 각 값은 이다.큐(Queue)에는 9자리 정수를 push하고, pop한 숫자를 문자열로 변환한다.변환한 문자열에서 문자 '9'의 위치를 찾는다.9자리 수의 문자열에 문자 '9'의 위치를 k라 하고, 3*3..
BOJ 1644 · 소수의 연속합
알고리즘 분류 : 투 포인터, 수학 에라토스테네스의 체로 소수를 먼저 구하고, 구한 소수를 바탕으로 투 포인터 알고리즘을 사용하여 해결할 수 있다.에라토스테네스의 체는 BOJ 1929번 '소수 구하기'를, 투 포인터는 BOJ 2003번 '수들의 합 2'를 참조. C++ 소스코드 #include #include using namespace std; int n, sum, ans, left, right; vector a; void prime() { vector c(n+1); for (int i=2; i*i n: break if not c[i]: for j in range(i*i, n+1, i): c[j] = True for i in range(2, n+1): if not c[i]: a.append(i) def..
BOJ 1806 · 부분합
알고리즘 분류 : 투 포인터 N 길이의 수열에서 연속된 수들의 부분합이 S 이상 되는 것 중, 가장 짧은 것의 길이를 구하는 문제다. 투 포인터 알고리즘을 응용하면 된다. 투 포인터에 대한 설명은 BOJ 2003번 '수들의 합 2' 문제를 참조. C++ 소스코드 #include int n, m, len, sum, left, right; int a[100000]; void solve() { int ans = 1e9; while (true) { if (sum >= m) { if (ans > len) ans = len; sum -= a[left]; left++; len--; } else { if (right == n) break; sum += a[right]; right++; len++; } } printf(..
BOJ 2003 · 수들의 합 2
알고리즘 분류 : 투 포인터 N개의 수로 구성된 수열에서 연속된 수의 합이 M이 되는 경우의 수를 구하는 문제다. 투 포인터 알고리즘으로 구현할 수 있다. 왼쪽과 오른쪽을 가리키는 포인터 Left, Right를 만든다. 이 포인터는 배열의 인덱스를 가리킨다.Left, Right는 각각 인덱스 0부터 시작한다.1. 현재의 합(Sum)이 M 이상인 경우- Left가 가리키는 값을 합에서 빼고, Left를 1 증가시킨다.2. 현재의 합이 M 미만인 경우- Right의 값이 인덱스 N인 경우, 루프를 종료한다. 즉, Right가 배열의 범위를 벗어난 경우에 종료한다.- Right가 N이 아니라면, Right가 가리키는 값을 합에 더하고, Right를 1 증가시킨다.3. 현재의 합이 M인 경우- 정답(Answer..
BOJ 9019 · DSLR
알고리즘 분류 : BFS A에서 B로 변환하기 위한 최소의 명령어 나열을 구하는 문제다. 변환 명령어는 총 4가지가 있으며, 최소 명령어 나열을 구해야 하므로, BFS를 사용하면 된다. 명령어 리스트는 역순으로 추적하면 된다. 레지스터를 변환하는 명령어는 총 4가지이다.현재 레지스터를 X라 했을 때, 명령어에 의해 변환되는 다음 레지스터를 Y라 하자. 각 명령에 따른 레지스터는 아래와 같이 나타낼 수 있다.명령어 D : Y = (X*2) % 10000명령어 S : Y = X-1 (단, Y < 0일 경우, Y = 9999)명령어 L : Y = (X%1000)*10 + X/1000명령어 R : Y = X/10 + (X%10)*1000위 4가지 명령어에 따라, BFS로 레지스터(숫자)를 탐색하고, 이동 경로와..