코딩 테스트 준비

두 개의 단어 begin, target과 단어의 집합 words가 주어집니다.아래 규칙을 이용해 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾습니다.한 번에 한 개의 알파벳만 바꿀 수 있습니다.words에 있는 단어로만 변환할 수 있습니다.예를 들어

삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는 문제입니다.아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동할 수 있습니다.예를 들어 어떤 칸에서 아래층으로 이동할 때는 바로 아래에 연결된 두 칸 중

계속되는 폭우로 일부 지역이 물에 잠겼습니다.물에 잠기지 않은 지역을 통해 집에서 학교까지 가려고 합니다.집에서 학교까지 가는 길은 m x n 크기의 격자 모양으로 나타낼 수 있습니다.집의 좌표: (1, 1)학교의 좌표: (m, n)이동 방향: 오른쪽, 아래쪽격자의 크

모든 빈칸을 채워보는 대신, 기차가 실제로 지나가는 경로만 따라가며 탐색한다.기차는 항상 현재 칸에 특정 방향으로 들어온다.따라서 빈칸에 선로를 놓을 때도 모든 선로를 볼 필요 없이, 현재 들어온 방향과 연결되는 선로만 후보가 된다.예를 들어 현재 왼쪽에서 들어왔다면,

예제 2번을 살펴보자.초기 큐는 다음과 같다.먼저 (0, 1)을 꺼낸다.큐 안에 우선순위 9가 있으므로 다시 뒤에 넣는다.마찬가지로 (1, 1)도 뒤로 간다.이제 (2, 9)를 꺼낸다.큐 안에 더 높은 우선순위가 없으므로 실행된다.실행 순서:이후 나머지 우선순위는 모두

마을의 집들이 원형으로 배치되어 있다.인접한 두 집을 동시에 털면 경보가 울리기 때문에,서로 인접하지 않은 집들만 선택해서 털어야 한다.훔칠 수 있는 돈의 최댓값을 구하는 문제이다.이 문제는 대표적인 DP(동적 계획법) 문제인"House Robber" 유형이다.하지만

n명의 사람이 입국심사를 받아야 하고, 각 심사관이 한 명을 처리하는 데 걸리는 시간이 times로 주어진다.모든 사람이 심사를 완료하는 데 필요한 최소 시간을 구하는 문제다.처음에는 "어떤 사람을 어느 심사대로 보낼지"를 생각하기 쉽다. 하지만 사람 수 n은 최대 1

메시지의 일부 구간에 스포일러 방지 기능이 적용되어 있습니다.사용자는 메시지의 왼쪽에서 오른쪽 순서로 스포일러 구간을 클릭해 단어를 공개합니다.이때 공개되는 스포일러 단어 중 중요한 단어의 개수를 구해야 합니다.중요한 단어가 되려면 다음 조건을 모두 만족해야 합니다.스

문제 요약 A도둑과 B도둑이 모든 물건을 훔치려고 한다. 각 물건을 훔칠 때는 둘 중 한 명이 훔쳐야 하며, 누가 훔치느냐에 따라 남기는 흔적의 개수가 다르다. A도둑이 물건 i를 훔치면 infoi개의 A 흔적을 남긴다. B도둑이 물건 i를 훔치면 infoi개의

게임 캐릭터는 붕대 감기 기술을 사용해 체력을 회복할 수 있다.붕대 감기는 일정 시간 동안 유지되며, 매초 체력을 회복한다.붕대 감기 정보는 다음과 같다.각 값의 의미는 다음과 같다.캐릭터는 매초 x만큼 체력을 회복한다.그리고 t초 연속으로 붕대 감기에 성공하면 추가로

N x N 크기의 격자에 인형들이 쌓여 있고, 사용자는 크레인을 특정 열로 이동시켜 가장 위에 있는 인형을 뽑습니다.뽑은 인형은 바구니에 순서대로 쌓입니다. 이때 바구니의 맨 위에 있는 인형과 새로 뽑은 인형의 모양이 같다면, 두 인형은 터지면서 사라집니다.모든 크레인

n x m 크기의 땅이 2차원 배열 land로 주어집니다.1은 석유가 있는 칸입니다.0은 빈 땅입니다.상, 하, 좌, 우로 연결된 석유 칸들은 하나의 석유 덩어리입니다.시추관은 세로 방향으로 열 하나를 끝까지 관통합니다. 어떤 열에 시추관을 설치했을 때, 그 열이 하나

물류창고에는 n x m개의 컨테이너가 놓여 있고, 각 컨테이너는 알파벳 대문자로 종류가 구분된다.출고 요청은 두 가지 방식으로 들어온다.요청 문자열의 길이가 1이면 지게차를 사용한다.요청 문자열의 길이가 2이면 크레인을 사용한다.예를 들어 요청이 "A"라면 지게차 요청

coding test

coding test

처음 문자열은 모두 A로 이루어져 있다.예를 들어 만들고자 하는 이름이 세 글자라면 처음 상태는 다음과 같다.네 글자라면 다음과 같다.조이스틱을 움직여 원하는 이름을 만들어야 한다.조이스틱 조작은 두 종류로 나눌 수 있다.현재 위치의 알파벳을 바꾼다.A에서 위로 움직이

coding test

coding test

문제 요약 퍼즐을 순서대로 풀어야 합니다. 각 퍼즐에는 난이도 diffs[i]와 소요 시간 times[i]가 있습니다. 플레이어의 숙련도를 level이라고 할 때, 퍼즐을 푸는 규칙은 다음과 같습니다. diffs[i] level이면 diffs[i] - level번 틀립니다. 한 번 틀릴 때마다 현재 퍼즐 시간 times[i]와 이전 퍼즐 시간 tim...

문제 요약 시침, 분침, 초침이 일정한 속도로 움직이는 아날로그시계가 있습니다. 초침이 시침 또는 분침과 겹칠 때마다 알람이 한 번 울립니다. 단, 0시 정각이나 12시 정각처럼 세 바늘이 동시에 겹치는 순간에는 알람이 두 번이 아니라 한 번만 울립니다. 주어진 시작 시각부터 종료 시각까지 알람이 울리는 횟수를 구해야 합니다. 시작 시각과 종료 시각...

문제 요약 발전소는 1층부터 h층까지 존재한다. 각 층은 모두 같은 구조의 n x m 격자로 이루어져 있다. 격자의 각 칸은 다음 중 하나다. .: 이동할 수 있는 통로 #: 이동할 수 없는 폐쇄 구역 @: 엘리베이터 기술자는 상하좌우로 한 칸 이동할 때마다 1초를 사용한다. 다른 층으로 이동하려면 반드시 엘리베이터를 이용해야 하며, 한 층을 이...

문제 요약 1번부터 n번까지의 스테이지를 순서대로 모두 해결해야 한다. 각 스테이지는 사용한 힌트권 개수에 따라 해결 비용이 달라진다. 힌트권을 많이 사용할수록 스테이지 해결 비용은 감소한다. 위 값은 i + 1번 스테이지에서 힌트권을 j개 사용했을 때의 해결 비용을 의미한다. 각 힌트권에는 사용할 수 있는 스테이지 번호가 정해져 있다. 예를 들...

문제 핵심 주문은 다음 순서로 정렬된다. 이 순서는 알파벳을 1~26으로 표현하는 숫자 순서와 같다. 따라서 주문을 번호로 변환하면 문자열 대신 숫자로 문제를 해결할 수 있다. 왜 <=로 비교할까? 삭제 번호가 목표 번호와 같은 경우에도 목표를 미뤄야 한다. 예를 들어 삭제 전 첫 번째 주문은 "a"다. 처음 목표는 1이지만 1번 주문이 삭제...

문제 요약 물류센터에는 번호가 붙은 여러 포인트가 존재한다. 각 로봇은 정해진 포인트들을 순서대로 방문한다. 모든 로봇은 0초에 동시에 출발하며, 1초마다 상하좌우 중 한 방향으로 한 칸 이동한다. 다음 포인트까지는 항상 최단 경로로 이동한다. 최단 경로가 여러 개라면 다음 우선순위를 따른다. 같은 시간에 같은 좌표에 로봇이 2대 이상 있다면 해...

문제 요약 루트가 정해지지 않은 여러 개의 트리, 즉 포레스트가 주어진다. 각 노드는 서로 다른 번호를 가지고 있다. 루트를 정하면 각 노드의 자식 수가 결정되고, 노드 번호와 자식 수의 홀짝 관계에 따라 노드의 종류가 나뉜다. 노드 종류 홀수 노드 짝수 노드 0은 짝수로 본다. 역홀수 노드 역짝수 노드 홀수 노드와 짝수 노드로만 구성된 ...

coding test

문제 요약 무인도에 갇힌 사람들을 구명보트로 구출해야 한다. 구명보트에는 다음 제한이 있다. 한 번에 최대 2명까지 탈 수 있다. 보트마다 무게 제한이 있다. 사람들의 몸무게 배열 people과 구명보트의 무게 제한 limit가 주어졌을 때, 모든 사람을 구출하기 위해 필요한 구명보트의 최소 개수를 구해야 한다. 핵심 아이디어 이 문제는 그리디로...

문제 요약 하드디스크는 한 번에 하나의 작업만 수행할 수 있다. 각 작업은 다음 정보를 가진다. 하드디스크가 비어 있고 대기 큐에 작업이 있다면, 우선순위가 가장 높은 작업을 꺼내 실행한다. 우선순위는 다음 순서로 결정된다. 소요 시간이 짧은 작업 요청 시각이 빠른 작업 작업 번호가 작은 작업 작업을 한 번 시작하면 끝날 때까지 중단하지 않는다....

문제 설명 N × M 크기의 게임 맵이 주어집니다. 1 : 이동 가능한 칸 0 : 벽 캐릭터는 (0, 0)에서 출발하여 (N-1, M-1) 위치까지 이동해야 합니다. 상하좌우로만 이동할 수 있으며, 지나가야 하는 칸의 최소 개수를 구하는 문제입니다. 도착할 수 없는 경우에는 -1을 반환해야 합니다. 풀이 아이디어 이 문제는 최단 거리를 구해야...

문제 요약 m x n 크기의 사막 격자가 주어진다. 이 격자 안에 세로 h, 가로 w 크기의 선인장 구역을 하나 정해야 한다. 선인장 구역은 격자 축에 맞춘 연속된 직사각형이다. 비는 drops 배열에 주어진 순서대로 격자의 칸에 떨어진다. 선인장 구역 안에 포함된 칸 중 하나라도 처음 비를 맞는 순간이 해당 선인장 구역이 처음 비를 맞는 시각이다...

문제 요약 숫자 야구는 서로 다른 숫자 4개로 이루어진 비밀번호를 맞히는 게임이다. 비밀번호는 다음 조건을 만족한다. 숫자는 1부터 9까지 사용한다. 같은 숫자는 중복해서 사용할 수 없다. 총 4자리 숫자다. 예를 들어 가능한 비밀번호는 다음과 같다. 하지만 다음은 불가능하다. 우리는 submit() 함수를 호출해 숫자를 제출할 수 있다. 제...

문제 핵심 이 문제는 출발점 (0, 0)에서 도착점 (n - 1, n - 1)까지 이동하면서 최소 비용으로 경주로를 건설하는 문제다. 이동은 상하좌우 4방향으로 가능하고, 벽이 있는 칸은 지나갈 수 없다. 도로 건설 비용은 다음과 같다. 직선 도로: 100원 코너: 500원 방향을 유지해서 이동하면 직선 도로만 추가되므로 100원이 든다. 방향...

문제 요약 채용 설명회에는 n명의 멘토가 있고, 상담 유형은 1번부터 k번까지 존재한다. 각 멘토는 하나의 상담 유형만 담당할 수 있다. 각 상담 유형에는 최소 1명 이상의 멘토를 배정해야 한다. 참가자가 상담을 요청하면 다음 규칙으로 상담이 진행된다. 해당 상담 유형을 담당하는 멘토 중 빈 멘토가 있으면 바로 상담을 시작한다. 모든 멘토가 상담 ...

문제 요약 자동차 실내온도를 제어하는 에어컨 시스템이 있다. 현재 0분의 실내온도는 실외온도와 같다. 승객이 탑승 중인 시간에는 실내온도가 항상 쾌적 범위인 t1 ~ t2 사이에 있어야 한다. 에어컨은 켜거나 끌 수 있고, 켜져 있을 때는 희망온도를 설정할 수 있다. 에어컨 동작 규칙은 다음과 같다. 에어컨이 켜져 있는 경우 실내온도와 희망온...

문제 요약 n명의 권투 선수가 있다. 경기 결과는 [A, B] 형태로 주어진다. 이는 다음 의미다. 권투 실력에는 모순이 없다고 가정한다. 즉, A가 B보다 강하고 B가 C보다 강하다면 A는 C보다 강하다고 볼 수 있다. 목표는 주어진 경기 결과를 바탕으로 정확한 순위를 알 수 있는 선수의 수를 구하는 것이다. 핵심 아이디어 어떤 선수의 정...

문제 요약 루트 노드, 분배 노드, 리프 노드로 이루어진 트리를 구성해야 한다. 루트 노드는 자식 노드를 정확히 1개 가진다. 루트가 아닌 노드는 다음 중 하나다. 자식 노드가 0개인 리프 노드 자식 노드가 2개인 분배 노드 자식 노드가 3개인 분배 노드 분배 노드는 최대 dist_limit개까지 사용할 수 있다. 또한 같은 깊이에 있는 분배 노...

문제 요약 일렬로 나열된 풍선들이 있고, 각 풍선에는 서로 다른 숫자가 적혀 있다. 풍선을 터트릴 때는 인접한 두 풍선 중 하나를 선택해 터트릴 수 있다. 단, 더 작은 번호의 풍선을 터트리는 행동은 전체 과정에서 최대 1번만 가능하다. 이 규칙을 지키면서 마지막까지 남을 수 있는 풍선의 개수를 구해야 한다. 핵심 아이디어 어떤 풍선 a[i]가 마...

문제 요약 거슬러 줘야 하는 금액 n과 사용할 수 있는 화폐 단위 money가 주어진다. 각 화폐는 무한히 사용할 수 있으며, n원을 만드는 방법의 수를 구해야 한다. 정답이 커질 수 있으므로 1,000,000,007로 나눈 나머지를 반환한다. 핵심 아이디어 이 문제는 동전으로 특정 금액을 만드는 조합의 수를 구하는 문제다. 중요한 점은 순서가...

문제 요약 각 부서가 물품 구매에 필요한 금액을 신청했다. 전체 예산 budget 안에서 최대한 많은 부서를 지원해야 한다. 단, 한 부서를 지원하려면 해당 부서가 신청한 금액을 전부 지원해야 하며, 일부 금액만 지원할 수는 없다. 부서별 신청 금액 배열 d와 전체 예산 budget이 주어졌을 때, 지원 가능한 부서의 최대 개수를 구해야 한다. 핵심...

문제 요약 N개의 아파트가 일렬로 있고, 일부 아파트에는 이미 기지국이 설치되어 있다. 기지국 하나는 설치된 위치를 기준으로 왼쪽 W칸, 오른쪽 W칸까지 전파를 전달할 수 있다. 이미 설치된 기지국으로 전파가 닿지 않는 아파트가 있을 때, 모든 아파트에 전파가 닿도록 추가로 설치해야 하는 기지국의 최소 개수를 구해야 한다. 핵심 아이디어 기지국 ...

문제 요약 n x m 크기의 격자에서 시작 위치 (x, y)에서 탈출 위치 (r, c)까지 이동해야 한다. 이때 다음 조건을 만족해야 한다. 격자 밖으로 나갈 수 없다. 정확히 k번 이동해야 한다. 같은 칸을 여러 번 방문할 수 있다. 가능한 경로 중 문자열이 사전순으로 가장 빠른 경로를 반환해야 한다. 불가능하면 "impossible"을 반환한다....

문제 요약 n x m 격자판이 주어진다. 각 칸에는 현재 보이는 값 visiblei와 숨겨진 값 hiddeni가 있다. 한 번의 행동으로 하나의 행 또는 하나의 열 전체를 뒤집을 수 있고, 행동할 때마다 비용 k가 든다. 행과 열을 원하는 만큼 뒤집은 뒤, (1, 1)에서 (n, m)까지 이동한다. 이동 조건은 다음과 같다. 상하좌우 인접한 칸...

문제 요약 이모티콘마다 할인율을 정해 판매할 수 있다. 할인율은 다음 네 가지 중 하나다. 각 사용자는 다음 기준을 가진다. 자신의 기준 할인율 이상인 이모티콘만 구매한다. 구매 금액 합이 자신의 기준 가격 이상이면 구매를 취소하고 이모티콘 플러스에 가입한다. 목표는 다음 우선순위를 따른다. 이모티콘 플러스 가입자 수를 최대화한다. 가입자 수가 ...

문제 요약 1부터 n까지의 카드가 한 장씩 있고, 카드를 뽑는 순서가 cards로 주어진다. 처음에는 n / 3장의 카드를 가지고 시작한다. 이후 매 라운드마다 카드 2장을 뽑고, 다음 라운드로 넘어가기 위해서는 합이 n + 1이 되는 카드 2장을 내야 한다. 라운드에서 새로 뽑은 카드는 카드 한 장당 동전 1개를 사용해야 가질 수 있다. 게임에서...

문제 요약 n x m 크기의 퍼즐판에 빨간 수레와 파란 수레가 있다. 각 수레는 자신의 시작 칸에서 출발해 자신의 도착 칸까지 이동해야 한다. 매 턴마다 두 수레는 동시에 움직인다. 단, 이미 도착 칸에 도착한 수레는 더 이상 움직이지 않고 그 자리에 고정된다. 이동할 때는 다음 규칙을 지켜야 한다. 격자 밖으로 나갈 수 없다. 벽으로 이동할 수 ...

문제 요약 5개의 대기실이 주어진다. 각 대기실은 5 x 5 크기이며, 각 칸은 다음 중 하나다. 응시자들 사이의 맨해튼 거리가 2 이하이면 거리두기 위반이다. 단, 두 응시자 사이가 파티션으로 막혀 있다면 허용된다. 각 대기실별로 거리두기를 지키고 있으면 1, 위반이 있으면 0을 반환해야 한다. 핵심 아이디어 대기실 크기는 항상 5 x 5로...

문제 요약 진열대에 보석들이 일렬로 놓여 있다. 어피치는 특정 연속 구간의 보석을 모두 구매하려고 한다. 목표는 다음과 같다. 모든 종류의 보석을 적어도 1개 이상 포함해야 한다. 가능한 가장 짧은 구간을 찾아야 한다. 가장 짧은 구간이 여러 개라면 시작 번호가 가장 작은 구간을 선택한다. 반환값은 1번부터 시작하는 진열대 번호 기준의 [시작, ...

문제 요약 이벤트 응모자 아이디 목록 userid와 불량 사용자 패턴 목록 bannedid가 주어진다. 불량 사용자 패턴에는 ` 문자가 포함되어 있으며, `는 어떤 문자 하나와도 매칭될 수 있다. 각 불량 사용자 패턴에 응모자 아이디를 하나씩 매칭해야 한다. 단, 같은 응모자 아이디가 제재 아이디 목록에 중복으로 들어갈 수 없다. 최종 제재 아이...

문제 요약 길이가 같은 두 큐 queue1, queue2가 주어진다. 한 번의 작업은 다음과 같다. 이 작업을 반복해서 두 큐의 원소 합을 같게 만들어야 한다. 가능한 최소 작업 횟수를 반환하고, 불가능하면 -1을 반환한다. 핵심 아이디어 두 큐의 전체 합을 total이라고 하자. 두 큐의 합이 같아지려면 각 큐의 합은 반드시 다음 값이 되어야...

문제 요약 n개의 주사위가 주어진다. A가 먼저 n / 2개의 주사위를 고르고, B는 남은 n / 2개의 주사위를 가진다. 각자 가진 주사위를 모두 굴려 나온 수의 합으로 승부한다. 목표는 A가 승리할 확률이 가장 높아지는 주사위 조합을 찾는 것이다. 정답은

문제 요약 현재 알고력 alp와 코딩력 cop가 주어진다. 문제를 풀기 위해서는 각 문제마다 요구하는 알고력과 코딩력이 필요하다. 능력치를 올리는 방법은 세 가지다. 알고리즘 공부를 해서 알고력 1 증가: 시간 1 코딩 공부를 해서 코딩력 1 증가: 시간 1 현재 풀 수 있는 문제를 풀어서 알고력과 코딩력 증가: 문제별 소요 시간 목표는 모든 문...

문제 요약 이진 트리 형태의 초원에 양과 늑대가 있다. 루트 노드에서 시작해 노드를 방문하면서 양을 최대한 많이 모아야 한다. 각 노드를 방문하면 해당 노드의 양 또는 늑대가 따라온다. 단, 어느 순간이라도 늑대 수가 양 수 이상이 되면 양이 모두 잡아먹히므로 그 경로는 더 이상 진행할 수 없다. 목표는 조건을 지키면서 모을 수 있는 양의 최대 ...

문제 요약 N x M 크기의 게임 맵에 건물이 있고, 각 칸에는 내구도가 있다. 스킬은 두 종류다. 각 스킬은 항상 직사각형 범위에 적용된다. 모든 스킬을 적용한 뒤 내구도가 1 이상인 건물의 개수를 구해야 한다. 핵심 아이디어 스킬마다 직사각형 내부의 모든 칸을 직접 갱신하면 시간이 너무 오래 걸린다. 예를 들어 N, M, skill의 개수...

문제 요약 윗변의 길이가 n, 아랫변의 길이가 n + 1인 삼각형 사다리꼴이 있다. 각 위치의 위쪽에는 tops[i]의 값에 따라 삼각형이 하나 더 붙을 수 있다. tops[i] == 1: 위쪽 삼각형이 붙어 있다. tops[i] == 0: 위쪽 삼각형이 붙어 있지 않다. 이 모양을 정삼각형 타일 또는 정삼각형 2개를 붙인 마름모 타일로 채우는 경...

문제 요약 출입구에서 출발해 산봉우리 하나를 방문한 뒤, 출발했던 출입구로 돌아오는 등산코스를 정해야 한다. 등산코스의 intensity는 코스에 포함된 등산로 중 가장 긴 이동 시간이다. 따라서 다음 조건을 만족하는 결과를 구해야 한다. intensity가 가장 작은 산봉우리를 선택한다. 최소 intensity가 같은 산봉우리가 여러 개라면 번호가...

문제 요약 n x n 크기의 벽면에 기둥과 보를 설치하거나 삭제하는 명령이 주어진다. 각 구조물은 다음과 같이 표현된다. [x, y, 0]: (x, y)에서 위쪽으로 설치된 기둥 [x, y, 1]: (x, y)에서 오른쪽으로 설치된 보 작업을 수행한 뒤 모든 구조물이 설치 규칙을 만족해야 한다. 규칙을 위반하는 작업은 무시하고, 모든 명령을 처리한 ...

문제 요약 동영상 재생기는 세 가지 기능을 지원한다. prev: 현재 위치에서 10초 전으로 이동 next: 현재 위치에서 10초 후로 이동 오프닝 건너뛰기: 현재 위치가 오프닝 구간 안이면 오프닝 끝 위치로 이동 입력으로는 다음 값들이 주어진다. video_len: 동영상 길이 pos: 현재 재생 위치 op_start: 오프닝 시작 시각 op_en...

문제 요약 길이가 n인 원형 외벽에 여러 개의 취약 지점이 있다. 각 친구는 1시간 동안 이동할 수 있는 거리가 서로 다르며, 취약 지점 중 원하는 곳에서 출발해 시계 방향이나 반시계 방향으로 이동할 수 있다. 모든 취약 지점을 점검하기 위해 필요한 친구 수의 최솟값을 구해야 한다. 모든 친구를 투입해도 전체 취약 지점을 점검할 수 없다면 -1을 ...

문제 요약 n개의 섬과 섬 사이에 다리를 건설하는 비용이 주어진다. 직접 연결되어 있지 않더라도 다른 섬을 거쳐 이동할 수 있으면 서로 통행 가능한 것으로 본다. 모든 섬이 서로 통행할 수 있도록 다리를 건설할 때 필요한 최소 비용을 구해야 한다. 핵심 아이디어 모든 섬을 연결하면서 전체 비용을 최소로 만들어야 하므로 최소 신장 트리를 구하는 문...

문제 요약 n명의 사람이 번호 순서대로 영어 끝말잇기를 진행한다. 끝말잇기에서는 다음 규칙을 지켜야 한다. 주어진 단어 목록에서 가장 먼저 규칙을 위반한 사람의 번호와 그 사람의 차례를 구해야 한다. 탈락자가 없다면 [0, 0]을 반환한다. 핵심 아이디어 단어를 순서대로 확인하면서 다음 두 가지를 검사한다. 이전에 등장한 단어를 빠르게 확인하...

문제 요약 크기가 50 × 50인 표가 있고, 처음에는 모든 셀이 비어 있다. 표에는 다음 명령을 수행할 수 있다. PRINT 명령의 결과를 순서대로 배열에 담아 반환해야 한다. 핵심 아이디어 병합된 셀들은 어느 위치를 선택하더라도 같은 값에 접근해야 한다. 따라서 병합된 셀들을 하나의 집합으로 관리하는 Union-Find 자료구조를 사용한다....

문제 요약 각 로그에는 요청의 응답 완료 시각과 처리 시간이 주어진다. 모든 요청의 처리 구간을 구한 뒤, 임의의 시점부터 시작하는 1초 구간에 포함되는 요청 수의 최댓값을 반환해야 한다. 요청은 1초 구간 안에서 완료될 필요가 없다. 처리 구간과 1초 구간이 조금이라도 겹치면 해당 요청은 처리량에 포함된다. 핵심 아이디어 모든 시각을 직접 확인할...

문제 요약 각 칸에 S, L, R 중 하나가 적힌 격자가 있다. 빛은 각 칸의 문자에 따라 다음과 같이 이동한다. 빛이 격자의 끝을 벗어나면 같은 행 또는 열의 반대편 끝으로 이동한다. 격자에서 만들 수 있는 모든 빛의 경로 사이클 길이를 구한 뒤 오름차순으로 정렬해 반환해야 한다. 핵심 아이디어 빛의 상태는 현재 위치만으로 결정되지 않는다. ...

문제 요약 동영상의 전체 재생 시간과 여러 시청자의 재생 구간이 주어진다. 정해진 길이의 광고를 동영상에 삽입할 때, 광고가 재생되는 구간의 누적 시청 시간이 최대가 되는 시작 시각을 구해야 한다. 누적 시청 시간이 같은 구간이 여러 개라면 가장 빠른 시작 시각을 반환한다. 시간은 다음 형식의 문자열로 주어진다. 핵심 아이디어 각 시청 기록의 모...

문제 요약 크기가 2 × 1인 직사각형 타일을 가로 또는 세로로 배치해 크기가 3 × n인 바닥을 빈틈없이 채우려고 한다. 바닥을 채울 수 있는 모든 경우의 수를 구하고, 결과를 1,000,000,007로 나눈 나머지를 반환해야 한다. 핵심 아이디어 이 문제는 작은 너비의 결과를 이용해 더 큰 너비의 결과를 구하는 동적 계획법 문제다. 먼저 3 ×...

문제 요약 숫자가 적힌 N개의 스티커가 원형으로 연결되어 있다. 하나의 스티커를 뜯으면 양옆에 인접한 스티커는 사용할 수 없다. 서로 인접하지 않은 스티커들을 선택해 얻을 수 있는 숫자 합의 최댓값을 구해야 한다. 원형 구조이므로 배열의 첫 번째 스티커와 마지막 스티커도 서로 인접해 있다. 핵심 아이디어 스티커가 일렬로 놓여 있다면 각 위치에서 ...

문제 요약 각 정점에 정수 가중치가 부여된 트리가 주어진다. 연결된 두 정점을 선택하여 한쪽 가중치는 1 증가시키고, 다른 쪽 가중치는 1 감소시키는 연산을 수행할 수 있다. 모든 정점의 가중치를 0으로 만들 수 없다면 -1, 가능하다면 필요한 최소 연산 횟수를 반환해야 한다. 제한사항에서 확인할 점 정점 수는 최대 300,000개이다. 트리의 ...

문제 요약 n개의 등대와 n - 1개의 뱃길이 있다. 모든 등대는 서로 이동할 수 있도록 연결되어 있으므로 전체 구조는 트리다. 각 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있어야 한다. 모든 뱃길이 이 조건을 만족하도록 켜야 하는 등대 수의 최솟값을 구해야 한다. 핵심 아이디어 각 뱃길을 하나의 간선으로 생각하면 문제의 조건은 다음과 같다....

문제 요약 두 종류의 타일을 회전해 사용하면서 크기가 3 × n인 판을 빈틈없이 채우려고 한다. 타일의 개수에는 제한이 없으며, 판을 채울 수 있는 모든 경우의 수를 구해야 한다. n은 최대 100,000이므로 결과를 1,000,000,007로 나눈 나머지를 반환한다. 핵심 아이디어 작은 너비의 판을 채우는 결과를 이용해 더 큰 너비의 판을 채우...

문제 요약 윗변의 길이가 n, 아랫변의 길이가 n + 1인 삼각형 사다리꼴이 있다. 각 위치의 위쪽에는 tops[i]의 값에 따라 삼각형이 하나 더 붙을 수 있다. tops[i] == 1: 위쪽 삼각형이 붙어 있다. tops[i] == 0: 위쪽 삼각형이 붙어 있지 않다. 이 모양을 정삼각형 타일 또는 정삼각형 2개를 붙인 마름모 타일로 채우는 경...

문제 요약 0과 1로 이루어진 문자열에서 다음 동작을 원하는 만큼 수행할 수 있다. 각 문자열을 만들 수 있는 문자열 중 사전순으로 가장 앞서는 문자열로 변환해야 한다. 문자열 배열 s의 각 원소에 대해 변환 결과를 배열에 담아 반환한다. 핵심 아이디어 문제를 다음 두 단계로 나누어 생각할 수 있다. 문자열에서 모든 "110"을 제거할 때는 스...

문제 요약 (와 )로만 이루어진 균형잡힌 괄호 문자열 p가 주어진다. 문제에서 제시한 변환 과정을 그대로 수행해 문자열을 올바른 괄호 문자열로 만들어야 한다. 두 용어의 차이는 다음과 같다. 예를 들어 다음 문자열은 균형잡혀 있지만 올바르지는 않다. 다음 문자열은 균형잡혀 있으면서 올바르다. 핵심 아이디어 문제에서 제시한 알고리즘을 재귀 함수...

문제 요약 n행 m열 격자의 모든 칸은 공의 시작점이 될 수 있다. 공은 쿼리를 순서대로 수행하며, 격자 밖으로 나가려고 하면 경계에서 멈춘다. 모든 가능한 시작점 중에서 모든 쿼리를 수행한 뒤 (x, y)에 도착하는 시작점의 개수를 구해야 한다. 쿼리의 의미는 다음과 같다. 핵심 아이디어 모든 시작점에서 쿼리를 정방향으로 수행하면 최대 n x ...

문제 요약 영문 대문자로 이루어진 문자열을 LZW 압축 알고리즘으로 압축한다. LZW 압축은 다음 과정을 반복한다. 출력된 사전 색인 번호들을 배열에 담아 반환해야 한다. 핵심 아이디어 사전에 등록된 문자열과 색인 번호를 딕셔너리로 관리한다. 현재까지 찾은 가장 긴 문자열을 current에 저장하고, 다음 글자를 붙인 candidate가 사전에...

문제 요약 여러 개의 행렬을 순서는 유지한 채 모두 곱하려고 한다. 행렬을 곱하는 괄호 위치에 따라 필요한 곱셈 연산 횟수가 달라진다. 모든 행렬을 곱하기 위한 최소 연산 횟수를 구해야 한다. 크기가 a x b인 행렬과 b x c인 행렬을 곱하는 비용은 다음과 같다. 핵심 아이디어 행렬의 순서는 고정되어 있으므로, 어떤 구간을 중간 어디에서 두...

문제 요약 오픈채팅방의 기록에는 다음 세 가지 명령이 들어 있다. 입장과 퇴장은 관리자 메시지를 남긴다. 닉네임이 변경되면 과거에 출력된 메시지의 닉네임도 모두 최신 닉네임으로 바뀐다. 모든 기록을 처리한 뒤 관리자에게 보여 줄 최종 메시지 배열을 반환해야 한다. 핵심 아이디어 메시지의 순서와 닉네임 정보는 분리해서 관리한다. 각 사용자 ID의...

문제 요약 두 사람이 같은 출발 지점 s에서 택시를 타고 각자의 도착 지점 a, b로 이동한다. 두 사람은 경로 일부를 합승할 수 있고, 중간 지점에서 각자 택시를 따로 탈 수 있다. 두 사람이 모두 귀가하기 위한 최소 택시 요금을 구해야 한다. 간선은 양방향이며, 같은 경로를 반대 방향으로 이동해도 요금은 같다. 핵심 아이디어 합승을 끝내는 ...

문제 요약 직사각형 공간에 앞면과 뒷면이 있는 동전이 놓여 있다. 한 번의 동작으로 행 하나 또는 열 하나에 있는 모든 동전을 뒤집을 수 있다. 초기 상태 beginning을 목표 상태 target으로 만들기 위해 필요한 최소 뒤집기 횟수를 구해야 한다. 목표 상태를 만들 수 없다면 -1을 반환한다. 핵심 아이디어 각 칸에서 초기 상태와 목표 ...

문제 요약 상자에는 1부터 N까지의 숫자가 하나씩 적힌 카드가 무작위로 들어 있다. 어떤 상자를 열면 카드에 적힌 번호의 상자를 다음으로 열어야 한다. 이미 열었던 상자를 다시 열려고 하면 하나의 상자 그룹이 완성된다. 첫 번째 그룹과 겹치지 않는 상자들 중 하나를 선택해 두 번째 그룹을 만들고, 두 그룹의 크기를 곱한 값이 점수다. 만들 수 있는...

문제 요약 일렬로 놓인 토핑 배열에서 한 곳을 잘라 두 조각으로 나눈다. 두 조각에 포함된 토핑의 종류 수가 같으면 공평하게 자른 것으로 본다. 공평하게 롤케이크를 자를 수 있는 위치의 개수를 구해야 한다. 핵심 아이디어 절단 위치를 왼쪽에서 오른쪽으로 한 칸씩 옮긴다. 각 위치에서 다음 두 값을 알아야 한다. 왼쪽 조각은 지금까지 등장한 토핑...

문제 요약 여러 부대원이 서로 다른 지역에서 강철부대가 있는 목적지로 복귀하려고 한다. 모든 길은 왕복할 수 있고, 길 하나를 지나는 시간은 모두 1이다. 각 출발 지역에서 목적지까지 복귀하는 최단시간을 구해야 한다. 목적지까지 도달할 수 없는 지역은 -1을 반환한다. 핵심 아이디어 각 부대원의 출발 지역마다 BFS를 수행하면 sources의 원...

문제 요약 파일명은 HEAD, NUMBER, TAIL 세 부분으로 나뉜다. 파일명을 다음 기준으로 정렬해야 한다. 핵심 아이디어 파일명 전체를 문자열 기준으로 정렬하면 숫자의 자릿수 때문에 자연스러운 순서가 만들어지지 않는다. 따라서 파일명에서 HEAD와 NUMBER를 분리한 뒤 정렬 키로 사용한다. TAIL은 정렬 기준에 포함되지 않는다. 파...

문제 요약 다단계 판매 조직에서 판매원이 칫솔을 판매하면 판매 이익의 10%를 추천인에게 전달하고, 나머지는 자신이 가진다. 추천인도 전달받은 금액의 10%를 자신의 추천인에게 전달한다. 전달할 금액이 1원 미만이면 더 이상 분배하지 않고 현재 판매원이 전부 가진다. 모든 판매 기록을 처리한 뒤 enroll 순서에 맞춰 각 판매원의 최종 이익을 반환해...

문제 요약 디딤돌을 밟을 때마다 해당 디딤돌의 숫자가 1씩 감소한다. 숫자가 0인 디딤돌은 밟을 수 없으며, 친구는 최대 k칸까지 건너뛸 수 있다. 모든 친구는 한 명씩 순서대로 징검다리를 건넌다. 최대 몇 명의 친구가 건널 수 있는지 구해야 한다. 핵심 관찰 어떤 인원 x명이 건널 수 있다면, 그보다 적은 인원도 반드시 건널 수 있다. 반대로 ...

문제 요약 셔틀은 09:00부터 총 n회, t분 간격으로 도착한다. 한 셔틀에는 최대 m명의 크루가 탑승할 수 있다. 크루는 도착 시각 순서대로 탑승하며, 콘은 같은 시각에 도착한 다른 크루보다 항상 뒤에 선다. 콘이 마지막 셔틀까지 포함해 무사히 탑승할 수 있는 가장 늦은 도착 시각을 구해야 한다. 핵심 아이디어 콘이 탑승할 수 있는 가장 늦은 ...

문제 요약 열쇠의 돌기(1)를 자물쇠의 홈(0)에 맞춰 자물쇠를 열어야 한다. 열쇠는 90도 단위로 회전하고 모든 위치로 이동할 수 있다. 자물쇠 영역 안에서는 다음 조건을 만족해야 한다. 자물쇠의 홈과 열쇠의 돌기가 만나야 한다. 자물쇠의 돌기와 열쇠의 돌기가 만나면 안 된다. 자물쇠의 모든 칸이 빈 곳 없이 채워져야 한다. 조건을 만족하는 회전...

문제 요약 각 노드는 서로 다른 x 좌표와 y 좌표를 가진다. 트리는 다음 조건을 만족해야 한다. 부모의 y 좌표는 자식의 y 좌표보다 크다. 왼쪽 서브트리의 모든 x 좌표는 부모보다 작다. 오른쪽 서브트리의 모든 x 좌표는 부모보다 크다. 주어진 좌표로 이진트리를 구성한 뒤, 전위 순회와 후위 순회 결과를 반환해야 한다. 핵심 아이디어 이 트리...

문제 요약 소괄호, 대괄호, 중괄호로 이루어진 문자열 s가 주어진다. 문자열을 왼쪽으로 x칸 회전한 결과가 올바른 괄호 문자열이 되는 x의 개수를 구해야 한다. 올바른 괄호 문자열은 괄호의 개수뿐 아니라 열고 닫는 순서와 종류도 모두 맞아야 한다. 핵심 아이디어 회전한 문자열이 올바른 괄호 문자열인지 확인할 때 스택을 사용한다. 여는 괄호를 만...

문제 요약 검색어 word와 여러 웹페이지 HTML이 주어진다. 각 웹페이지의 기본 점수와 다른 페이지로부터 받은 링크 점수를 더한 매칭 점수를 계산한 뒤, 점수가 가장 높은 페이지의 인덱스를 반환한다. 기본 점수: 본문 텍스트에서 word가 등장한 횟수 링크 점수: 다른 페이지가 자신의 기본 점수를 외부 링크 수만큼 나누어 전달한 점수 점수가 같으면...

문제 요약 도넛 모양, 막대 모양, 8자 모양 그래프들이 존재한다. 새로운 정점을 하나 만든 뒤, 각 그래프의 임의의 정점으로 향하는 간선을 하나씩 추가했다. 이후 모든 정점의 번호가 섞인 상태에서 간선 정보만 주어진다. 다음 값을 순서대로 반환해야 한다. 새로 생성한 정점 번호 도넛 모양 그래프 개수 막대 모양 그래프 개수 8자 모양 그래프 개수 ...

문제 요약 각 폭격 미사일은 개구간 (s, e)로 주어진다. 요격 미사일은 하나의 x 좌표에서 발사하며, 해당 좌표가 폭격 미사일의 구간 내부에 있으면 요격할 수 있다. 단, 구간은 개구간이므로 s와 e에서는 요격할 수 없다. 모든 폭격 미사일을 요격하기 위한 요격 미사일 수의 최솟값을 구해야 한다. 핵심 아이디어 가장 빨리 끝나는 폭격 미사일부...

문제 요약 다이아몬드, 철, 돌 곡괭이는 한 번 선택하면 최대 5개의 광물을 연속해서 캔다. 광물은 주어진 순서를 바꿀 수 없으며, 가진 곡괭이를 모두 사용하거나 모든 광물을 캐면 작업을 끝낸다. 목표는 곡괭이를 사용하는 순서를 적절히 정해 총 피로도를 최소화하는 것이다. 핵심 아이디어 곡괭이 하나는 정확히 최대 5개 광물을 캐므로, 광물 목록을 5...

문제 요약 캐릭터는 (0, 0)에서 시작해 U, D, R, L 명령에 따라 이동한다. 이동 가능한 좌표 범위는 -5 (0, 1)을 지나간 뒤 (0, 1) -> (0, 0)으로 돌아오면, 두 이동은 방향만 다를 뿐 같은 길이다. 따라서 한 번의 이동을 아래처럼 저장한다. 그리고 반대 방향도 함께 집합에 넣는다. 이렇게 저장하면 같은 길을 어느 방향...

문제 요약 양의 정수 x보다 큰 수 중에서, x와 이진수 표현이 다른 비트의 개수가 1개 또는 2개인 수들 가운데 가장 작은 수 f(x)를 구한다. numbers의 모든 원소에 대해 f(x)를 계산한 배열을 반환하면 된다. 핵심 아이디어 정답은 x가 짝수인지 홀수인지에 따라 규칙이 나뉜다. 1. x가 짝수인 경우 짝수의 이진수는 항상 마지막 비트...

문제 요약 회사 조직은 CEO를 루트로 하는 트리다. 각 팀은 팀장과 그의 직속 팀원들로 이루어진다. 워크숍에 참석하는 직원들의 매출액 합을 최소화해야 하며, 모든 팀에서 팀장 또는 팀원 중 적어도 한 명은 반드시 참석해야 한다. 핵심 아이디어 각 직원에 대해 두 가지 상태를 계산한다. dpnode: 현재 직원이 워크숍에 참석하지 않을 때 서브트리...

문제 요약 각 차량의 고속도로 이동 경로가 구간으로 주어진다. 모든 차량이 적어도 한 대의 카메라를 만나도록 하면서, 설치해야 하는 카메라 수의 최솟값을 구한다. 카메라는 차량의 진입 지점이나 진출 지점에 설치되어 있어도 해당 차량을 단속할 수 있다. 핵심 아이디어 각 차량 경로를 하나의 구간으로 생각한다. 가장 먼저 끝나는 구간의 진출 지점에 ...

문제 요약 배열 a의 부분 수열 중 가장 긴 스타 수열의 길이를 구한다. 스타 수열은 인접한 두 원소씩 묶었을 때 다음을 만족해야 한다. 모든 묶음에 공통으로 포함되는 숫자가 하나 이상 있다. 각 묶음의 두 원소는 서로 다르다. 예를 들어 공통 숫자를 0으로 정했다면, 선택하는 모든 쌍은 (0, 다른 수) 또는 (다른 수, 0) 형태여야 한다. ...

문제 요약 귤 k개를 골라 한 상자에 담을 때, 상자에 포함되는 귤 크기의 종류 수를 최소화해야 한다. 같은 크기의 귤은 모두 같은 종류로 취급하며, 귤 전체 개수는 최대 100,000개다. 핵심 아이디어 한 종류를 선택했을 때 상자에 넣을 수 있는 귤 수는 그 크기의 전체 개수를 넘을 수 없다. 따라서 종류 수를 적게 사용하려면 한 종류에서 최...

문제 요약 각 시작점 s에 대해 [s, e] 범위에서 억억단에 가장 많이 등장하는 수를 구한다. 등장 횟수가 같다면 더 작은 수를 선택한다. 공식 제한에서 e는 최대 5,000,000이고, starts의 길이는 최대 100,000이다. 질문마다 구간 전체를 확인하면 많은 계산이 반복되므로, 모든 질문이 같은 끝점 e를 사용한다는 점을 활용한다. 핵심...

문제 요약 숫자와 연산자 +, -, *로만 구성된 수식이 주어진다. 등장한 연산자들의 우선순위를 모두 다르게 정할 수 있을 때, 계산 결과의 절댓값이 가장 커지는 값을 반환한다. 연산자 종류는 최대 세 개이므로 가능한 우선순위는 최대 3! = 6개다. 핵심 아이디어 우선순위 하나를 정하면, 높은 우선순위의 연산자부터 수식 전체에서 계산하면 된다. ...

문제 요약 새 도시 건설 장소로 금 akg과 은 bkg을 전달해야 한다. 각 도시는 금, 은 보유량과 한 대의 트럭을 가지고 있다. 트럭은 도시와 건설 장소 사이를 왕복하며, 한 번에 금과 은을 합쳐 최대 w[i]kg까지 운반할 수 있다. 가장 빠르게 목표 광물을 전달할 수 있는 시간을 반환한다. 핵심 아이디어 어떤 시간 time 안에 목표량을 운...

각 칸에 S, L, R이 적힌 격자에서 빛은 현재 칸의 지시에 따라 직진, 좌회전, 우회전한 뒤 다음 칸으로 이동한다. 격자 밖으로 나가면 반대편으로 이어지는 토러스 구조다.모든 빛의 경로 사이클 길이를 구해 오름차순으로 반환해야 한다.빛의 경로는 위치만으로 결정되지

문제 요약 처리 시간이 서로 다른 여러 CPU 코어에 작업을 순서대로 배정한다. 시작 시각에는 모든 코어가 비어 있으므로, 앞 번호 코어부터 작업을 하나씩 받는다. 어떤 코어의 작업이 끝나면 즉시 다음 작업을 받는다. 같은 시각에 여러 코어가 비면 번호가 작은 코어부터 작업을 받는다. n번째, 즉 마지막 작업을 처리하는 코어 번호를 반환한다. 핵심...

문제 요약 트리에서 서로 다른 세 정점 a, b, c를 골랐을 때, 세 쌍의 거리의 중간값을 f(a, b, c)라고 한다. 모든 세 정점 조합 중 f의 최댓값을 구한다. 핵심 아이디어 트리에서 가장 먼 두 정점 사이의 거리를 지름이라고 하자. 어떤 세 정점을 골라도 두 정점 사이의 거리는 지름을 넘을 수 없으므로, f의 최댓값도 지름을 넘을 수 없다...

문제 요약 4 x 4 보드에서 같은 그림 카드 두 장을 선택해 제거한다. 방향키 이동, Ctrl + 방향키 이동, Enter 입력은 각각 1회 조작으로 센다. 현재 커서 위치에서 모든 카드 쌍을 제거하는 최소 조작 횟수를 구한다. 핵심 아이디어 이 문제에는 두 종류의 탐색이 필요하다. BFS: 현재 남은 카드 상태에서 한 커서 위치에서 다른 위치까...

문제 요약 주어진 단어 조각을 원하는 만큼 사용해 문자열 t를 완성한다. 문자열을 완성하는 데 필요한 단어 조각 수의 최솟값을 구하고, 만들 수 없다면 -1을 반환한다. 핵심 아이디어 dp[i]를 t의 앞에서부터 i글자까지 완성하는 데 필요한 최소 조각 수라고 정의한다. 어떤 위치 i까지 만들 수 있고, 그 위치부터 시작하는 조각 piece가 t와...

문제 요약 A팀의 출전 순서는 이미 정해져 있고, B팀은 출전 순서를 자유롭게 정할 수 있다. B팀 선수가 A팀 선수보다 큰 숫자를 낼 때만 1점을 얻는다. B팀이 얻을 수 있는 최대 승점을 구한다. 핵심 아이디어 실제 출전 순서보다 어떤 숫자가 어떤 숫자를 이기는지가 중요하다. 따라서 A와 B를 모두 오름차순 정렬한다. B의 작은 숫자부터 확인하...

문제 요약 중복 없는 학습 단어들이 주어졌을 때, 각 단어를 다른 단어와 구분해 자동완성하려면 몇 글자를 입력해야 하는지 구한다. 모든 단어에 필요한 입력 글자 수의 합을 반환한다. 핵심 아이디어 단어를 사전순으로 정렬하면, 어떤 단어와 가장 긴 접두사를 공유할 수 있는 단어는 정렬된 목록에서 바로 앞 또는 바로 뒤에 있다. 따라서 현재 단어가 ...

문제 요약 병사 n명으로 순서대로 등장하는 적을 막는다. 한 라운드를 일반적으로 막으면 적 수만큼 병사가 줄어든다. 무적권은 최대 k번 사용할 수 있고, 사용한 라운드에서는 병사가 줄지 않는다. 최대로 막을 수 있는 라운드 수를 구한다. 핵심 아이디어 어떤 시점까지 막은 라운드들 중에서 무적권은 적 수가 가장 많은 k개 라운드에 쓰는 것이 항상 최...

문제 요약 n x n 시계 격자에서 한 시계를 조작하면 자기 자신과 상하좌우 인접 시계가 시계 방향으로 90도 회전한다. 모든 시곗바늘을 12시 방향인 0으로 만들기 위한 최소 조작 횟수를 구한다. 시계 방향은 0, 1, 2, 3으로 표현하며 모든 변화는 mod 4 연산으로 처리할 수 있다. 핵심 관찰 1. 같은 시계는 최대 3번만 조작하면 된다 ...

문제 요약 도로는 수평 또는 수직 선분이며, 교차하거나 만나는 지점에서 서로 연결된다. 각 도로의 중앙에는 제한 속도를 가진 카메라가 있다. 1번 도시에서 출발해 각 도시까지 일정한 속도로 이동할 때, 경로에서 통과하는 모든 카메라 제한 속도를 만족하는 최대 속도를 구한다. 카메라를 전혀 지나지 않는 경로가 있으면 제한 없이 이동할 수 있으므로 0을 반...

문제 요약 수열의 연속 부분 수열 하나를 선택하고, [1, -1, 1, -1, ...] 또는 [-1, 1, -1, 1, ...] 형태의 펄스 수열을 곱한다. 만들어진 연속 펄스 부분 수열의 합 중 최댓값을 구한다. 핵심 아이디어 펄스 수열의 부호 패턴은 두 가지뿐이다. 원본 수열의 인덱스 기준으로 두 패턴을 미리 곱한 변환 수열을 생각한다. 어떤...

문제 요약 목표 점수 target을 정확히 만들기 위해 다트를 던진다. 최적의 방법은 다음 우선순위로 결정한다. 던지는 다트 수를 최소화한다. 다트 수가 같으면 싱글 또는 불을 맞힌 횟수를 최대화한다. [최소 다트 수, 최대 싱글 또는 불 횟수]를 반환한다. 핵심 아이디어 dp[score]를 정확히 score점을 만드는 최적의 결과라고 정의한다....

문제 요약 로봇은 상, 하, 좌, 우 중 한 방향을 선택하면 장애물 또는 보드 경계에 닿을 때까지 미끄러진다. 로봇이 시작 위치 R에서 목표 위치 G에 정확히 멈추기 위한 최소 이동 횟수를 구한다. 목표에 도달할 수 없으면 -1을 반환한다. 핵심 아이디어 한 번의 방향 선택이 한 번의 이동이고, 모든 이동의 비용이 같다. 따라서 각 정지 위치를 정...