알고리즘 문제 풀이

최대 4x4 크기의 2차원 배열이 주어지므로 DFS를 이용해 m개의 지점을 순서대로 방문하는 경우를 모두 탐색하여 해결할 수 있을 것이라 생각했다. [ 풀이 방법 ] DFS를 이용해 m개의 지점을 순서대로 방문하는 경우를 모두 탐색 - board 배열을 이용해 벽이 있는 위치는 탐색하지 않도록 구현 - dest 배열을 이용해 방문 지점을 순서대로 저장하고, DFS 과정에서 순서에 맞지 않는 지점이 먼저 탐색될 경우 되돌아 가도록 구현 - visited 배열을 이용해 DFS 과정에서 이미 방문한 위치는 탐색하지 않도록 구현 [ 정답 코드 ] #include #include #include using namespace std; typedef pair Cord; int N, M; vector board; ve..

deque 2개로 1~N번 까지의 컨베이어 벨트와 2N~N+1번 까지의 벨트를 처리하여 구현할 수 있을 것이라 생각했다. [ 풀이 방법 ] 1. 컨베이어 벨트 생성 기능 1. 1~N을 저장하는 deque 1개(dur1), 2N~N+1을 저장하는 deque 1개(dur2)를 이용하여 컨베이어 벨트 각 위치의 내구도를 저장한다. 2. dur1의 front()가 올리는 위치, dur1의 back()이 내리는 위치가 된다. 3. 1~N 위치에 로봇이 있는지 저장하는 deque(robot)을 생성한다. 2. 컨베이어 벨트 회전 기능 - dur1을 pop_back() -> dur2에 push_back() - dur2을 pop_front() -> dur2에 push_front() - robot은 N번 위치에 도달하..

우선순위 큐를 이용해, 택시가 이동한 거리 -> 행 번호 -> 열 번호가 작은 순서로 BFS를 실행하는 방법으로 택시의 이동을 구현해 문제를 해결할 수 있을 것이라 생각했다. [ 풀이 방법 ] 1. 택시 위치에서 승객 위치로 이동하는 기능 - 택시에서 가장 가까운 승객에게 이동한다(거리가 같다면 행번호가 작은 승객, 행번호가 같다면 열번호가 작은 승객에게 이동). - 연료는 이동할 때 1씩 소모되며 연료가 남지 않았다면 이동을 종료한다. 2. 승객 위치에서 목적지 위치로 이동하는 기능 - 승객에서 목적지까지 소모된 연료의 2배를 충전한다. - 연료는 이동할 때 1씩 소모되며 연료가 남지 않았다면 이동을 종료한다. - 목적지 도착과 동시에 연료 바닥난 경우에는 실패로 처리되지 않는다. 3. 목적지에 도달 ..

길이가 N인 좋은 수열들 중 가장 작은 수를 나타내는 수열을 구해야 한다. 이 때, N은 최대 80이 주어지기 때문에 완전 탐색을 이용하여 모든 수열을 찾고 최소값을 갱신하는 방식으로 구현한다면 시간 초과가 발생할 것이다. 따라서 시간복잡도를 줄일 수 있는 방법을 생각해야 한다. 모든 경우를 탐색해야 하는 문제에서 완전 탐색을 사용할 수 없는 경우 보통 DP를 적용할 수 있나 확인하지만 이 문제의 경우 탐색해야하는 수열의 조건이 주어지므로, 모든 경우를 탐색하기보다는 백트래킹을 이용해 제시된 조건에 맞는 수열 중 가장 작은 수열 단 하나를 찾도록 구현하여 시간복잡도를 충분히 줄이고 문제를 해결할 수 있을 것이다. [ 풀이방법 ] 1. 재귀함수를 길이가 N인 수열이 만들어질 때까지 반복하여 호출한다. 2..

다른 삼성 기출 문제들과 비슷한 구현, 시뮬레이션 문제라고 생각해, 시간 초과에는 크게 신경쓰지 않고 접근 방법과 구현 계획을 시간을 들여 확실하게 생각한 뒤 실수하지 않고 정확하게 구현하는데 집중하여 문제를 해결하였다. [ 풀이 방법 ] 1. 번호, 위치, 이동 방향, 방향에 따른 이동 방향 우선순위, 제거되었는지 여부를 멤버 변수로 갖는 상어 구조체를 담는 배열, 2. 상어의 위치를 표시하는 2차원 배열, 3. 냄새를 담을 2차원 배열, 4. 냄새가 없어지기 까지 남은 시간을 저장할 2차원 배열이 필요 struct Shark { int num; int x; int y; int dir; vector priority; bool removed; }; vector board; vector smell; vec..

상어가 더 이상 이동할 수 없을 때까지 물고기를 먹는 모든 조합을 탐색해야 한다. 처음 한 마리를 먹은 후 시작하여 최대 15마리를 추가로 먹을 수 있고, 상어가 이동할 수 있는 경로의 길이는 최대 3이기 때문에 상어가 한 번 이동할 때 경로 상 존재할 수 있는 물고기의 수는 최대 3마리이다. 따라서 물고기의 이동과 상어의 이동을 재귀함수로 구현하여 상어가 더 이상 움직이지 못할 때까지 반복하여 탐색하도록 구현한다면, 물고기의 이동에 15번 x 상어의 이동에 최대 약 400만번(313x 2 x 1)의 연산이 필요하게 되어 시간 초과가 발생하지 않을 것이라 생각하고 문제를 풀었다. [ 풀이 방법 ] 1. 물고기 이동 기능 1. 물고기 크기 순서대로 지정된 방향(상하좌우, 대각선)으로 물고기를 이동한다. -..

최대 반복 횟수는 10000번이고, 탐색해야하는 배열의 크기는 4x6, 6x4이기 때문에 시간복잡도는 크게 신경 쓸 필요없이 구현이 어려운 문제로 생각하고 풀었다. [ 풀이 방법 ] 1. 빨간색 보드에 블록을 놓는 기능 - 빨간색 보드를 2개 만들어 하나는 파란색 보드, 하나는 반시계 방향으로 90도 돌려 초록색 보드를 처리 - 빨간색 보드를 2차원 배열로 만들 필요 없이, 주어진 블록을 파란색 보드나 초록색 보드의 연한색 칸에 놓도록 처리한다. - 초록색 보드에 블록을 놓을 때에는 블록을 90도 돌려서 놓아야 한다. 2. 블록 이동 기능 - 오른쪽으로 이동하는 기능만 구현하면 된다. - 연한색 칸에 놓인 블록을 벽 또는 다른 블록과 만날 때까지 오른쪽으로 이동시킨다. 3. 블록이 한 열에 가득 찼는지 ..

시간 제한이 2초이고, 4개의 말을 10번 움직이는 경우의 수는 410이기 때문에 모든 경우를 탐색하여 문제를 해결할 수 있다. [ 풀이 방법 ] 1. 윷놀이 판 생성 기능 - 4가지 경로를 생성한다. 경로 1: 시작 - 10 - 20 - 30 - 40 - 도착 경로 2: 시작 - 10 - 25 - 40 - 도착 경로 3: 시작 - 10 - 20 - 25 - 40 - 도착 경로 4: 시작 - 10 - 20 - 30 - 25 - 40 - 도착 - 경로의 각 위치에는 점수가 저장된다. vector board[4] = { {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0}, {0, 2, 4, 6, 8, 10, 13..