두 명의 플레이어 Alex와 Lee가 여러 개의 돌 무더기를 놓고 게임을 진행하는 상황을 생각해 보겠습니다. 돌 무더기는 짝수 개수로 일렬로 배치되어 있으며, 각 무더기에는 piles[i]개의 돌이 들어 있습니다. 게임 규칙 게임의 목표는 게임이 끝났을 때 가장 많은 돌을 가지는 것입니다. 전체 돌의 개수가 홀수이므로 무승부는 존재하지 않습니다. Alex와 Lee는 번갈아 가며 차례를 진행하고, Alex가 항상 먼저 시작합니다. 각 차례에 플레이어는 일렬로 된 돌 무더기 중 맨 앞 또는 맨 뒤에 있는 무더기 전체를 가져가야 합니다

문제 소개사람들의 몸무게가 담긴 people 배열이 주어집니다. i번째 사람의 무게는 people[i]이며, 각 보트는 최대 limit만큼의 무게를 실을 수 있습니다. 한 보트에는 동시에 최대 2명까지만 탑승할 수 있고, 이때 두 사람의 무게 합은 limit 이하여야 합니다.목표는 모든 사람을 태우기 위해 필요한 최소 보트 수를 구하는 것입니다. 예를 들어 입력이 [3, 2, 1, 2]이고 limit이 3이라면, 다음과 같이 세 개의 보트가 필요합니다.[(1, 2), (2), (3)]접근 방법: 정렬 + 투 포인터 + 그리디이 문제

R행 C열로 이루어진 2차원 격자가 있다고 가정해 보겠습니다. 우리는 (r0, c0) 위치에서 동쪽을 향해 출발하며, 격자의 북서쪽 모서리는 첫 번째 행과 열에, 남동쪽 모서리는 마지막 행과 열에 위치합니다. 이때 시계 방향의 나선형 경로를 따라 이동하면서 격자의 모든 칸을 방문해야 합니다. 도중에 격자 경계를 벗어나더라도 걸음을 멈추지 않고 계속 진행하며(이후 다시 격자 안으로 돌아올 수 있습니다), 방문한 순서대로 좌표 목록을 만들면 됩니다. 예를 들어 격자가 아래와 같다면 − 화살표가 표시하는 경로가 곧 우리가

문제 소개 1부터 N까지 번호가 매겨진 N명의 사람이 있다고 가정해 보겠습니다. 우리는 모든 사람을 크기 제한 없이 두 개의 하위 그룹으로 나누려고 합니다. 단, 각 사람은 다른 사람 중 일부를 싫어할 수 있으며, 서로 싫어하는 두 사람은 같은 그룹에 배치되어서는 안 됩니다. 즉, dislikes[i] = [a, b]라는 조건이 주어지면 번호가 a와 b인 사람은 반드시 서로 다른 그룹에 속해야 합니다. 이처럼 모든 사람을 조건에 맞게 두 그룹으로 나누는 것이 가능한지 판별하는 것이 이 글의 핵심입니다. 예를 들어 입력이 N = 4이

문제 개요음수가 아닌 정수로 이루어진 배열 A가 주어졌다고 가정해 봅시다. 배열의 모든 연속된 부분 배열 B = [A[i], A[i+1], ..., A[j]](단, i <= j)에 대해, B에 포함된 모든 원소의 비트 OR 연산 결과 A[i] | A[i+1] | ... | A[j]를 계산합니다. 우리가 구해야 하는 것은 이렇게 만들어질 수 있는 서로 다른 결과값의 개수입니다. 동일한 결과가 여러 번 나타나더라도 최종 답에는 한 번만 포함됩니다.예를 들어 입력이 [1,1,2]라면, 만들 수 있는 부분 배열은 [1], [1], [

RLE(Run-Length Encoding, 런 길이 인코딩)는 연속적으로 반복되는 값을 압축하여 표현하는 기법입니다. 이번 글에서는 런 길이 인코딩된 시퀀스를 순회할 수 있는 반복자를 C++로 구현하는 방법을 단계별로 살펴보겠습니다.문제 정의반복자는 RLEIterator(int[] A) 생성자를 호출하여 초기화합니다. 여기서 A는 어떤 시퀀스의 런 길이 인코딩 결과입니다. 즉, 모든 짝수 인덱스 i에 대해 A[i]는 비음수 정수 A[i+1]이 시퀀스에서 반복되는 횟수를 의미합니다.이 반복자는 다음 함수를 지원합니다.next(int

정수 배열 A가 주어졌을 때, 각 원소 A[i]마다 x = -K 또는 x = K 중 하나를 선택하여 딱 한 번 더하는 문제를 생각해 봅시다. 이 과정을 거치면 새로운 배열 B가 만들어지는데, 우리가 구해야 하는 것은 B의 최댓값과 최솟값 사이 차이가 가장 작아지도록 만드는 것입니다.예를 들어 입력이 A = [0, 10], K = 2라고 해 보겠습니다. 각 원소에 ±2를 더한 결과 B = [2, 8]을 얻을 수 있으며, 이때 최댓값과 최솟값의 차이는 8 - 2 = 6입니다. 따라서 정답은 6이 됩니다.문제 해결 접근 방법이 문제는 정

선거에서 i번째 표가 times[i] 시점에 persons[i] 후보에게投되었다고 가정해 보겠습니다. 우리는 다음과 같은 쿼리 함수를 구현해야 합니다.TopVotedCandidate.q(int t) — t 시점에 선거를 리드하고 있던 후보의 번호를 반환합니다. 정확히 t 시점에投된 표도 쿼리 결과에 포함되며, 동률이 발생할 경우 동률 후보 중 가장 최근에 표를 받은 후보가 승자가 됩니다.동작 예시TopVotedCandidate([0,1,1,0,0,1,0], [0,5,10,15,20,25,30])으로 클래스를 초기화한 뒤, q(3),

정수로 이루어진 배열이 주어졌을 때, 이를 오름차순으로 정렬하는 것이 목표입니다. 예를 들어 배열이 [5,2,3,1]이라면, 정렬 후 결과는 [1,2,3,5]가 되어야 합니다. 이 문제는 대표적인 분할 정복(divide and conquer) 알고리즘인 퀵 정렬(Quick Sort)을 사용하면 효율적으로 해결할 수 있습니다. 퀵 정렬은 하나의 기준값인 피벗(pivot)을 정한 뒤, 그보다 작은 값들은 왼쪽에 큰 값들은 오른쪽에 배치하고, 나뉜 각 영역을 재귀적으로 정렬하는 방식으로 동작합니다. 문제 해결 절차 다음 단계를 따라 구

문제 개요배열 A가 주어졌을 때, 이를 왼쪽(left)과 오른쪽(right) 두 개의 부분 배열로 분할해야 합니다. 이때 분할 결과는 다음 세 가지 조건을 모두 만족해야 합니다.왼쪽 부분 배열의 모든 원소는 오른쪽 부분 배열의 모든 원소보다 작거나 같아야 합니다.왼쪽과 오른쪽 부분 배열은 모두 비어 있지 않아야 합니다.왼쪽 부분 배열의 크기는 가능한 한 가장 작아야 합니다.목표는 이러한 분할이 이루어진 후 왼쪽 부분 배열의 길이를 구하는 것입니다. 문제에서는 이러한 분할이 항상 존재한다고 보장합니다.예를 들어 입력이 [5,0,3,8

문제 설명0과 1로만 이루어진 문자열이 주어졌다고 가정해 보겠습니다. 이러한 문자열은 일정 개수의 0(0개일 수도 있음) 뒤에 일정 개수의 1(역시 0개일 수도 있음)이 이어지는 형태일 때 단조 증가(monotonic increasing)라고 합니다.우리는 0과 1로 구성된 문자열 S를 가지고 있으며, 임의의 0을 1로 바꾸거나 1을 0으로 뒤집을(flip) 수 있습니다. 이때 S를 단조 증가 문자열로 만들기 위해 필요한 최소 뒤집기 횟수를 구하는 것이 이 문제의 목표입니다.예를 들어 입력이 010110이라면 출력은 2입니다. 두

0과 1로만 이루어진 배열 A가 주어졌을 때, 원소의 합이 정확히 S가 되는 비어 있지 않은 부분 배열의 개수를 구하는 문제입니다.예를 들어 입력이 [1,0,1,0,1]이고 S = 2라면, 답은 4가 됩니다. 조건을 만족하는 부분 배열은 다음과 같습니다.[1, 0, 1] (인덱스 0~2)[1, 0, 1, 0] (인덱스 0~3)[0, 1, 0, 1] (인덱스 1~4)[1, 0, 1] (인덱스 2~4)접근 방법: 슬라이딩 윈도우이 문제는 슬라이딩 윈도우 기법을 응용하면 O(N) 시간에 해결할 수 있습니다. 핵심 아이디어는 합이 x 이하

문제 개요 고정된 값 N이 주어졌을 때, 배열 A가 1부터 N까지의 정수로 이루어진 순열(permutation)이면서 다음 조건을 만족하면 이를 아름다운 배열(Beautiful Array)이라고 정의합니다. 모든 i < j에 대하여, i < k < j를 만족하면서 A[k] × 2 = A[i] + A[j]가 성립하는 k가 존재하지 않아야 합니다. 쉽게 풀어 설명하면, 배열에서 임의의 세 원소를 순서대로 골랐을 때 가운데 값이 양쪽 끝 값의 평균이 되는 경우, 즉 세 값이 등차수열 관계로 배치되는 경우가 없어야 한다

정수 배열 A가 주어졌다고 가정해 봅시다. 여기서 한 번의 이동(move)이란 배열의 임의의 원소 A[i]를 선택하여 1만큼 증가시키는 연산을 의미합니다. 우리의 목표는 배열 내 모든 값이 서로 중복되지 않도록(고유하게) 만드는 데 필요한 최소 이동 횟수를 구하는 것입니다.예를 들어 입력이 [3, 2, 1, 2, 1, 7]이라면 출력은 6입니다. 총 6번의 이동 후 배열은 [3, 4, 1, 2, 5, 7]이 될 수 있으며, 5번 이하의 이동으로는 모든 값을 고유하게 만드는 것이 불가능함을 알 수 있습니다.문제 해결 접근 방식이 문제

초기 파워 P와 초기 점수 0점, 그리고 하나의 토큰 가방이 주어져 있다고 가정해 보겠습니다. 각 토큰은 최대 한 번만 사용할 수 있으며, token[i]라는 고유한 값을 가지고 있습니다. 각 토큰은 다음 두 가지 방식으로 활용할 수 있습니다.앞면으로 사용: 현재 파워가 token[i] 이상이라면, 해당 토큰을 앞면으로 내려놓아 token[i]만큼 파워를 잃는 대신 1점을 얻습니다.뒷면으로 사용: 현재 점수가 최소 1점 이상이라면, 해당 토큰을 뒷면으로 내려놓아 token[i]만큼 파워를 얻는 대신 1점을 잃습니다.우리의 목표는 토

문제 개요고유한 숫자가 적힌 카드 한 벌(deck)이 있다고 가정해 봅시다. 우리는 이 카드 덱을 원하는 어떤 순서로든 배열할 수 있습니다. 처음에는 모든 카드가 앞면이 보이지 않는 상태(뒷면)로 한 벌에 담겨 있습니다. 이제 다음 과정을 모든 카드가 공개될 때까지 반복합니다.덱에 카드가 남아 있다면, 맨 위의 카드를 꺼내 공개하고 제거합니다.덱에 아직 카드가 남아 있다면, 그 다음 맨 위의 카드를 덱의 맨 아래로 옮깁니다.아직 공개되지 않은 카드가 남아 있다면 첫 번째 단계로 돌아가고, 그렇지 않으면 과정을 종료합니다.우리가 구해

문제 소개 길이가 짝수인 정수 배열 A가 있다고 가정해 봅시다. 이 배열을 임의로 재정렬했을 때, 모든 0 <= i < len(A)/2에 대해 A[2*i + 1] = 2 * A[2*i] 조건을 만족하도록 배치할 수 있는 경우에만 true를 반환해야 합니다.예를 들어 입력이 [3,1,3,6]이라면 어떤 순서로 배치해도 조건을 충족할 수 없으므로 결과는 false입니다. 반면 [4,-2,2,-4]는 [-2,4,-4,2]처럼 재정렬하면 조건을 만족하므로 true를 반환합니다. 접근 방법 이 문제는 각 원소의 빈도수를 저장하는 맵(map)

문제 개요 한 줄로 늘어선 8개의 감옥 칸이 있으며, 각 칸에는 수감자가 있거나 비어 있습니다. 매일이 지나면 각 칸의 점유 여부가 다음 규칙에 따라 바뀝니다. 어떤 칸의 양쪽 이웃 칸이 모두 점유 중이거나 모두 비어 있는 경우, 해당 칸은 다음 날 점유 상태가 됩니다. 그 외의 경우에는 해당 칸이 비게 됩니다. 참고로 맨 왼쪽 칸과 맨 오른쪽 칸은 이웃이 하나뿐이기 때문에, 하루가 지나면 항상 빈 칸으로 바뀝니다. 감옥의 현재 상태는 배열 cells로 표현합니다. i번째 칸에 수감자가 있으면 cells[i] = 1, 비어 있으

문제 개요정수 배열 A가 주어졌을 때, 램프(ramp)란 i < j이면서 A[i] <= A[j]를 만족하는 인덱스 쌍 (i, j)를 의미하며, 이때 램프의 너비는 j - i로 정의됩니다. 목표는 배열 A에서 가장 넓은 램프의 너비를 구하는 것이고, 만약 램프가 하나도 존재하지 않는다면 0을 반환해야 합니다.예를 들어 입력이 [6,0,8,2,1,5]라고 한다면 결과는 4가 됩니다. 최대 너비 램프는 (i, j) = (1, 5)에서 만들어지는데, A[1] = 0이고 A[5] = 5이므로 너비는 5 - 1 = 4입니다.알고리즘

문제 소개길이가 N인 모든 음이 아닌 정수 중에서, 인접한 두 자릿수의 절댓값 차이가 항상 K가 되는 숫자들을 모두 찾는 문제입니다. 단, 답에 포함되는 숫자는 앞자리가 0으로 시작하면 안 되며, 숫자 0 자체만이 유일한 예외입니다. 결과는 어떤 순서로 반환해도 무방합니다.예를 들어 N = 3, K = 7이라면 출력은 [181, 292, 707, 818, 929]가 됩니다. 여기서 070은 유효하지 않은데, 그 이유는 맨 앞에 불필요한 0(선행 영)이 붙어 있기 때문입니다.접근 방법: 동적 계획법(DP)이 문제는 자릿수를 하나씩 확