당신은 로봇이 움직이는 2D 그리드 상에서 최단 경로를 찾는 알고리즘을 개발하고 있습니다. 로봇은 시작 지점 (0, 0)에서 목표 지점 (m, n)으로 이동해야 합니다. 로봇은 오른쪽 방향으로만 움직일 수 있으며, 한 번에 한 칸씩 이동할 수 있습니다. 그리드 상의 각 셀은 장애물일 수도 있어 로봇은 장애물을 피해야 합니다. 이제 로봇의 최단 경로를 찾는 역추적 알고리즘을 구현해야 합니다. 주어진 dp 테이블과 그리드 정보를 이용하여 시작 지점부터 목표 지점까지의 최단 경로를 찾는 함수 traceShortestPath(dp, grid)를 작성해주세요. 함수는 최단 경로에 해당하는 좌표들의 배열을 반환해야 합니다. 함수의 입력: dp: 로봇의 최단 경로를 저장한 DP 테이블 (2D 배열) grid: 장애물..

메모이제이션 테이블은 동적 계획법(Dynamic Programming)에서 중복 계산을 피하기 위해 사용되는 테이블입니다. 동적 계획법은 큰 문제를 작은 하위 문제로 나누어 해결하고, 작은 하위 문제의 해답을 저장하여 중복 계산을 피하는 방법입니다. 메모이제이션 테이블은 이전에 계산한 값을 저장하는 역할을 합니다. 이를 통해 동일한 입력에 대한 계산이 여러 번 필요할 때, 이미 계산된 값을 다시 계산하는 대신 메모이제이션 테이블에서 값을 조회하여 중복 계산을 피할 수 있습니다. 이는 알고리즘의 실행 속도를 향상시키는데 도움이 됩니다. 주로 1차원 배열, 2차원 배열 또는 객체 형태의 메모이제이션 테이블이 사용됩니다. 각 위치에는 하위 문제의 해답이 저장되며, 이를 통해 중복 계산을 효율적으로 피할 수 있..

function quickSort(arr) { if (arr.length

function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while (left

문제: 한 외판원이 N개의 도시를 순회하여 각 도시를 한 번씩 방문한 뒤 다시 시작 도시로 돌아오려고 합니다. 각 도시 간의 이동 거리가 주어질 때, 최단 경로를 찾아 시작 도시로 돌아오는 최소 거리를 구하는 프로그램을 작성하세요. 입력: N: 도시의 수 (2 이상 10 이하의 정수) distance: N x N 크기의 2차원 배열로 표현된 도시 간의 이동 거리. distance[i][j]는 도시 i에서 도시 j로 이동하는데 필요한 거리를 나타냅니다. (1 이상 1,000 이하의 정수) 출력: 시작 도시로 돌아오는 최단 경로의 거리 제약 조건: 외판원은 모든 도시를 한 번씩 방문한 뒤 시작 도시로 돌아와야 합니다. 각 도시 간의 이동 거리는 양수입니다. 시작 도시와 도착 도시는 항상 동일합니다. 도시 간..

여틀왕은 그의 거북이 왕관을 재배치해서 가장 계급이 높은 귀족과 가장 가까운 측근들을 더 위쪽으로 올리고 싶어한다. 쌓여있는 거북이들이 순서를 바꾸는 방법은 거북이 한말리가 원래 자기 위치에서 빠져 나와서 맨 위로 올라가서 자리를 잡는 방법밖에 없다. 거북이 스택의 원래 순서와 새로 만들어져야 할 스택의 순서가 주어졌을때 최소한의 이동 횟수만으로 원래 스택을 새로운 스택으로 재배치할 수 있는 순서를 찾아야 한다. 입력 입력의 첫번째 줄에는 테스트 케이스의 개수를 나타내는 K라는 정수 하나만 들어있다. 각 테스트 케이스는 스택에 들어있는 거북이의 개수를 나타내는 n이라는 정수로 시작되며 그 밑으로 n개의 줄에 걸쳐서 거북이 스택의 원래 배치가 기술된다. 각 줄에는 거북이의 이름이 들어있으며, 맨 윗줄에는 ..

로마의 도르는 견고하게 지어진 것으로 유명하다. 하지만 이렇게 견고한 도로를 만드는 데는 비용이 들게 마련이다. 그래서 자동 사용료 부과 방법을 통해 도로 건설 비용을 회수하기로 했다. CDVII라는 유료 고속도로에서 사용하는 요금 체계를 설명하자면 다음과 같다. 그 도로를 주행하려면 그 주행이 시작된 시각에 따라 주행 거리(킬로미터 단위)당 일정한 요금을 지불해야 한다. 모든 입구와 출구에는 카메라가 장착되어 있어서 들어오고 나가는 차량의 번호판을 기록한다. 매달 그 자동차 소유주에게 (도로에 들어간 시각을 기준으로 결정되는 요금에 따라) 킬로미터 단위로 요금이 부과되는데, 이때 매 주행마다 1달러가 추가되고 매달 2달러의 기본요금이 부과된다. 일련의 번호판 사진이 주어졌을때 한 달 동안의 도로 이용 ..

어떤 구두 수선공에게 N개의 주문이 들어와 있다. 그는 하루에 한 가지 작업만 할 수 있으며 보통 한 작업을 하는데 며칠이 걸린다. i 번째 작업에 대해 Ti(1 ≤Ti≤10,000)라는 정수는 구두 수선공이 작업을 끝내는 데 걸리는 시간이 며칠인지를 나타낸다. 하지만 인기가 좋으면 그만큼의 대가가 따른다. 구두 수선공은 i번째 작업을 시작하기 전까지 지연되는 날 수를 기준으로 하루에 Si(1 ≤Si≤10,000) 센트씩의 벌금을 내기로 했다. 벌금의 총합이 최소가 되게 해주는 작업 순서를 찾아내기 위한 프로그램을 만들어서 구두 수선공을 도와주자 입력 첫 줄에는 테스트 케이스의 개수를 나타내기 위한 양의 정수 한개가 들어가며 그 다음줄은 빈 줄이다. 서로 다른 테스트 케이스 사이에도 빈 줄이 하나씩 들어..

교수들은 각종 업무와 약속으로 가득 찬 복잡한 스케줄 속에서 매우 바쁘게 살아간다. p 교수는 낮잠을 자는걸 좋아하지만 스케줄이 바쁘다 보니 낮잠을 잘 수 있는 시간이 별로 없다. 하지만 p교수는 매일 한 번씩은 낮잠을 자고 싶어한다. 물론 그의 스케줄을 감안해서 될 수 있으면 오래동안 낮잠을 즐길 수 있는 방법을 찾아야 한다. p교수가 최대한 오래동안 낮잠을 잘 수 있는 프로그램을 만들어라. 입력 값 입력은 임의 개수의 테스트 케이스가 입력되며 각 테스트 케이스가 하루를 나타낸다. 각 테스트 케이스 첫번째 줄에는 100이하의 양의 정수 s가 있으며, 이 수는 그날 미리 잡혀있는 약속의 갯수이다. 그 다음 줄 부터 s개의 줄에는 'time1 ~ time2 약속내용' 형식으로 잡혀 있는 약속이 입력되며, ..

문제 n명의 사람들로 구성된 한 그룹이 밤중에 다리를 건너려고 한다. 한 번에 최대 2명까지만 다리를 건널수 있으며 다리 위를 지나가는 사람들은 반드시 플래시를 가지고 가야 한다. 그 n명의 사람들한테는 플래시가 한 개밖에 없기 때문에 다른 사람들이 다리를 건너려면 어떤 식으로든 플래시를 가지고 다시 다리를 건너지 않는 사람들이 있는 곳으로 돌아가는 일을 해야 한다. 사람마다 다리를 건너는 속도가 다른데, 그룹의 속도는 가장 느린 구성원의 속도에 따라 결정된다. 가장 짧은 시간 안에 n명이 모두 다리를 건널 수 있는 방법을 결정해야 한다. 해석 가장 짧은 시간 안에 n명이 모두 다리를 건너는 방법을 결정하기 위해서는 다음과 같은 전략을 사용할 수 있습니다: 사람들을 속도 순으로 정렬합니다. 가장 빠른 두..