출발 공항과 도착 공항의 쌍 [from, to] 형태로 표현된 티켓 목록이 있다고 가정해 봅시다. 우리는 이 티켓들을 모두 사용하여 올바른 순서의 여정을 찾아야 합니다. 모든 티켓은 첸나이(Chennai)에서 출발하는 한 사람의 것이므로, 여정은 반드시 첸나이에서 시작해야 합니다.예를 들어 입력이 [[Mumbai, Kolkata], [Chennai, Mumbai], [Delhi, Bangalore], [Kolkata, Delhi]]라면, 출력은 [Chennai, Mumbai, Kolkata, Delhi, Bangalore]가 됩니다

문제 개요 N개의 작업 목록이 주어지며, 각 작업은 다음 세 가지 정보를 가지고 있습니다. 시작 시간(Start Time): 작업이 시작되는 시점 종료 시간(Finish Time): 작업이 끝나는 시점 수익(Profit): 작업 완료 시 얻는 이익 구하고자 하는 답은, 선택한 작업들끼리 실행 시간이 서로 겹치지 않으면서 수익의 총합이 최대가 되는 작업 부분 집합입니다. 예를 들어 입력이 N = 4, J = {{2, 3, 55}, {4, 6, 25}, {7, 20, 150}, {3, 150, 250}}이라면 결과는 [(2, 3,

개념이 문제에서는 인코딩된 문자열이 주어지며, 부분 문자열의 반복은 해당 부분 문자열 뒤에 반복 횟수를 붙이는 방식으로 표현됩니다. 예를 들어 인코딩된 문자열이 pq2rs2이고 k=5라면, 해독된 문자열은 pqpqrsrs가 되고 5번째 문자는 r이므로 출력 결과는 r입니다.여기서 한 가지 주의할 점은 인코딩된 부분 문자열의 반복 빈도가 두 자릿수 이상일 수 있다는 것입니다. 예를 들어 pq12r3에서 pq는 12번 반복됩니다. 또한 빈도 수에는 선행 0(leading zero)이 존재하지 않습니다.입력 예시"p2q2r3&q

문제 소개이진 탐색 트리(Binary Search Tree, BST)와 정수 K가 입력으로 주어졌을 때, 트리에서 K번째로 작은 요소를 찾아야 합니다.예를 들어 아래와 같은 BST가 있다고 가정해 보겠습니다.k = 3일 때, 세 번째로 작은 값인 15가 출력됩니다.접근 방법: 중위 순회 활용하기BST의 가장 중요한 성질은 중위 순회(inorder traversal)를 수행하면 노드 값이 오름차순으로 방문된다는 점입니다. 이 성질을 활용하면 다음과 같은 알고리즘을 만들 수 있습니다.find_kth_smallest() 함수를 정의합니다

개념 주어진 두 개의 배열을 이용해 가장 긴 바이토닉(bitonic) 수열을 찾는 것이 이 문제의 목표입니다. 바이토닉 수열이란 처음에는 계속 증가하다가 이후에는 계속 감소하는 형태의 수열을 의미합니다. 여기서 중요한 제약 조건은, 증가하는 부분은 반드시 첫 번째 배열(arr1)의 부분 수열이어야 하고, 감소하는 부분은 반드시 두 번째 배열(arr2)의 부분 수열이어야 한다는 점입니다. 입력 예제 1 arr1[] = {2, 6, 3, 5, 4, 6}, arr2[] = {9, 7, 5, 8, 4, 3} 출력 2, 3, 4, 6, 9

개념 주어진 문자열에서 문자를 일부 제거하거나 순서를 재배치하여 만들 수 있는 가장 긴 회문(palindrome)을 구하는 문제입니다. 최장 길이의 회문이 여러 개 존재할 수 있는데, 이 경우 그중 하나만 출력하면 됩니다. 입력 · 출력 예시 예시 1 입력: pqr 출력: p 또는 q 또는 r 모든 문자가 한 번씩만 등장하므로, 어떤 단일 문자든 길이 1의 회문이 됩니다. 예시 2 입력: ppqqrr 출력: pqrrqp 또는 qprrpq 또는 rqppqr 등 길이 6의 회문을 만들 수 있으며, 가능한 조합은 여러 가지입니다. 예시

개념서로 내용이 거의 같은 두 개의 배열이 주어지고, 단 한 개의 요소만 어느 한쪽 배열에서 빠져 있다고 가정해 봅시다. 이때 우리의 과제는 바로 그 누락된 요소를 찾아내는 것입니다.입력 예시arr1[] = {2, 5, 6, 8, 10} arr2[] = {5, 6, 8, 10}출력2두 번째 배열에는 2가 빠져 있습니다.입력 예시arr1[] = {3, 4, 5, 6} arr2[] = {3, 4, 5, 6, 7}출력7첫 번째 배열에는 7이 빠져 있습니다.해결 방법1. 선형 탐색 (단순 접근)가장 간단한 방법은 두 배열을 처음부터 끝까지

개념 정수 배열이 주어졌을 때, 배열의 모든 요소에 대해 왼쪽에서 가장 가까운 더 작은 요소와 오른쪽에서 가장 가까운 더 작은 요소를 찾아 두 값의 절댓값 차이를 계산하고, 그중 최댓값을 구하는 것이 이 문제의 목표입니다. 만약 어떤 요소의 왼쪽이나 오른쪽에 더 작은 요소가 존재하지 않는다면 해당 값은 0으로 간주합니다. 예를 들어 가장 왼쪽에 있는 요소는 왼쪽에 더 작은 값이 없으므로 0으로 처리하며, 가장 오른쪽 요소 역시 오른쪽의 더 작은 값을 0으로 처리합니다. 예시 1 arr[] = {3, 2, 9} 출력: 2 왼쪽 더

개념도시의 개수 N(0번부터 N-1번까지 번호가 매겨짐)과 역이 설치된 도시들의 목록이 주어졌을 때, 각 도시에서 가장 가까운 역까지의 거리 중 최댓값을 구하는 것이 이 문제의 목표입니다. 역이 있는 도시들은 특정한 순서 없이 임의로 주어질 수 있다는 점에 유의해야 합니다.입력 및 출력 예시예시 1:numOfCities = 6, stations = [2, 4]출력:2예시 2:numOfCities = 6, stations = [4]출력:4예시 설명첫 번째 예시에는 총 6개의 도시가 있으며, 역이 설치된 도시는 아래 그림에서 초록색으로

개념주어진 숫자 격자(grid)에서 최대 길이의 뱀 시퀀스(Snake Sequence)를 찾아 화면에 출력하는 것이 목표입니다. 만약 최대 길이를 가지는 뱀 시퀀스가 여러 개 존재한다면, 그중 아무거나 하나만 출력하면 됩니다.여기서 뱀 시퀀스란 격자 안에서 서로 인접한 숫자들로 이루어진 경로를 말하며, 각 숫자 기준으로 오른쪽 또는 아래에 있는 숫자가 현재 값보다 +1 또는 -1 차이가 나야 합니다. 즉, 현재 위치가 (a, b)라면 오른쪽 칸 (a, b+1)이 ±1 차이일 때 오른쪽으로 이동하거나, 아래 칸 (a+1, b)이 ±1

개념정수 X가 주어졌을 때, 처음 N개의 자연수의 제곱의 합이 X를 초과하지 않도록 하는 최댓값 N을 구하는 것이 이 문제의 목표입니다.입력X = 7출력2N = 3일 경우 수열의 합이 X를 초과하므로(1² + 2² + 3² = 1 + 4 + 9 = 14), 2가 N이 가질 수 있는 최댓값입니다.입력X = 27출력3N = 4일 경우 수열의 합이 X를 초과하므로(1² + 2² + 3² + 4² = 1 + 4 + 9 + 16 = 30), 3이 N이 가질 수 있는 최댓값입니다.풀이 방법단순 해법가장 간단한 방법은 S(N) ≤ X를 만족하는

개념 최대 10^6까지 될 수 있는 두 개의 수 P와 Q가 주어지며, 이 두 수는 N = P!/Q!라는 수를 형성합니다. 우리의 목표는 연산을 최대한 많이 수행하여 N을 1로 줄이는 것입니다. 각 연산에서는 N이 X로 나누어 떨어질 경우 N을 N/X로 대체할 수 있습니다. 이때 가능한 최대 연산 횟수를 구해야 합니다. 입력 및 출력 예시 예시 1 A = 7, B = 4 출력: 4 설명: N은 210이며, 소인수는 2, 3, 5, 7입니다. 예시 2 A = 3, B = 1 출력: 2 설명: N은 6이며, 소인수는 2, 3입니다.

문제 개념N개의 원소를 가진 배열 A와 두 정수 l, r이 주어집니다. 단, 각 원소는 1 ≤ ax ≤ 105 범위를 가지며 1 ≤ l ≤ r ≤ N 조건을 만족합니다. 배열에서 임의의 원소 ax를 선택해 삭제하면, 값이 ax+1, ax+2 … ax+r 또는 ax-1, ax-2 … ax-l에 해당하는 모든 원소도 함께 제거됩니다. 이 연산 하나는 ax만큼의 점수를 얻게 됩니다.목표는 배열의 모든 원소를 삭제하는 과정에서 얻을 수 있는 총 점수를 최대화하는 것입니다.예제 12 1 2 3 2 2 1l = 1, r = 1출력:8값 2를

개념크기가 n인 양의 정수 배열이 주어졌을 때, 인덱스 조건 0 <= i < j < k < n과 값 조건 ai < aj < ak를 동시에 만족하는 삼중항( ai + aj + ak )의 최대 합을 구하는 것이 이번 문제의 목표입니다.입력a[] = 3 6 4 2 5 10출력19설명가능한 모든 삼중항은 다음과 같습니다.3 4 5 => 합 = 123 6 10 => 합 = 193 4 10 => 합 = 174 5 10 => 합 = 192 5 10 => 합 = 17최대 합 = 19풀이

개념주어진 이진 탐색 트리(Binary Search Tree, BST)에서 중앙값(median)을 구하는 것이 우리의 과제입니다.노드의 개수에 따라 중앙값은 다음과 같이 정의됩니다.노드 수가 짝수일 때: 중앙값 = ((n/2번째 노드 + (n+1)/2번째 노드) / 2노드 수가 홀수일 때: 중앙값 = (n+1)/2번째 노드먼저 노드 수가 홀수인 BST의 예를 살펴보겠습니다.       7      / \ &n

문제 개요 RAM이 블록 단위로 구성되어 있고, 시스템에서는 여러 프로세스가 동시에 실행되고 있다고 가정해 보겠습니다. 각 프로세스는 다음과 같은 형식의 메모리 접근 정보를 가집니다. (스레드 T, 메모리 블록 M, 시간 t, R/W) 이 정보는 스레드 T가 시간 t에 메모리 블록 M에 접근했으며, 해당 연산이 읽기(R) 또는 쓰기(W) 중 하나였음을 의미합니다. 메모리 충돌 판정 조건 같은 메모리 위치에서 여러 스레드가 동시에 읽기(R) 연산을 수행하는 것은 충돌이 아닙니다. 어떤 스레드가 시간 x에 메모리 블록 M에 접근할 때

개념양의 정수로 이루어진 배열이 주어졌을 때, 배열의 각 요소를 교체하여 인접한 요소 간의 차이가 주어진 target 값 이하가 되도록 만들어야 합니다. 이때 목표는 조정 비용(adjustment cost), 즉 새로운 값과 기존 값의 차이의 합을 최소화하는 것입니다.다시 말해, Σ|A[i] – Anew[i]| (단, 0 ≤ i ≤ n-1)를 최소화해야 하며, 여기서 n은 배열 A[]의 크기, Anew[]는 인접 요소 간 차이가 target 이하가 되도록 조정된 배열을 의미합니다. 편의상 배열의 모든 요소는 상수 M = 100보다

개요다음과 같은 흐름 네트워크(flow network)가 주어졌다고 가정해 봅시다. s-t 컷(s-t cut)이란 소스(source) 노드 s와 싱크(sink) 노드 t가 서로 다른 집합에 속하도록 그래프를 분할하는 것을 의미합니다. 이때 컷에는 소스 쪽 집합에서 싱크 쪽 집합으로 향하는 간선들이 포함됩니다.s-t 컷의 용량(capacity)은 컷 집합(cut-set)에 포함된 각 간선 용량의 합으로 정의됩니다. 우리의 목표는 주어진 네트워크에서 최소 용량을 가지는 s-t 컷을 찾고, 해당 최소 컷을 구성하는 모든 간선을 출력하는

개요서로 다른 소요 시간을 가진 작업 배열이 주어지고, 동일한 능력을 지닌 k명의 작업자(할당자)가 사용 가능하며, 각 작업자가 작업 1단위를 처리하는 데 걸리는 시간 t도 함께 주어집니다. 이때 다음 두 가지 제약 조건을 만족하면서 모든 작업을 완료하는 데 필요한 최소 시간을 구하는 것이 문제의 목표입니다.첫 번째 제약 조건: 한 작업자에게는 반드시 연속된 작업만 할당할 수 있습니다. 예를 들어 배열에서 위치 1과 2의 작업은 같은 작업자에게 배정할 수 있지만, 위치 1과 3처럼 떨어진 작업은 배정할 수 없습니다.두 번째 제약 조

개념 n개의 서로 다른 정수로 이루어진 배열 array[]가 주어집니다. 요소들은 오름차순으로 연속적으로 배치되어 있지만, 그중 하나의 요소가 빠져 있습니다. 우리의 목표는 이진 탐색(Binary Search)을 활용해 O(logN) 시간 안에 누락된 요소를 찾아내는 것입니다. 입력 및 출력 예시 예시 1 array[] = {1, 2, 3, 4, 5, 6, 7, 9} 출력: 8 예시 2 array[] = {-4, -2, -1, 0, 1, 2} 출력: -3 예시 3 array[] = {1, 2, 3, 4} 출력: -1 세 번째 예