문제 개요 등차수열의 항 n-1개가 담긴 배열 nums가 있다고 가정해 보겠습니다. 이 배열에서 첫 번째 항이나 마지막 항을 제외한 하나의 요소가 미리 제거되었고, 우리의 목표는 바로 그 제거된 숫자를 찾아내는 것입니다. 예를 들어 입력이 nums = [5, 7, 11, 13]이라면 출력은 9가 됩니다. 이 수열의 항들은 2i+5 공식을 따르는데, i = 2일 때 2*2 + 5 = 9가 되어야 하지만 해당 값이 빠져 있기 때문입니다. 해결 접근 방식 이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수

문제 개요 각 쿼리가 세 값 [ai, bi, di]로 구성된 쿼리 목록 Q가 주어졌다고 가정해 봅시다. 우리는 좌표 평면 위의 원점 (0, 0)에서 출발하며, 한 번의 걸음으로 현재 위치 (x₁, y₁)에서 새로운 위치 (x₂, y₂)로 이동할 수 있습니다. 단, 이때 두 점 사이의 유클리드 거리는 반드시 a 이상, b 이하여야 합니다. 목표는 각 쿼리마다 원점 (0, 0)에서 목적지 (di, 0)까지 도달하는 데 필요한 최소 걸음 수를 구하는 것입니다. 예시 입력이 Q = [(2,3,1), (1,2,0), (3,4,11)]일 때

숫자로 이루어진 리스트 nums가 주어졌을 때, 이 리스트에는 값이 1인 원소가 최소 하나 이상 포함되어 있습니다. 우리가 확인해야 할 것은 모든 1이 서로 인접하게(연속적으로) 나타나는지 여부입니다.예를 들어 입력이 nums = [8, 2, 1, 1, 1, 3, 5]라면, 세 개의 1이 모두 붙어 있으므로 출력은 True가 됩니다. 반면 [1, 2, 1]처럼 1 사이에 다른 숫자가 끼어 있다면 False를 반환해야 합니다.해결 접근 방식이 문제는 상태 플래그 하나만으로 간단히 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

숫자로 이루어진 리스트 nums가 주어졌다고 가정해 봅시다. 이 문제의 목표는 배열 안에서 x + 1 역시 배열에 존재하는 요소 x의 개수를 구하는 것입니다.예를 들어 입력이 nums = [4, 2, 3, 3, 7, 9]라고 한다면 결과는 3이 됩니다. 2+1=3이 배열에 존재하고, 3+1=4 역시 존재하며, 중복된 값 3 하나까지 포함되어 총 3개이기 때문입니다.문제 해결 접근 방법이 문제는 Counter를 활용하면 효율적으로 해결할 수 있습니다. 다음과 같은 단계를 따릅니다.answer를 0으로 초기화합니다.c := nums에

크기가 n + 1인 리스트 nums가 있고, 그 요소들은 1, 2, ..., n 범위에서 선택되었다고 가정해 보겠습니다. 비둘기집 원리(서랍 원리)에 따르면 요소의 개수가 선택 가능한 값의 종류보다 많기 때문에 반드시 중복된 값이 하나 이상 존재합니다. 이때 우리는 그 중복 값을 찾아야 하며, 목표는 O(n) 시간 복잡도와 상수 공간으로 문제를 해결하는 것입니다.예를 들어 입력이 nums = [2, 1, 4, 3, 5, 4]라면 출력은 4가 됩니다.해결 접근 방법핵심 아이디어는 간단한 산술 연산입니다. 1부터 n까지의 합은 공식으로

points라는 리스트에 데카르트 좌표점들이 담겨 있다고 가정해 보겠습니다. 이 점들을 극각(polar angle)을 기준으로 정렬해야 합니다. 극각의 범위는 0부터 2π까지이며, 만약 여러 점이 동일한 극각을 가진다면 원점으로부터의 거리를 기준으로 정렬합니다.예를 들어 입력이 다음과 같다면,points = [(1,1), (1,-2), (-2,2), (5,4), (4,5), (2,3), (-3,4)]출력 결과는 다음과 같습니다.[(5, 4), (1, 1), (4, 5), (2, 3), (-3, 4), (-2, 2), (1, -2)]

문제 설명 두 개의 리스트 nums1과 nums2가 주어지며, 두 리스트의 모든 요소는 1부터 6 사이의 값을 가집니다. 사용할 수 있는 연산은 nums1 또는 nums2에서 숫자 하나를 골라 그 값을 1부터 6 사이의 임의의 숫자로 바꾸는 것입니다. 이때 두 배열의 합이 서로 같아지도록 만드는 데 필요한 최소 연산 횟수를 구해야 하며, 어떻게 해도 같게 만들 수 없다면 -1을 반환합니다. 예를 들어 nums1 = [1, 4], nums2 = [5, 4, 4]가 입력으로 주어졌다고 해봅시다. 먼저 nums1의 1을 6으로 바꾸면 n

문제 개요숫자로 이루어진 리스트 nums가 주어졌을 때, nums[i]와 nums[j]의 값이 서로 같으면서 i < j를 만족하는 인덱스 쌍의 개수를 구하는 문제입니다.예를 들어 입력이 nums = [5, 4, 5, 4, 4]라면 출력은 4가 됩니다. 조건을 만족하는 인덱스 쌍이 (0, 2), (1, 3), (1, 4), (3, 4)로 총 네 개이기 때문입니다.해결 접근 방법모든 인덱스 쌍을 하나씩 비교하는 브루트 포스 방식은 O(n²)의 시간 복잡도를 가지므로, 데이터 크기가 커지면 비효율적입니다. 대신 다음 단계를 따르면

숫자 n이 주어졌을 때, 0과 9 두 숫자로만 구성되면서 n의 배수가 되는 가장 작은 양의 정수 x를 찾는 것이 이번 글의 목표입니다. 예를 들어 n = 26이 주어지면 정답은 90090입니다. 90090은 0과 9로만 이루어져 있으며, 26 × 3465 = 90090이므로 26의 배수이기 때문입니다. 핵심 아이디어: 이진수 활용하기 0과 9로 이루어진 수를 일일이 만들어 검사하는 것은 비효율적입니다. 대신 이진수(binary)의 성질을 활용하면 깔끔하게 해결할 수 있습니다. 모든 이진수는 0과 1로만 구성됩니다. 여기서 이진 표현

숫자로 이루어진 리스트 nums가 주어졌을 때, 자신의 값과 출현 빈도가 정확히 같은 요소가 존재하는지 확인해야 하는 문제입니다.예를 들어 입력이 nums = [2,5,7,5,3,5,3,5,9,9,5]라고 한다면 결과는 True가 됩니다. 숫자 5가 리스트 안에 정확히 5번 등장하기 때문입니다.문제 해결 접근 방법이 문제는 다음 단계를 따라 해결할 수 있습니다.nums에 포함된 각 요소의 빈도를 계산하여 저장합니다.각 값 i와 해당 빈도 j를 하나씩 순회합니다.i와 j가 같다면 즉시 True를 반환합니다.모든 요소를 확인한 후에도

리스트 nums가 주어졌을 때, 리스트 안의 모든 숫자가 각각 짝수 번 나타나는지 확인해야 하는 문제입니다. 이때 추가적인 메모리 사용 없이, 즉 상수 공간(constant space)만으로 해결하는 것이 핵심 조건입니다.예를 들어 입력이 nums = [8, 9, 9, 8, 5, 5]라면 출력은 True가 됩니다. 모든 숫자가 두 번씩 등장하기 때문입니다.해결 접근 방식다음 단계에 따라 문제를 해결할 수 있습니다.nums의 길이가 홀수라면 즉시 False를 반환합니다. 요소 개수가 홀수이면 모든 값이 짝수 번 등장하는 것은 불가능합

문제 개요숫자로 이루어진 리스트 nums가 주어졌다고 가정해 봅시다. 우리의 목표는 이 리스트 안에 있는 모든 피크(peak, 봉우리) 요소의 인덱스를 찾아내는 것입니다.여기서 인덱스 i가 피크가 되는 조건은 다음과 같습니다.i = 0일 때: nums[i] > nums[i + 1]i = n - 1일 때: nums[i] > nums[i - 1]그 외의 경우: nums[i - 1] < nums[i] > nums[i + 1]즉, 리스트의 첫 번째 요소는 오른쪽 이웃보다, 마지막 요소는 왼쪽 이웃보다 클 때 피크이며,

숫자 n이 주어졌을 때, 이 숫자가 피보나치 수열에 포함되어 있는지 확인해야 합니다. 피보나치 수열은 f(0) = 0, f(1) = 1이며, i가 2부터 n까지 각 항이 f(i) = f(i-1) + f(i-2) 공식을 따르는 수열입니다.예를 들어 입력값이 n = 13이라면 출력은 True가 됩니다. 피보나치 수열의 항들은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34와 같이 나열되므로 13이 수열에 존재하기 때문입니다.해결 접근 방식이 문제는 황금비(Golden Ratio)의 성질을 활용하면 효율적으로 해결할 수 있습니다

문제 설명숫자로 이루어진 리스트 rooms와 목표값 t가 주어졌을 때, rooms에서 값이 t 이상인 첫 번째 요소를 찾아야 합니다. 만약 조건을 만족하는 방이 없다면 -1을 반환합니다.예를 들어, 입력이 rooms = [20, 15, 35, 55, 30]이고 t = 30이라면 출력은 35가 됩니다. 앞의 두 방(20, 15)은 목표값 30에 미치지 못하고, 세 번째 방인 35가 처음으로 조건을 충족하기 때문입니다.해결 접근 방법이 문제는 간단한 선형 탐색(linear search)으로 해결할 수 있습니다. 단계는 다음과 같습니다.

서로 중복되지 않는 고유한 요소들로 구성되어 있고 오름차순으로 정렬된 리스트 nums가 있다고 가정해 보겠습니다. 이때 nums[i] = i를 만족하는 최소 인덱스 i를 찾아야 하며, 조건을 만족하는 인덱스가 존재하지 않으면 -1을 반환해야 합니다. 또한 이 문제는 O(log n) 시간 복잡도 내에 해결해야 한다는 제약이 있습니다. 예를 들어 입력이 nums = [-4, -1, 2, 3, 8]이라면 결과는 2입니다. nums[2] = 2와 nums[3] = 3이 모두 조건을 만족하지만, 그중 더 작은 값이 2이기 때문입니다. 접근

문제 개요 소문자로만 이루어진 문자열 s가 주어졌다고 가정해 봅시다. 우리가 찾아야 할 것은, 문자열 내 서로 다른 위치에 존재하는 또 다른 부분 문자열과 아나그램(anagram) 관계에 있는 모든 부분 문자열입니다. 최종 결과는 사전순(lexicographic order)으로 정렬된 리스트 형태로 반환해야 합니다. 예를 들어 입력이 s = abcba라면 출력은 다음과 같습니다. [a, a, ab, abc, abcb, b, b, ba, bc, bcba, cb, cba] 위 결과의 각 부분 문자열은 원본 문자열 자체 안에서 서로 다른

두 개의 입력값 n과 k가 주어졌을 때, n이 정확히 k개의 소수의 합으로 표현될 수 있는지 판별하는 문제입니다. 예를 들어 n = 30, k = 3이 입력으로 주어진다면, 30은 2 + 11 + 17처럼 세 개의 소수의 합으로 나타낼 수 있으므로 결과는 True가 됩니다. 문제 해결 접근 방식 이 문제는 다음과 같은 논리적 단계를 통해 효율적으로 해결할 수 있습니다. n < 2k인 경우: 가장 작은 소수는 2이므로, k개의 소수의 합으로 만들 수 있는 최솟값은 2k입니다. 따라서 n이 2k보다 작으면 표현이 불가능하며 Fa

숫자들이 담긴 리스트 nums가 주어졌을 때, 이 리스트의 모든 정수를 나눌 수 있는 가장 큰 양의 정수, 즉 최대공약수(GCD)를 찾아야 합니다.예를 들어 입력이 nums = [15, 81, 78]이라면 출력은 3이 됩니다. 3은 15, 81, 78 세 숫자를 모두 나눌 수 있는 가장 큰 정수이기 때문입니다.해결 접근 방식최대공약수에는 중요한 수학적 성질이 있습니다. 바로 gcd(a, b, c) = gcd(gcd(a, b), c)처럼 여러 수의 GCD를 두 수씩 묶어 순차적으로 계산할 수 있다는 점입니다. 이 성질을 이용하면 다음

nums라는 숫자 리스트가 주어졌을 때, 특정 인덱스 i를 기준으로 왼쪽에 있는 숫자들의 합과 오른쪽에 있는 숫자들의 합이 서로 같아지는 가장 작은 인덱스를 찾는 것이 이번 문제의 목표입니다. 만약 조건을 만족하는 인덱스가 존재하지 않는다면 -1을 반환하면 됩니다.예를 들어 입력이 nums = [8,2,3,6,5,2,5,9,1,2]라고 해보겠습니다. 이 경우 정답은 4입니다. 인덱스 4를 기준으로 왼쪽 요소들은 [8,2,3,6]으로 합이 19이고, 오른쪽 요소들은 [2,5,9,1,2]로 합 역시 19이기 때문입니다.문제 해결 접근

두 개의 문자열 s1과 s2가 주어졌을 때, 두 문자열 모두의 특수 부분 문자열(special substring)에 해당하는 가장 긴 문자열 s3의 크기를 구하는 프로그램을 만들어 보겠습니다.여기서 문자열 x가 다른 문자열 y의 특수 부분 문자열이라는 것은, y에서 0개 이상의 문자를 제거했을 때 x를 얻을 수 있다는 의미입니다. 즉, 이 문제는 널리 알려진 최장 공통 부분 수열(Longest Common Subsequence, LCS) 문제와 본질적으로 같은 문제입니다.예를 들어 입력이 s1 = pineapple, s2 = peo