본문 바로가기

전체

BOJ 1525 · 퍼즐 알고리즘 분류 : BFS3x3 표에서 퍼즐을 맞춰야 하는 문제다. 빈칸(0)을 옮겨서 정렬된 123456780으로 퍼즐을 맞춰야 한다. BFS로 퍼즐을 한 칸 옮기면서, 매번 퍼즐 상태를 저장해야 한다. 메모리 제한이 32 MB이기 때문에, 9자리의 수를 한 번에 저장할 수는 없다. 이 때문에 map 자료구조를 사용해야 한다.입력받을 때, 빈 칸(0)을 숫자 9로 치환한다. 그 후, 입력받은 9개의 수를 9자리 수로 변환한다.퍼즐 상태를 저장할 di..
BOJ 1644 · 소수의 연속합 알고리즘 분류 : 투 포인터, 수학 (소수)에라토스테네스의 체로 소수를 먼저 구하고, 구한 소수를 바탕으로 투 포인터 알고리즘을 사용하여 해결할 수 있다.에라토스테네스의 체는 BOJ 1929번 '소수 구하기'를, 투 포인터는 BOJ 2003번 '수들의 합 2'를 참조.C++ 소스코드#include <cstdio> #include <vector> using namespace std; int n, sum, ans, lef..
BOJ 1806 · 부분합 알고리즘 분류 : 투 포인터N 길이의 수열에서 연속된 수들의 부분합이 S 이상 되는 것 중, 가장 짧은 것의 길이를 구하는 문제다. 투 포인터 알고리즘을 응용하면 된다. 투 포인터에 대한 설명은 BOJ 2003번 '수들의 합 2' 문제를 참조.C++ 소스코드#include <cstdio> int n, m, len, sum, left, right; int a[100000]; void solve() { int ans = 1..
BOJ 2003 · 수들의 합 2 알고리즘 분류 : 투 포인터N개의 수로 구성된 수열에서 연속된 수의 합이 M이 되는 경우의 수를 구하는 문제다. 투 포인터 알고리즘으로 구현할 수 있다.왼쪽과 오른쪽을 가리키는 포인터 Left, Right를 만든다. 이 포인터는 배열의 인덱스를 가리킨다.Left, Right는 각각 인덱스 0부터 시작한다.1. 현재의 합(Sum)이 M 이상인 경우- Left가 가리키는 값을 합에서 빼고, Left를 1 증가시킨다.2. 현재의 합이 M 미만인 ..
BOJ 9019 · DSLR 알고리즘 분류 : BFSA에서 B로 변환하기 위한 최소의 명령어 나열을 구하는 문제다. 변환 명령어는 총 4가지가 있으며, 최소 명령어 나열을 구해야 하므로, BFS를 사용하면 된다. 명령어 리스트는 역순으로 추적하면 된다.레지스터를 변환하는 명령어는 총 4가지이다.현재 레지스터를 X라 했을 때, 명령어에 의해 변환되는 다음 레지스터를 Y라 하자. 각 명령에 따른 레지스터는 아래와 같이 나타낼 수 있다.명령어 D : Y = (X*2..
BOJ 12100 · 2048 (Easy) 알고리즘 분류 : 브루트 포스게임 '2048'을 구현하는 문제다. 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 구해야 한다.2048을 구현하기 위해 크게 두 단계로 나눈다.첫 번째, 숫자 블록을 움직이는 단계, 두 번째, 블록을 합치는 단계이다.1. 움직이는 단계는 상, 하, 좌, 우 방향으로 총 4가지의 경우의 수가 있다.움직일 때, 방향에 따라 해당 열(또는 행)의 숫자 블록을 큐에 넣는다. 빈 공간(0)은 넣지 않는다. 블록을 넣었다면,..
BOJ 2580 · 스도쿠 알고리즘 분류 : 백트래킹스도쿠는 9 x 9 칸에 숫자를 채워 넣는 퍼즐 게임이다. 워낙 유명한 게임이니, 부연 설명은 생략. 이 문제는 비워진 칸에 숫자를 채워 넣어야 한다. N-퀸과 마찬가지로 백트래킹 알고리즘을 쓰면 된다.가로 줄, 세로 줄, 서브 사각형을 체크할 변수를 각각 2차원 배열로 선언한다.row는 가로 줄(행)을 나타내며, 인덱스는 [행 번호] [채워 넣은 숫자] 이다.col은 세로 줄(열)을 나타내며, 인덱스는 [열 번호] [채워 ..
BOJ 9663 · N-Queen 알고리즘 분류 : 백트래킹N-퀸은 백트래킹 알고리즘에서 가장 대표적인 문제다. N x N 사이즈의 체스판에 N개의 퀸을 놓는 방법의 수를 구해야 한다.다음 위치에 퀸을 놓을 때마다, 해당 위치에 퀸을 놓을 수 있는지 확인하면서 백트래킹을 하면 된다.가능 여부를 확인할 때, 하나의 배열에서 매번 상하좌우 대각선을 확인하는 것은 효율적이지 않다.3개의 배열을 만들고, 각각 세로 줄(|), 대각선 줄(/), 대각선 줄(\)을 체..
BOJ 1987 · 알파벳 알고리즘 분류 : DFS, 백트래킹N x M 사이즈의 보드에서 (0, 0) 부터 출발하여 최대한 많이 지날 수 있는 거리를 구하는 문제다. 단, 이동할 때 이미 지나쳤던 알파벳을 다시 지날 수 없다. DFS 기반에 백트래킹을 하면 된다.방문 여부를 체크할 check 배열의 길이는 알파벳의 개수(26개) 만큼 선언한다.상하좌우로 이동하면서, 방문하지 않은 알파벳이라면 true로 체크한다.이동하면서, 이미 방문한 알파벳이라면 무시한다.DFS이므..
BOJ 1248 · 맞춰봐 알고리즘 분류 : 백트래킹입력으로 주어지는 합의 부호에 맞는 숫자 배열을 출력하는 문제다. 총 21개의 숫자 중에서 N개의 숫자를 골라야 한다. 일반적인 재귀 함수를 통해 브루트 포스로 구현하면 시간 초과가 나기 쉬우므로, 백트래킹 기법을 사용해야 한다.숫자의 범위 (-10 ~ 10) 만큼 재귀 함수를 호출한다.하나의 숫자를 고를 때마다, 이 숫자가 주어진 부호에 맞는지 확인한다.해당 숫자가 가능하다면, 다음 재귀 함수를 호출한다.하나의 숫..
BOJ 6087 · 레이저 통신 알고리즘 분류 : BFS'C'와 'C' 사이를 레이저로 연결하기 위해 필요한 거울의 개수를 세는 문제다. 최소의 거울을 설치해야 하므로, BFS 탐색을 통해 해결하는 것이 좋다. 레이저는 직선으로 움직이며, 레이저가 방향을 꺾기 위해서 거울이 필요하다.기본적으로 BFS 탐색을 하되, 한 번 이동할 때 갈 수 있는 데까지 이동한다."갈 수 있는 데까지"란, 벽('*')을 만나기 전까지 또는 범위를 벗어나기 전까지이다.같은 방향으로 한 칸씩 이..
BOJ 1445 · 일요일 아침의 데이트 알고리즘 분류 : 다익스트라S부터 출발해서 F에 도착할 때까지, 쓰레기를 최소로 지나면서, 쓰레기의 옆을 최소로 지나는 방법을 찾는 문제다. 두 가지의 우선순위 조건 때문에, 다익스트라 알고리즘을 사용하는 것이 좋다. 다익스트라를 이용하기 위해, 입력으로 주어지는 문자열 맵에 상응하는 인접 행렬을 만든다.쓰레기가 있는 칸 'g'는 2500으로 두고, g에 인접한 4칸은 1로 둔다. 나머지 칸은 0으로 둔다.맵이 최대 50*..