2차원 평면 위에 2n개의 좌표가 주어져 있다고 가정해 봅시다. 이 좌표들은 두 개의 배열 coordA와 coordB로 나누어 주어지며, 각 좌표는 정수 쌍으로 표현됩니다. 우리의 목표는 coordA에서 한 점과 coordB에서 한 점을 짝지어 좌표 쌍을 만드는 것입니다. 단, 쌍을 이룰 수 있는 조건은 coordA의 점의 x좌표가 coordB의 점의 x좌표보다 작고, 동시에 coordA의 점의 y좌표가 coordB의 점의 y좌표보다 작아야 한다는 것입니다. 또한 한 점이 여러 쌍에 중복해서 속할 수는 없습니다. 이렇게 만들 수

문제 개요 정수로 이루어진 순열 seq와, 0부터 n-1 범위의 정수 쌍 m개로 구성된 배열 pairs가 주어집니다. 우리는 seq[i] = i(0 ≤ i < n)를 만족하는 i의 개수를 최대화하기 위해 다음 연산을 원하는 만큼 반복해서 수행할 수 있습니다. 0 ≤ j < m인 정수 j를 하나 선택한 뒤, seq[pairs[j]의 첫 번째 값]과 seq[pairs[j]의 두 번째 값]의 위치를 서로 맞바꿉니다. 목표는 연산을 여러 번 수행한 결과 seq[i] = i가 성립하는 i의 최대 개수를 구하는 것입니다. 예를

문제 개요 n개의 도시와 이들을 연결하는 m개의 도로가 있다고 가정해 봅시다. 모든 도로는 일방통행이며, 출발 도시에서 목적지 도시까지 이동하는 데 일정한 시간이 걸립니다. 도로 정보는 roads 배열에 담겨 있으며, 각 원소는 (출발지, 목적지, 소요 시간) 형식을 따릅니다. 어떤 사람이 한 도시에서 출발해 다시 같은 도시로 돌아오는 왕복 여행(round-trip)을 하려고 합니다. 왕복 여행이란 특정 도시에서 시작해 하나 이상의 도로를 지나 다시 출발했던 도시에서 끝나는 경로를 의미합니다. 따라서 우리는 각 도시마다 그 도시에

문제 상황어떤 제조업체가 특정 제품에 들어갈 부품을 전문적으로 생산한다고 가정해 봅시다. 이 제조업체는 n가지 서로 다른 종류의 부품을 보유하고 있으며, 각 부품은 세 가지 기준(A, B, C)에 따라 평점이 매겨집니다. n개 부품의 평점은 배열 ratings에 담겨 있고, 각 원소는 (A, B, C) 형태입니다.이제 어느 OEM 업체가 자사 제품 하나당 m개의 부품을 이 제조업체로부터 구매하려고 합니다. 단, 부품을 선택할 때 아래 두 가지 조건을 만족해야 합니다.동일한 부품을 두 개 이상 구매할 수 없습니다.다음 식의 값 V가

문제 설명문자열 S가 주어지며, 각 문자는 0, 1 또는 ? 중 하나입니다. 우리는 ?를 각각 0 또는 1로 치환하여 새로운 문자열 T를 만들려고 합니다.여기서 T의 불균형(unbalancedness)은 다음과 같이 정의됩니다. 0 ≤ l ≤ r < |S|를 만족하는 모든 구간 [l, r]에 대해, 해당 구간 안에서 0의 개수와 1의 개수 차이의 절댓값을 계산하고, 그 값들 중 최댓값을 불균형이라고 합니다. 목표는 ?를 적절히 채워 T가 가질 수 있는 최소 불균형을 찾는 것입니다.예를 들어 입력이 S = 0??0이라면, 출력은 2가

문제 소개N개의 요소로 이루어진 숫자 리스트 A가 있다고 가정해 보겠습니다. 리스트의 모든 요소는 1, 2 또는 3입니다. 이때 행렬 X를 다음과 같이 정의합니다.X[1][j] = A[j] (단, j는 1부터 N까지)X[i][j] = |X[i-1][j] − X[i-1][j+1]| (단, i는 2부터 N까지, j는 1부터 N+1−i까지)우리가 구해야 하는 것은 위 규칙을 끝까지 적용했을 때 얻어지는 행렬의 마지막 값입니다.예제입력이 A = [1, 2, 3, 1]이라면 출력은 1이 됩니다. 계산 과정은 다음과 같습니다.X[1][1] ~

문제 설명 N개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. N개의 상자가 하나의 원을 이루며 배치되어 있고, i번째 상자에는 A[i]개의 돌이 들어 있습니다. 우리는 다음 연산을 반복 수행하여 모든 상자에서 돌을 완전히 비울 수 있는지 확인해야 합니다. 임의의 상자 i를 하나 선택합니다. j가 1부터 N까지 변하는 동안, (i+j)번째 상자에서 정확히 j개의 돌을 제거합니다. 이때 (N+k)번째 상자는 k번째 상자와 동일하게 취급합니다(원형 순환). 만약 어떤 상자에 충분한 돌이 들어 있지 않다면 해당 연산은 수행할 수

숫자 N이 하나 주어져 있다고 가정해 봅시다. 어떤 케이크 가게에서는 케이크를 40루피에, 도넛을 70루피에 판매하고 있습니다. 우리가 확인해야 할 것은 정확히 N루피를 사용해 이 제품들을 구매할 수 있는지 여부입니다.예를 들어 입력이 N = 110이라면 출력은 True가 됩니다. 케이크 한 개(40루피)와 도넛 한 개(70루피)를 구매하면 40 + 70 = 110루피가 되기 때문입니다.문제 해결 접근 방식이 문제는 깊이 우선 탐색(DFS)을 활용해 해결할 수 있습니다. 현재까지 계산한 금액 i에서 시작하여, 매 단계마다 케이크(4

문제 개요N개의 요소를 가진 배열 A가 있다고 가정해 봅시다. N마리의 고양이가 있으며, 각각 1부터 N까지 번호가 매겨져 있습니다. 모든 고양이는 모자를 하나씩 쓰고 있는데, i번째 고양이는 나를 제외한 나머지 N-1마리 고양이의 모자 중에서 서로 다른 색상은 정확히 A[i]가지다라고 말합니다.우리가 확인해야 할 것은, 고양이들의 발언과 모순되지 않는 모자 색상 배치가 실제로 존재하는지 여부입니다.예를 들어 입력이 A = [1, 2, 2]라면 출력은 True입니다. 1번 고양이는 빨간색 모자를, 2번과 3번 고양이는 파란색 모자를

문제 소개통신사가 올인원(all-in-one)이라는 신규 서비스를 출시했다고 가정해 보겠습니다. 이 서비스에 가입하면 n개의 OTT 콘텐츠 제공업체를 모두 고정 요금 k달러로 이용할 수 있습니다. 반면, 각 OTT 플랫폼에 개별적으로 직접 구독하려면 플랫폼마다 별도의 요금을 지불해야 합니다.모든 플랫폼을 매월 구독할 필요는 없기 때문에, 필요한 기간에 맞춰 가장 비용 효율적으로 서비스를 이용하는 방법을 찾아야 합니다. i번째 플랫폼의 구독 시작 월은 배열 start_month에, 종료 월은 배열 end_month에 담겨 있으며, 각

x × y 크기의 그리드가 주어졌다고 가정해 보겠습니다. 이 그리드는 두 종류의 칸으로 이루어져 있는데, 하나는 접근할 수 없는 막힌 칸(blocked)이고 다른 하나는 자유롭게 이동할 수 있는 열린 칸(unblocked)입니다. 그리드는 2차원 배열로 표현되며, 막힌 칸은 #, 열린 칸은 .으로 나타냅니다.목표는 왼쪽 위 끝 칸인 (0, 0)에서 출발하여 오른쪽 아래 끝 칸인 (x−1, y−1)에 도달하는 것입니다. 사용할 수 있는 이동은 오직 두 가지뿐입니다. 현재 칸에서 오른쪽으로 한 칸 이동하거나 아래쪽으로 한 칸 이동하는

칼을 무기로 적을 물리치는 비디오 게임을 하고 있다고 가정해 보겠습니다. 주인공은 칼로 적을 직접 베거나(슬래시), 칼을 적에게 던질 수도 있습니다. 단, 던진 칼은 다시 회수할 수 없습니다. i번째 칼이 가하는 피해량은 배열 knives에 담겨 있으며, 각 요소는 {slash, throw} 형태입니다. 여기서 slash는 해당 칼로 적을 베었을 때의 피해량, throw는 그 칼을 던졌을 때의 피해량을 의미합니다. 베기(slash)는 원하는 만큼 무제한으로 사용할 수 있지만, 각 칼은 딱 한 번만 던질 수 있습니다. 이제 체력이 h

h × w 크기의 그리드가 주어진다고 가정해 보겠습니다. 그리드의 각 셀은 두 가지 유형으로 구분됩니다. 접근할 수 없는 막힌 셀(blocked)과 자유롭게 이동할 수 있는 열린 셀(unblocked)입니다. 그리드는 2차원 배열로 표현하며, 막힌 셀은 #으로, 열린 셀은 .으로 나타냅니다. 목표는 한 열린 셀에서 출발해 다른 열린 셀에 도달할 때 필요한 이동 횟수의 최댓값을 구하는 것입니다. 이동은 상하좌우 방향(수직·수평)으로만 가능하고 대각선 이동은 허용되지 않으며, 경로에는 반드시 열린 셀만 포함되어야 합니다. 예를 들어 h

문제 개요 2차원 평면에 두 점 a와 b가 있으며, 각각 좌표 (x1, y1)과 (x2, y2)를 가지고 있다고 가정해 보겠습니다. 현재 우리는 점 a에 위치해 있으며, 한 번에 수직 또는 수평 방향으로 거리 1만큼만 이동할 수 있습니다. 목표는 점 a에서 점 b로 이동한 뒤 다시 점 a로 돌아오고, 이후 또다시 점 b로 이동하는 전체 여정의 이동 과정을 찾아 출력하는 것입니다. 단, 점 a와 b를 제외한 어떤 점도 두 번 이상 지나갈 수 없습니다. 이동 방향은 다음과 같이 문자로 표현합니다. R : 오른쪽으로 이동 L : 왼쪽으

문제 소개 빈 시퀀스가 하나 주어져 있고, 이 시퀀스에 대해 처리해야 할 n개의 쿼리가 있다고 가정해 봅시다. 쿼리는 배열 queries에 저장되어 전달되며, 각 쿼리는 {query, data} 형식을 따릅니다. 쿼리의 종류는 다음 세 가지입니다. query = 1 : 전달된 데이터(data)를 시퀀스의 맨 뒤에 추가합니다. query = 2 : 시퀀스 맨 앞의 원소를 출력하고, 해당 원소를 시퀀스에서 제거합니다. query = 3 : 시퀀스 전체를 오름차순으로 정렬합니다. 단, 쿼리 타입 2와 3에서는 항상 data = 0이

문제 소개h × w 크기의 격자(grid)가 있다고 가정해 보겠습니다. 격자의 시작점인 (0, 0) 위치에 로봇이 있으며, 이 로봇은 목적지인 (h − 1, w − 1) 위치로 이동해야 합니다.격자를 이루는 칸은 막힌 칸(#)과 열린 칸(.) 두 가지입니다. 로봇은 열린 칸은 자유롭게 통과할 수 있지만 막힌 칸은 지나갈 수 없으며, 상·하·좌·우 네 방향으로 움직일 수 있습니다.그런데 로봇은 한 칸에서 다른 칸으로 이동할 때 직전에 있던 칸을 제외한 어느 방향으로든 움직일 수 있기 때문에, 경로가 여러 갈래로 갈라질 수 있습니다.

문제 개요 n개의 정점과 m개의 간선으로 이루어진 가중치 무방향 그래프가 있다고 가정해 보겠습니다. 그래프의 점수(score)는 그래프에 포함된 모든 간선 가중치의 합으로 정의됩니다. 간선의 가중치는 음수일 수도 있는데, 음수 가중치를 가진 간선을 제거하면 오히려 점수가 증가하게 됩니다. 우리가 해야 할 작업은 그래프의 연결 상태를 유지하면서 간선을 제거해 그래프의 점수를 최소화하는 것이며, 이때 감소시킬 수 있는 점수의 최댓값을 구하는 것입니다. 입력 형식과 예시 그래프는 edges 배열로 주어지며, 각 원소는 {weight,

문제 개요n × n 픽셀 크기의 정사각형 이미지 두 개(first와 second)가 있다고 가정해 보겠습니다. 각 픽셀은 검은색 또는 흰색이며, 이미지는 행렬 형태로 주어집니다. 검은색 픽셀은 x, 흰색 픽셀은 .으로 표현합니다. 이 문제의 목표는 두 번째 이미지를 90° 단위로 회전하거나 평행 이동했을 때 첫 번째 이미지와 완전히 일치하는지 판별하는 것입니다. 일치하면 true를, 그렇지 않으면 false를 반환합니다.예를 들어 n = 4이고 first = {..x., x.x., x.xx, xx..}, second = {..xx,

한 자동차 회사가 빨간색 차 p대와 파란색 차 q대를 서로 다른 가격으로 판매하기로 결정했다고 가정해 보겠습니다. 현재 회사 재고에는 빨간색 차 a대, 파란색 차 b대, 그리고 아직 도색되지 않은 무색(미도색) 차 c대가 보관되어 있으며, 각 차량의 가치는 배열 A, B, C에 담겨 주어집니다. 회사는 하루 동안 반드시 p + q대의 차량을 판매해야 하며, 이때 가능한 한 최대 이익을 실현해야 합니다. 무색 차량은 빨간색 또는 파란색 중 원하는 색으로 자유롭게 도색할 수 있습니다. 이 조건에서 판매를 통해 얻을 수 있는 최대 수익

문제 개요총 2n개의 문자가 있고, 각 문자에는 1부터 n 사이의 정수가 하나씩 적혀 있습니다. 같은 숫자는 정확히 두 개의 문자에만 등장합니다. 이 문자들은 m개의 스택에 나누어 쌓여 있으며, i번째 스택에는 stacks[i]에 해당하는 문자들이 들어 있습니다.목표는 다음 규칙에 따라 모든 스택을 비우는 것입니다.임의의 두 스택을 선택하고, 두 스택에서 각각 맨 위의 문자를 제거합니다.이때 제거한 두 문자에는 반드시 동일한 숫자가 적혀 있어야 합니다.이러한 방식으로 m개의 스택을 모두 비울 수 있다면 true를 출력하고, 그렇지