난류 부분 배열(Turbulent Subarray)이란? 배열 A의 부분 배열 A[i], A[i+1], ..., A[j]가 다음 조건 중 하나를 만족할 때, 이를 난류(turbulent) 상태라고 정의합니다. i <= k < j인 모든 k에 대해, k가 홀수일 때는 A[k] > A[k+1], k가 짝수일 때는 A[k] < A[k+1] 반대로 같은 범위의 모든 k에 대해, k가 짝수일 때는 A[k] > A[k+1], k가 홀수일 때는 A[k] < A[k+1] 쉽게 말해, 부분 배열 안에서 인접한 두

이번 글에서는 타임스탬프와 함께 데이터를 저장하고 조회할 수 있는 시간 기반 키-값 저장소(TimeMap) 클래스를 C++로 구현해 보겠습니다. 이 자료구조는 두 가지 연산을 지원해야 합니다.set(string key, string value, int timestamp): 주어진 키(key)에 값(value)과 타임스탬프(timestamp)를 함께 저장합니다.get(string key, int timestamp): 이전에 호출된 set(key, value, timestamp_prev) 중에서 timestamp_prev <= t

문제 개요두 정수 A와 B가 주어졌을 때, 다음 조건을 모두 만족하는 임의의 문자열 S를 반환하는 것이 목표입니다.S의 길이는 A + B이며, 정확히 A개의 문자 a와 B개의 문자 b로 구성됩니다.부분 문자열 "aaa"와 "bbb"는 S에 절대 나타나지 않아야 합니다.예를 들어 A = 4, B = 1이 입력으로 주어지면, 유효한 출력은 "aabaa"입니다. 이 문자열은 a 4개와 b 1개를 포함하면서도 같은 문자가 세 번 연속으로 등장하지 않습니다.풀이 전략핵심 아이디어는 개수가

변수들 간의 관계를 나타내는 등식 배열이 주어졌다고 가정해 봅시다. 각 문자열 equations[i]는 길이가 4이며, "a==b" 또는 "a!=b" 두 가지 형태 중 하나입니다. 여기서 a와 b는 한 글자짜리 변수 이름을 나타내는 소문자입니다. 이 문제의 목표는 주어진 모든 등식을 동시에 만족하도록 변수에 정수를 할당할 수 있을 때만 true를 반환하는 것입니다.예를 들어 입력이 ["a==b","b==c","a==c"]라면, 세 변수 a, b

문제 설명양의 정수로 구성된 배열 A가 있다고 가정해 보겠습니다. 여기서 A[i]는 i번째 관광 명소의 가치를 나타내며, 두 관광 명소 i와 j 사이의 거리는 j - i입니다. 이때 관광 명소 쌍 (i < j)의 점수는 다음 공식으로 계산됩니다.A[i] + A[j] + i - j우리의 목표는 이 점수가 최대가 되는 관광 명소 쌍을 찾는 것입니다. 예를 들어 입력이 [8, 1, 5, 2, 6]이라면 출력은 11이 됩니다. i = 0, j = 2일 때 A[0] + A[2] + 0 - 2 = 8 + 5 + 0 - 2 = 11이 되어

이진 문자열 S와 양의 정수 N이 주어졌을 때, 1부터 N까지의 모든 정수 X에 대해 X의 이진 표현이 문자열 S의 부분 문자열로 존재한다면 true를 반환해야 합니다.예를 들어 S = 0110이고 N = 3이라면 결과는 true입니다. 1은 1, 2는 10, 3은 11로 표현되며, 이 세 값이 모두 0110 안에 포함되어 있기 때문입니다.문제 해결 접근 방법정수 n을 입력받아 이진 문자열로 변환하는 convert() 메서드를 정의합니다.ret := 빈 문자열로 초기화합니다.n이 0이 아닌 동안 다음을 반복합니다.ret := ret

문제 개요 하나의 숫자 N이 주어졌을 때, 그 값을 -2진법(음수 2를 밑으로 하는 진법)으로 표현하는 0과 1로만 이루어진 문자열을 찾는 것이 목표입니다. 단, 반환되는 문자열은 정확히 0인 경우를 제외하고 선행 0(leading zero)을 포함해서는 안 됩니다. 예를 들어 입력이 2라면 출력은 110이 됩니다. 이는 (-2)² + (-2)¹ = 4 - 2 = 2이기 때문입니다. 해결 접근 방식 일반적인 진법 변환과 원리는 비슷하지만, 밑(base)이 음수라는 점에서 나머지 처리에 주의해야 합니다. 다음 단계를 따릅니다. r

문제 이해하기2차원 배열 A가 주어져 있습니다. 각 칸은 0(바다) 또는 1(육지)을 나타내며, 이동(move)은 한 육지 칸에서 상하좌우 네 방향 중 하나로 인접한 육지 칸으로 걸어가는 것, 또는 그리드의 경계 밖으로 나가는 것을 의미합니다. 우리가 구해야 하는 값은 아무리 이동해도 그리드 경계 밖으로 나갈 수 없는 육지 칸, 즉 엔클레이브(enclave)의 개수입니다.예시다음과 같은 그리드가 주어졌다고 가정해 보겠습니다.0000101001100000이 경우 정답은 3입니다. 0으로 완전히 둘러싸인 1이 세 개 존재하고, 나머지

문제 설명T초 동안 진행된 스포츠 경기를 담은 여러 개의 영상 클립이 있다고 가정해 보겠습니다. 클립들은 서로 겹칠 수도 있고 길이도 제각각입니다. 각 클립 clips[i]는 하나의 구간(interval)을 의미하며, clips[i][0] 시점에 시작해서 clips[i][1] 시점에 끝납니다.클립은 자유롭게 잘라 세그먼트로 만들 수 있습니다. 목표는 이 클립들을 편집해 경기 전체 구간인 [0, T]를 온전히 덮을 때 필요한 최소 클립 개수를 구하는 것입니다. 어떻게 조합해도 전체 구간을 커버할 수 없다면 -1을 반환해야 합니다.예를

문제 개요 정수로 이루어진 배열 A가 주어졌을 때, A에서 가장 긴 등차수열(arithmetic sequence) 부분 수열의 길이를 반환해야 합니다. 배열 A의 부분 수열이란 0 <= i_1 < i_2 < ... < i_k <= A.length - 1 조건을 만족하는 A[i_1], A[i_2], ..., A[i_k] 형태의 리스트를 의미합니다. 그리고 수열 B에서 인접한 두 원소의 차이 B[i+1] - B[i]가 모두 동일한 값을 가질 때(0 <= i < B.length - 1), B를 등차

문제 설명두 개의 수평선 위에 정수 배열 A와 B가 주어진 순서대로 적혀 있다고 가정해 봅시다. 이제 두 숫자 A[i]와 B[j]를 잇는 연결선을 그릴 수 있는데, 이때 다음 조건을 만족해야 합니다.A[i] == B[j] 여야 합니다.그려지는 선은 다른 어떤 연결선(수평선은 제외)과도 교차해서는 안 됩니다.주의할 점은 연결선이 끝점에서도 서로 교차할 수 없다는 것입니다. 즉, 각 숫자는 오직 하나의 연결선에만 속할 수 있습니다. 우리의 목표는 그릴 수 있는 연결선의 최대 개수를 구하는 것입니다.예를 들어 입력이 [1,4,2]와 [1

문제 설명값 N이 주어졌다고 가정해 봅시다. 꼭짓점에 A[0], A[1], ..., A[N-1] 라벨이 시계 방향 순서로 붙어 있는 볼록 N각형이 하나 있습니다. 이제 이 다각형을 N-2개의 삼각형으로 나누는 삼각분할(Triangulation)을 수행하려고 합니다.각 삼각형의 값은 해당 삼각형을 이루는 세 꼭짓점 라벨의 곱으로 정의되며, 삼각분할 전체의 총 점수는 N-2개 삼각형 값들의 합입니다. 우리가 구해야 하는 것은 가능한 모든 삼각분할 방식 중에서 얻을 수 있는 최소 총 점수입니다.예를 들어 입력이 [1,2,3]이라면 출력은

문제 개요 무한히 넓은 평면 위에 로봇이 하나 있다고 가정해 보겠습니다. 로봇은 처음에 좌표 (0, 0)에 서 있으며 북쪽 방향을 바라보고 있습니다. 로봇은 다음 세 가지 명령 중 하나를 받을 수 있습니다. G – 직진하여 1단위 앞으로 이동 L – 왼쪽으로 90도 회전 R – 오른쪽으로 90도 회전 로봇은 주어진 명령을 순서대로 수행하며, 이 명령 시퀀스는 끝없이 반복됩니다. 우리가 확인해야 할 것은 로봇이 절대로 벗어나지 않는 원이 평면 위에 존재하는지, 즉 로봇의 이동 경로가 유계(bounded)인지 판별하는 것입니다. 예

소문자로만 구성된 단어 목록이 주어졌을 때, 한 단어(word1)가 다른 단어(word2)의 선행자(predecessor)가 되는 조건은 word1의 아무 위치에 정확히 한 글자를 추가했을 때 word2와 같아지는 경우입니다. 예를 들어 abc는 abac의 선행자입니다.단어 체인(word chain)= 1)로, word_1이 word_2의 선행자이고, word_2가 word_3의 선행자인 식으로 이어지는 구조를 말합니다. 우리의 목표는 주어진 단어 목록에서 선택한 단어들로 만들 수 있는 가장 긴 단어 체인의 길이를 구하는 것입니다.

문제 설명양의 정수 가중치를 가진 돌들이 여러 개 주어져 있습니다. 매 턴마다 임의의 두 돌을 골라 서로 부딪히게 하는데, 두 돌의 무게를 각각 x, y(x ≤ y)라고 할 때 충돌 결과는 다음과 같습니다.x = y인 경우: 두 돌은 모두 완전히 파괴됩니다.x ≠ y인 경우: 무게 x인 돌은 완전히 파괴되고, 무게 y인 돌은 새로운 무게 y − x를 갖습니다.이 과정을 반복하면 최종적으로 최대 1개의 돌만 남게 되는데, 이때 남은 돌의 최소 가능한 무게를 구하는 것이 목표입니다. 모든 돌이 파괴된다면 답은 0입니다.예시입력이 [2,

문제 소개문자열이 하나 주어졌을 때, 몇 개의 문자를 삭제하거나 아무것도 삭제하지 않은 상태로 그 문자열의 부분 수열(subsequence)을 만들 수 있습니다. 이제 두 문자열 source와 target이 주어진다고 가정해 봅시다. 우리가 구해야 하는 것은 source의 부분 수열들을 이어 붙였을 때 target과 완전히 같아지도록 하는 부분 수열의 최소 개수입니다. 만약 어떤 방법으로도 불가능하다면 -1을 반환합니다.예를 들어 source = abc, target = abcbc인 경우를 살펴보겠습니다. abc와 bc 두 개의 부

문제 개요 가격 배열 P = [p₁, p₂, ..., pₙ]와 목표 값(target)이 주어졌을 때, 각 가격 Pᵢ를 Roundᵢ(Pᵢ)로 반올림하여 반올림된 배열 [Round₁(P₁), Round₂(P₂), ..., Roundₙ(Pₙ)]의 총합이 목표 값과 정확히 일치하도록 만들어야 합니다. 여기서 각 반올림 연산 Roundᵢ(pᵢ)는 내림(Floor) 또는 올림(Ceil) 중 하나만 사용할 수 있습니다. 반올림된 배열의 합을 목표 값으로 맞추는 것이 불가능한 경우에는 문자열 "-1"을 반환합니다. 가능하다면

정렬된 서로 다른 숫자들의 배열 A가 주어졌을 때, 배열의 가장 왼쪽 숫자를 기준으로 K번째 누락된 숫자를 찾는 문제입니다. 예를 들어 배열이 [4, 7, 9, 10]이고 k = 1이라면, 답은 5가 됩니다.접근 방법: 이진 탐색 활용배열이 정렬되어 있으므로 선형 탐색(O(n)) 대신 이진 탐색(O(log n))을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 두 인덱스 사이에 실제 존재하는 요소 수와 있어야 할 요소 수의 차이, 즉 누락된 개수를 계산하는 것입니다.알고리즘 단계n := 배열의 크기로 설정하고, low :

길이가 같은 두 문자열 A와 B가 주어졌을 때, A[i]와 B[i]는 서로 동치(equivalent)인 문자로 간주합니다. 예를 들어 A = abc, B = cde라면 a = c, b = d, c = e가 성립합니다. 이러한 동치 관계는 다음과 같은 일반적인 동치 관계의 성질을 따릅니다. 반사성(Reflexivity): a = a 대칭성(Symmetry): a = b이면 b = a 추이성(Transitivity): a = b이고 b = c이면 a = c 예를 들어 위의 동치 정보가 주어졌을 때, S = eed, acd, aab는

문자열 S가 주어졌을 때, 가장 긴 반복 부분 문자열(longest repeating substring)의 길이를 찾는 것이 이번 문제의 목표입니다. 만약 반복되는 부분 문자열이 존재하지 않는다면 0을 반환해야 합니다.예를 들어 문자열이 abbaba라고 해봅시다. 이 경우 정답은 2입니다. 왜냐하면 가장 긴 반복 부분 문자열이 ab 또는 ba이고, 그 길이가 2이기 때문입니다.문제 접근 방법이 문제는 동적 계획법(Dynamic Programming)을 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.dp[i]