문제 설명문자열 배열 arr가 주어졌을 때, 배열의 부분 수열(sub-sequence)을 연결하여 만든 문자열 s를 생각해 봅시다. 단, s는 중복 없는 고유한 문자들로만 구성되어야 합니다. 이때 s가 가질 수 있는 최대 길이를 구하는 것이 목표입니다.예를 들어 입력이 [cha, r, act, ers]라면 출력은 6이 됩니다. chaers와 acters처럼 각각 고유한 문자만으로 이루어진 길이 6짜리 문자열을 만들 수 있기 때문입니다.접근 방법이 문제는 브루트포스 방식으로 모든 가능한 조합을 탐색하면서 해결할 수 있습니다. 핵심 아

문제 소개 n개의 열과 2개의 행으로 구성된 행렬에 대해 다음과 같은 정보가 주어진다고 가정해 보겠습니다. 행렬의 모든 요소는 0 또는 1이어야 합니다. 0번째(위쪽) 행에 있는 요소들의 합은 upper로 주어집니다. 1번째(아래쪽) 행에 있는 요소들의 합은 lower로 주어집니다. i번째 열(0부터 시작하는 인덱스 기준)에 있는 요소들의 합은 colsum[i]이며, colsum은 길이가 n인 정수 배열로 주어집니다. 이때 주어진 upper, lower, colsum 정보를 바탕으로 원래의 행렬을 재구성하는 것이 과제입니다. 결

음이 아닌 정수 n이 주어졌을 때, 이 숫자를 특정 규칙에 따라 인코딩된 형태로 변환하는 문제를 살펴보겠습니다. 인코딩 규칙은 다음 표와 같습니다.숫자인코딩된 값0 (빈 문자열)10213004015106117000표에서 확인할 수 있듯이, 각 숫자는 해당 범위 내에서 이진수처럼 순차적으로 증가하며, 자릿수가 늘어날 때마다 앞자리가 초기화되는 패턴을 보입니다. 예를 들어 숫자가 23이라면 결과는 1000이 되고, 54라면 10111이 됩니다.문제 해결 접근 방법이 문제는 로그 연산과 이진수 변환을 조합하면 효율적으로 해결할 수 있습니

문제 이해하기 여러 개의 지역(region) 목록이 주어지며, 각 목록의 첫 번째 지역은 해당 목록에 속한 나머지 모든 지역을 포함하는 상위 지역입니다. 즉, 지역 X가 지역 Y를 포함하고 있다면 X는 Y보다 더 넓은(상위의) 지역이고, 정의에 따라 모든 지역은 스스로를 포함합니다. 이러한 구조에서 두 지역 r1과 r2가 주어졌을 때, 두 지역을 모두 포함하는 가장 작은 공통 영역을 찾아야 합니다. 한 지역을 포함하는 상위 지역은 유일하다는 조건이 보장되므로 포함 관계는 트리 형태를 이루며, 정답 역시 항상 하나로 결정됩니다. 예

정수 배열 nums가 주어졌을 때, 배열 요소들의 합이 3으로 나누어떨어지는 경우 중 가능한 최대 합을 구하는 문제입니다.예를 들어 입력이 [3, 6, 5, 1, 8]이라면 출력은 18이 됩니다. 이는 부분 수열 [3, 6, 1, 8]을 선택했을 때 합이 18이 되고, 18은 3으로 나누어떨어지기 때문입니다. 만약 5까지 포함하면 합이 23이 되어 3으로 나누어떨어지지 않으므로 제외해야 합니다.문제 해결 접근 방식이 문제는 동적 계획법(Dynamic Programming)을 활용하여 효율적으로 해결할 수 있습니다. 핵심 아이디어는

문제 개요두 개의 정수 tomatoSlices(토마토 슬라이스 수)와 cheeseSlices(치즈 슬라이스 수)가 주어집니다. 이 재료들은 서로 다른 종류의 버거를 만드는 데 사용됩니다.점보 버거(Jumbo Burger): 토마토 슬라이스 4개와 치즈 슬라이스 1개 필요스몰 버거(Small Burger): 토마토 슬라이스 2개와 치즈 슬라이스 1개 필요목표는 [점보 버거 수, 스몰 버거 수] 형태의 조합을 찾아, 버거를 만든 뒤 남는 토마토 슬라이스와 치즈 슬라이스가 모두 0이 되도록 하는 것입니다. 만약 주어진 재료를 전부 사용할

문제 소개m x n 크기의 이진 행렬(binary matrix)이 주어졌을 때, 모든 원소가 1인 정사각형 부분 행렬의 개수를 세는 문제입니다. 예를 들어 다음과 같은 행렬이 있다고 가정해 보겠습니다.011111110111이 경우 정사각형은 총 15개가 됩니다. 크기 1x1짜리 정사각형이 10개, 2x2짜리 정사각형이 4개, 그리고 3x3짜리 정사각형이 1개 있는 것입니다.해결 방법이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 위치에서 만들 수 있는 가장

n명의 사람이 있고, 각 사람의 ID는 0부터 n-1까지의 범위에 있다고 가정해 보겠습니다. 모든 사람은 정확히 하나의 그룹에만 속합니다. 길이가 n인 배열 groupSizes가 주어지며, 이 배열은 각 사람이 속한 그룹의 크기를 나타냅니다. 우리의 목표는 실제 그룹들을 찾아내고, 각 그룹에 포함된 사람들의 ID를 구하는 것입니다.예를 들어 입력이 [3,3,3,3,3,1,3]이라면 출력은 [[5], [0, 1, 2], [3, 4, 6]]이 됩니다. 물론 [[2,1,6],[5],[0,4,3]] 또는 [[5],[0,6,2],[4,3,1

정수 배열 nums와 임계값을 나타내는 정수 k가 주어졌다고 가정해 봅시다. 우리는 양의 정수인 제수(divisor)를 하나 선택하여 배열의 모든 원소를 이 값으로 나눈 뒤, 나눈 결과들을 모두 더해야 합니다. 이때 구해야 하는 것은 그 합이 임계값 k 이하가 되도록 만드는 가장 작은 제수입니다.예를 들어 nums = [1,2,5,9]이고 k = 6이라면 출력은 5가 됩니다. 제수가 1일 때 합은 (1+2+5+9) = 17이며, 제수가 4일 때는 (1+1+2+3) = 7, 제수가 5일 때는 (1+1+1+2) = 5가 됩니다. 따라서

문제 개요 정수의 각 자릿수가 바로 앞 자릿수보다 정확히 1만큼 클 때, 그 수를 연속 숫자(Sequential Digits)라고 합니다. 이번 글에서는 주어진 범위 [low, high]에 포함된 모든 연속 숫자를 오름차순으로 정렬된 리스트 형태로 구하는 방법을 알아보겠습니다. 예를 들어 low = 100, high = 300이 주어진다면, 이 범위 안에 속하는 연속 숫자는 123과 234 두 개뿐이므로 출력 결과는 [123, 234]가 됩니다. 알고리즘 접근 방식 이 문제는 가능한 모든 연속 숫자를 직접 생성한 뒤, 주어진 범위

정수 배열 nums와 양의 정수 k가 주어졌을 때, 이 배열을 각각 k개의 연속된 숫자로 이루어진 집합들로 나눌 수 있는지 판별하는 문제입니다. 나누는 것이 가능하면 true를, 불가능하면 false를 반환해야 합니다.예를 들어 입력이 [1,2,3,3,4,4,5,6]이고 k = 4라면, 출력은 true가 됩니다. 배열을 [1,2,3,4]와 [3,4,5,6] 두 그룹으로 나눌 수 있기 때문입니다.문제 해결 접근 방법이 문제는 다음 단계를 통해 해결할 수 있습니다.숫자의 등장 횟수를 저장할 맵(map) m을 생성하고, n := nums

정수 배열 arr와 목표 값 target이 주어졌다고 가정해 보겠습니다. 이때 배열에서 특정 정수 value보다 큰 모든 요소를 value로 변경한 뒤, 변경된 배열의 합이 목표 값에 최대한 가까워지도록 하는 정수를 찾아야 합니다. 후보 값이 여러 개일 경우에는 그중 가장 작은 값을 반환합니다. 예를 들어 배열이 [4, 9, 3]이고 목표 값이 10이라면 정답은 3입니다. 3을 선택하면 배열이 [3, 3, 3]이 되어 합이 9가 되고, 이는 10에 가장 근접한 결과입니다. 문제 해결 접근 방법 이 문제는 다음 단계를 따라 해결할 수

문제 소개처음에 모두 꺼져 있는 전구가 n개 있다고 가정해 봅시다. 첫 번째 라운드에서는 모든 전구를 켭니다. 두 번째 라운드에서는 매 두 번째 전구를 끕니다. 세 번째 라운드에서는 매 세 번째 전구의 상태를 반전시키는데, 꺼져 있으면 켜고 켜져 있으면 끕니다. 이런 식으로 i번째 라운드에서는 매 i번째 전구를 반전시키며, n번째 라운드에서는 마지막 전구 하나만 반전시킵니다.결국 우리가 구해야 할 값은 n번의 라운드가 모두 끝난 뒤 켜져 있는 전구의 개수입니다. 예를 들어 입력이 3이라면 정답은 1이 됩니다.예시 과정 살펴보기초기

rand7() 함수가 1부터 7 사이의 균등한(uniform) 무작위 정수를 반환한다고 가정해 봅시다. 이때 별도의 난수 생성 라이브러리 함수를 사용하지 않고, 1부터 10 사이의 균등한 무작위 정수를 반환하는 rand10() 함수를 구현하는 것이 목표입니다. 접근 방법: 기각 샘플링(Rejection Sampling) 핵심 아이디어는 기각 샘플링입니다. rand7()을 두 번 호출하면 각 호출마다 7가지 결과가 나올 수 있으므로, 총 7 × 7 = 49개의 동일한 확률을 가진 조합을 만들 수 있습니다. 이 조합들을 다음 식으로 하

안데르센 동화 속 성냥팔이 소녀를 떠올려 봅시다. 소녀가 가진 성냥개비의 개수와 길이를 정확히 알고 있다면, 이 성냥개비를 전부 사용하여 하나의 정사각형을 만들 수 있는 방법을 찾아야 합니다. 단, 성냥개비를 부러뜨릴 수는 없고 서로 이어 붙일 수만 있으며, 각 성냥개비는 정확히 한 번씩 사용해야 합니다.입력으로는 소녀가 가진 성냥개비들의 길이가 주어지고, 출력으로는 모든 성냥개비를 사용해 정사각형을 만들 수 있는지 여부(true 또는 false)를 반환해야 합니다. 예를 들어 입력이 [1,1,2,2,2]라면 답은 true입니다.

문제 개요0을 m개, 1을 n개 가지고 있다고 가정해 보겠습니다. 그리고 이진수(0과 1)로만 이루어진 문자열 배열이 하나 주어집니다. 목표는 주어진 m개의 0과 n개의 1을 사용해 만들 수 있는 문자열의 최대 개수를 구하는 것이며, 각 0과 1은 최대 한 번씩만 사용할 수 있습니다.예를 들어 배열이 ["10", "0001", "111001", "1", "0"]이고 m = 5, n = 3이라면 정답은 4입니다. 5개의 0과 3개의 1로 &quo

원의 반지름과 중심의 x-y 좌표가 주어졌을 때, 원 내부에 균일하게 분포하는 랜덤한 점을 생성하는 randPoint() 함수를 작성해야 합니다. 구현 시 다음 사항들을 반드시 염두에 두어야 합니다.입력값과 출력값은 모두 부동소수점(floating-point) 형태입니다.원의 반지름과 중심 좌표는 클래스 생성자를 통해 전달됩니다.원의 둘레(경계) 위에 있는 점도 원 안에 포함된 것으로 간주합니다.randPoint()는 랜덤 점의 x좌표와 y좌표를 순서대로 반환합니다.예를 들어 입력이 [10, 5, -7.5]라면, [11.15792,

1과 2로만 이루어진 문자열 S가 있다고 상상해 보세요. 이 문자열은 특별한 성질 때문에 마법 문자열(Magical String)이라고 불리는데, 그 비결은 문자 1과 2가 연속해서 등장하는 횟수를 순서대로 이어 붙였을 때 그 결과가 놀랍게도 문자열 S 자신이 된다는 점입니다.마법 문자열 S의 첫 부분은 다음과 같습니다.S = "1221121221221121122……"S에서 연속된 같은 문자들을 그룹으로 묶어 보면 다음과 같습니다.1 | 22 | 11 | 2 | 1 | 22 | 1 | 22 | 11 | 2 | 11

문제 소개 정수 배열이 주어졌을 때, 해당 배열에서 만들 수 있는 모든 증가 부분 수열(increasing subsequence)을 찾아야 합니다. 이때 각 부분 수열의 길이는 최소 2 이상이어야 한다는 조건이 있습니다. 예를 들어 배열이 [4, 6, 7, 7]이라면 출력은 다음과 같습니다. [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7, 7], [4, 7, 7]] 주의할 점은, 값이 같은 원소가 여러 개 있더라도 동일한 부분 수열이 중복해서 출력되지 않도록 처리해

문제 소개리그 오브 레전드(LOL)의 세계에 티모(Teemo)라는 영웅이 있다고 가정해 봅시다. 티모의 공격은 적인 애쉬(Ashe)에게 중독 상태를 일으킵니다. 여기서 티모가 애쉬를 공격한 시점들을 오름차순으로 정렬한 배열과, 한 번 공격할 때마다 중독이 지속되는 시간이 주어집니다. 우리가 구해야 하는 것은 애쉬가 중독 상태로 있게 되는 총 시간입니다.단, 티모는 특정 시점의 시작 부분에서 공격하며, 공격하는 순간 애쉬는 즉시 중독 상태에 빠진다고 가정합니다.예제로 이해하기공격 시점 배열이 [1, 4]이고 중독 지속 시간이 2초라면