BOJ

    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로 레지스터(숫자)를 탐색하고, 이동 경로와..

    BOJ 12100 · 2048 (Easy)

    알고리즘 분류 : 브루트 포스, 시뮬레이션 게임 '2048'을 구현하는 문제다. 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 구해야 한다. 2048을 구현하기 위해 크게 두 단계로 나눈다.첫 번째, 숫자 블록을 움직이는 단계, 두 번째, 블록을 합치는 단계이다.1. 움직이는 단계는 상, 하, 좌, 우 방향으로 총 4가지의 경우의 수가 있다.움직일 때, 방향에 따라 해당 열(또는 행)의 숫자 블록을 큐에 넣는다. 빈 공간(0)은 넣지 않는다. 블록을 넣었다면, 블록에 있던 자리는 빈 공간(0)으로 만든다.2. 합치는 단계에서는 큐에서 블록을 꺼내고 이를 순서대로 보드와 비교하면서 진행한다.만약 현재 좌표 보드가 빈 공간(0)이라면, 큐에 꺼낸 숫자를 그대로 보드에 놓는다.보드에 현재 좌표에 숫자가 ..