전체 글
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)이라면, 큐에 꺼낸 숫자를 그대로 보드에 놓는다.보드에 현재 좌표에 숫자가 ..
BOJ 2580 · 스도쿠
알고리즘 분류 : 백트래킹 스도쿠는 9 x 9 칸에 숫자를 채워 넣는 퍼즐 게임이다. 워낙 유명한 게임이니, 부연 설명은 생략. 이 문제는 비워진 칸에 숫자를 채워 넣어야 한다. N-퀸과 마찬가지로 백트래킹 알고리즘을 쓰면 된다. 가로 줄, 세로 줄, 서브 사각형을 체크할 변수를 각각 2차원 배열로 선언한다.row는 가로 줄(행)을 나타내며, 인덱스는 [행 번호] [채워 넣은 숫자] 이다.col은 세로 줄(열)을 나타내며, 인덱스는 [열 번호] [채워 넣은 숫자] 이다.squ는 3 x 3 사이즈의 서브 사각형을 나타내며, 인덱스는 [서브 사각형 번호] [채워 넣은 숫자] 이다.서브 사각형은 왼쪽 위에서부터 오른쪽 아래까지 0~8로 번호를 매긴다.1칸의 인덱스를 (X, Y)로 나타낸다고 할 때, 3 x 3..
BOJ 9663 · N-Queen
알고리즘 분류 : 백트래킹 N-퀸은 백트래킹 알고리즘에서 가장 대표적인 문제다. N x N 사이즈의 체스판에 N개의 퀸을 놓는 방법의 수를 구해야 한다.다음 위치에 퀸을 놓을 때마다, 해당 위치에 퀸을 놓을 수 있는지 확인하면서 백트래킹을 하면 된다. 가능 여부를 확인할 때, 하나의 배열에서 매번 상하좌우 대각선을 확인하는 것은 효율적이지 않다.3개의 배열을 만들고, 각각 세로 줄(|), 대각선 줄(/), 대각선 줄(\)을 체크한다.N x N 판에서 한 칸의 인덱스를 [X, Y]라 하자. 세로 줄(|)은 각 칸이 [Y]이며, 대각선(/)은 각 칸이 [X+Y]이고, 대각선(\)은 각 칸이 [X-Y+N-1]이다. 아래의 그림은 N이 5일 때의 예시다.solve 함수에서 인자 i는 행(row)이며, for 문..
BOJ 1987 · 알파벳
알고리즘 분류 : DFS, 백트래킹 N x M 사이즈의 보드에서 (0, 0) 부터 출발하여 최대한 많이 지날 수 있는 거리를 구하는 문제다. 단, 이동할 때 이미 지나쳤던 알파벳을 다시 지날 수 없다. DFS 기반에 백트래킹을 하면 된다. 방문 여부를 체크할 check 배열의 길이는 알파벳의 개수(26개) 만큼 선언한다.상하좌우로 이동하면서, 방문하지 않은 알파벳이라면 true로 체크한다.이동하면서, 이미 방문한 알파벳이라면 무시한다.DFS이므로, 가장 깊게 들어갔을 때가 정답이 된다. C++ 소스코드 #include int n, m, ans; char a[20][20]; bool check[26]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; void..
BOJ 1248 · 맞춰봐
알고리즘 분류 : 백트래킹 입력으로 주어지는 합의 부호에 맞는 숫자 배열을 출력하는 문제다. 총 21개의 숫자 중에서 N개의 숫자를 골라야 한다. 일반적인 재귀 함수를 통해 브루트 포스로 구현하면 시간 초과가 나기 쉬우므로, 백트래킹 기법을 사용해야 한다. 숫자의 범위 (-10 ~ 10) 만큼 재귀 함수를 호출한다.하나의 숫자를 고를 때마다, 이 숫자가 주어진 부호에 맞는지 확인한다.해당 숫자가 가능하다면, 다음 재귀 함수를 호출한다.하나의 숫자 리스트만 찾으면 되므로, 찾으면 바로 프로그램을 종료한다. C++ 소스코드 #include #include #include using namespace std; int n; char a[10][10]; vector v; bool possible(int idx) ..
BOJ 6087 · 레이저 통신
알고리즘 분류 : BFS 'C'와 'C' 사이를 레이저로 연결하기 위해 필요한 거울의 개수를 세는 문제다. 최소의 거울을 설치해야 하므로, BFS 탐색을 통해 해결하는 것이 좋다. 레이저는 직선으로 움직이며, 레이저가 방향을 꺾기 위해서 거울이 필요하다. 기본적으로 BFS 탐색을 하되, 한 번 이동할 때 갈 수 있는 데까지 이동한다."갈 수 있는 데까지"란, 벽('*')을 만나기 전까지 또는 범위를 벗어나기 전까지이다.같은 방향으로 한 칸씩 이동할 때마다, 같은 이동 거리로 저장한다.같은 방향으로 갈 수 있는 데까지는 모두 방문 체크를 했으므로, 다른 방향으로 가는 곳은 이동 거리 +1을 해주면 된다. C++ 소스코드 #include #include using namespace std; struct la..