XY 평면 위에 여러 점들이 배열 형태로 주어져 있다고 가정해 봅시다. 이 점들로 만들 수 있는 직사각형 중 가장 작은 넓이를 구하는 것이 목표입니다. 단, 직사각형의 변은 반드시 X축과 Y축에 각각 평행해야 하며, 직사각형을 만들 수 없는 경우에는 0을 반환해야 합니다.예를 들어 점들의 배열이 [(1, 1), (1, 3), (3, 1), (3, 3), (2, 2)]와 같다면 결과는 4가 됩니다. 점 (1, 1), (1, 3), (3, 1), (3, 3) 네 개를 꼭짓점으로 하는 직사각형이 만들어지기 때문입니다. 가로 길이가 2,

n개의 요소를 가진 배열이 있다고 가정해 보겠습니다. 이 배열에는 각 책의 평점이 담겨 있습니다. 우리의 목표는 다음 조건을 만족하면서 모든 책을 구입할 때 드는 최소 비용을 구하는 것입니다.각 책의 비용은 최소 1달러 이상이어야 합니다.어떤 책의 평점이 인접한(왼쪽 또는 오른쪽) 책보다 높다면, 해당 책의 비용 역시 인접한 책보다 높아야 합니다.문제 예시예를 들어 평점 배열이 [1, 3, 4, 3, 7, 1]과 같이 주어졌다고 해봅시다. 이 경우 정답은 10이 됩니다. 실제 비용 계산은 1 + 2 + 3 + 1 + 2 + 1 =

n개의 숫자로 이루어진 배열이 있다고 가정해 봅시다. 이때 배열 안에서 자신보다 큰 요소가 최소 두 개 이상 존재하는 모든 원소를 찾아야 합니다. 예를 들어 배열이 A = [2, 8, 7, 1, 5]라면 결과는 [2, 1, 5]가 됩니다. 2, 1, 5는 각각 8, 7처럼 자신보다 큰 값을 두 개 이상 가지고 있기 때문입니다.문제 해결 접근 방법이 문제는 정렬 없이도 선형 시간에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.배열을 한 번 순회하며 최댓값(first_max)과 두 번째로 큰 값(second_max)을 구합니다

두 개의 문자열 A와 B가 있고, 두 문자열의 길이는 서로 같다고 가정해 보겠습니다. 한 번의 시프트(shift) 연산으로 문자열 B를 한 칸씩 회전할 수 있으며, 목표는 A와 B 사이의 공통 접두사(prefix) 길이를 최대화하기 위해 필요한 최소 시프트 횟수를 구하는 것입니다.예를 들어 A = programminglanguage, B = computerprogramming이라고 할 때, B를 왼쪽으로 8번 회전하면 programmingcomputer가 되어 A와의 공통 접두사가 programming(길이 11)으로 최대가 됩니다

자연수 N이 주어졌을 때, 1부터 N 사이에 존재하는 거의 소수(almost prime)의 개수를 구하는 것이 목표입니다. 거의 소수란 서로 다른 소인수를 정확히 두 개 가지는 수를 의미합니다. 이때 소수가 아닌 약수는 몇 개가 있더라도 상관없으며, 핵심은 서로 다른 소수 인수가 정확히 두 개여야 한다는 점입니다. 예를 들어 N이 10이라면 정답은 2입니다. 해당 범위에서 조건을 만족하는 수는 6(= 2 × 3)과 10(= 2 × 5) 두 개뿐이기 때문입니다. 접근 방법 – 에라토스테네스의 체 활용 이 문제는 에라토스테네스의 체(

문제 개요n개의 요소로 이루어진 배열이 있다고 가정해 보겠습니다. 이때 우리가 구해야 할 것은 배열 요소들의 최소 합이며, 단 하나의 조건이 붙습니다. 바로 연속된 세 개의 요소로 이루어진 구간마다 적어도 하나의 요소를 반드시 선택해야 한다는 것입니다.예를 들어 배열이 [1, 2, 3, 6, 7, 1]이라면 출력은 4가 됩니다. 3과 1을 선택하면 3 + 1 = 4이기 때문입니다. 이 배열에서 확인해야 하는 연속 구간은 [1, 2, 3], [2, 3, 6], [3, 6, 7], [6, 7, 1]이며, 각 구간에서 하나씩 요소를 골랐

N개의 정수로 구성된 배열이 있다고 가정해 보겠습니다. 이 글에서는 주어진 배열 안의 중복 요소를 모두 찾아 출력하는 방법을 다룹니다. 만약 중복된 요소가 하나도 없다면 -1을 반환합니다. 예를 들어 배열이 [12, 15, 12, 3, 6, 12, 3, 48, 56, 8, 48]과 같다면, 중복 요소는 [12, 3, 48]입니다.접근 방법이 문제는 C++의 unordered_map(해시 맵)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.먼저 배열의 모든 요소를 순회하면서 각 값의 등장 횟수를 unord

문제 개요n개의 요소로 이루어진 배열이 있다고 가정해 보겠습니다. 배열의 모든 요소를 특정 값 x로 통일했을 때(arr[i] = x), 새 배열 전체의 곱이 원래 배열 전체의 곱보다 엄격하게 커지도록 만드는 최솟값 x를 구하는 것이 목표입니다.제약 조건은 다음과 같습니다.1 ≤ n ≤ 10^51 ≤ arr[i] ≤ 10^10예를 들어 배열이 [4, 2, 1, 10, 6]이라면 정답은 4입니다. 4 × 4 × 4 × 4 × 4 = 1024로, 원래 곱인 4 × 2 × 1 × 10 × 6 = 480보다 크기 때문입니다. 반면 3으로 채

0부터 n-1까지의 숫자로 이루어진 배열이 있다고 가정해 봅시다. 이때 어떤 숫자는 여러 번 중복해서 나타날 수 있으며, 우리는 추가 메모리 공간을 전혀 사용하지 않고 이러한 중복된 숫자들을 찾아야 합니다.예를 들어 n = 7이고 배열이 [5, 2, 3, 5, 1, 6, 2, 3, 4, 5]와 같다면, 중복된 값은 5, 2, 3입니다.알고리즘 접근 방식이 문제는 배열 원소의 부호(sign)를 활용하는 영리한 기법으로 해결할 수 있습니다. 모든 값이 0부터 n-1 범위 안에 존재하므로 각 값 자체가 유효한 인덱스 역할을 하며, 해당

두 개의 배열 A와 B가 있다고 가정해 보겠습니다. 배열 A는 n개의 요소를 가지고 있으며, 두 번째 배열 B는 A의 모든 요소를 포함하지만 순서가 섞여(shuffled) 있고 그중 하나의 요소가 제거되어 있습니다. 우리의 목표는 이 누락된 요소를 찾아내는 것입니다.예를 들어 A = [4, 8, 1, 3, 7]이고 B = [7, 4, 3, 1]이라면, B에는 없는 요소인 8이 출력되어야 합니다.XOR 연산을 활용한 해결 원리이 문제는 XOR(배타적 논리합) 트릭을 사용하면 매우 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과

문제 개요N개의 양의 정수로 이루어진 배열과 변수 K가 주어져 있다고 가정해 보겠습니다. 이때 임의의 두 원소의 차이가 k로 나누어떨어지는 정확히 m개의 원소로 구성된 집합을 찾아야 합니다.예를 들어 배열이 A = [4, 7, 10, 6, 9]이고 k = 3, m = 3이라면 출력은 yes입니다. 4, 7, 10처럼 서로 간의 차이(3, 3, 6)가 모두 3으로 나누어떨어지는 세 원소를 찾을 수 있기 때문입니다.접근 방법: 나머지(Remainder) 활용이 문제를 효율적으로 해결하려면 각 원소를 k로 나눈 나머지를 추적해야 합니다.

2차원 평면 위의 한 점 P와 직선의 방정식이 주어졌을 때, 점 P에서 그 직선으로 내린 수선의 발(foot of perpendicular)의 좌표를 구하는 것이 이 글의 목표입니다. 기하학적 개념을 간단한 대수 공식으로 바꾸면 코드 몇 줄만으로도 손쉽게 해를 구할 수 있습니다. 수학적 접근 방법 주어진 직선의 방정식은 다음과 같습니다. ax + by + c = 0 점 P(x1, y1)를 지나면서 위 직선에 수직인 직선은 다음 형태의 방정식을 갖습니다. ay − bx + d = 0 이 수직선이 원래의 직선과 만나는 점을 Q(x2

이진 문자열 bin이 주어졌을 때, 여기에 n번의 반복(변환)을 적용한다고 가정해 보겠습니다. 각 반복 단계에서 0은 01로, 1은 10으로 변환됩니다. 우리의 목표는 n번 반복을 모두 거친 최종 문자열에서 i번째 인덱스의 문자를 찾아내는 것입니다.예를 들어 이진 문자열이 101이고 n = 2, i = 3이라고 가정해 보겠습니다. 첫 번째 반복 후에는 100110이 되고, 두 번째 반복 후에는 100101101001이 됩니다. 따라서 인덱스 3에 해당하는 문자는 1입니다.문제 해결 접근 방법이 문제는 다음 단계에 따라 해결할 수 있

문제 개요양수 k가 주어졌을 때, n과 n+1의 XOR 연산 결과가 k와 정확히 일치하는 양수 n을 찾는 것이 목표입니다.예를 들어 k = 7(이진수 111)이라면, 정답은 3입니다. 3은 이진수로 011이고, 3 + 1 = 4는 이진수로 100이므로 다음과 같이 계산됩니다.011 XOR 100 = 111 (십진수 7)해결 접근 방법이 문제는 두 가지 경우로 나누어 분석할 수 있습니다.경우 1: n이 짝수일 때짝수 n의 마지막 비트는 0이고, n+1의 마지막 비트는 1입니다. 나머지 상위 비트들은 모두 동일하므로, XOR 연산 결과

괄호가 포함된 표현식이 있을 때, 특정 여는 괄호의 인덱스가 주어지면 그 괄호에 대응하는 닫는 괄호의 위치를 찾아야 하는 경우가 있습니다. 예를 들어 표현식이 (25*6+(88-32+(50/10)+20))이고 여는 괄호의 인덱스가 6이라면, 그에 대응하는 닫는 괄호는 인덱스 23에 위치합니다.해결 접근 방법: 스택 활용이 문제는 스택(Stack) 자료구조를 사용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.주어진 인덱스부터 표현식을 순회하며 시작합니다.여는 괄호 (를 만나면 스택에 push 합니다.닫는

숫자 n이 주어졌을 때, 짝수 인덱스에 위치한 이항 계수들의 합을 구하는 문제를 살펴보겠습니다. 즉, 다음과 같은 형태의 값을 계산해야 합니다.$$\left(\begin{array}{c}n\\ 0\end{array}\right)+\left(\begin{array}{c}n\\ 2\end{array}\right)+\left(\begin{array}{c}n\\ 4\end{array}\right)+\left(\begin{array}{c}n\\ 6\end{array}\right)+...$$예를 들어 n = 4인 경우는 다음과 같습니다.$$\

초기값이 0인 이진 문자열이 있다고 가정해 보겠습니다. 매 반복(iteration)마다 현재 문자열을 반전시킨 후(0은 1로, 1은 0으로 변경), 그 결과를 기존 문자열 뒤에 덧붙입니다. 이 과정을 n번 수행한 뒤, 완성된 문자열에서 k번째 비트를 찾는 것이 이 문제의 목표입니다.예를 들어 반복 횟수가 4이고 k = 7이라면, 문자열은 아래 표와 같이 변화합니다.반복 횟수문자열 값 (초기값: 0)1012011030110100140110100110010110따라서 7번째 비트는 1입니다.접근 방법핵심 아이디어는 간단합니다. 각 반복

배열 A에 여러 개의 요소가 저장되어 있다고 가정해 보겠습니다. 우리가 구해야 할 것은 배열에 존재하는 모든 고유한(distinct) 요소들의 합입니다. 예를 들어 A = [5, 12, 63, 5, 33, 47, 12, 63]이라면, 고유한 요소들의 합은 160이 됩니다. 중복된 값은 한 번이라도 계산에 포함되었다면 이후에는 완전히 무시됩니다.접근 방법: unordered_set 활용이 문제는 unordered_set(정렬되지 않은 집합)을 사용하면 매우 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.배열을 단 한

어떤 자연수 n이 주어졌을 때, 1/n을 소수로 전개했을 때 반복되는 숫자 열(순환 마디)의 길이를 구하는 것이 이 문제의 목표입니다. 예를 들어 n = 7이라면 1/7 = 0.142857142857… 이 되며, 굵게 표시된 부분이 무한히 반복됩니다. 따라서 이 경우 마침표의 길이는 6입니다.접근 방법n으로 나누는 과정에서 나올 수 있는 서로 다른 나머지는 최대 n가지입니다. 하지만 순환이 반드시 첫 번째 나머지부터 시작하는 것은 아니며, 초반의 일부 나머지는 반복되지 않는 비순환 구간에 속할 수 있습니다.따라서 순환 구간에 속한

문제 개요크기가 n인 배열이 주어졌을 때, 배열의 모든 요소를 동일한 값으로 만든 후 얻을 수 있는 최대 합을 구하는 것이 목표입니다. 단, 허용되는 연산은 하나뿐입니다. 임의의 두 요소를 선택하고, 그중 더 큰 값을 두 수의 절대 차(차이)로 대체하는 것입니다.예를 들어 배열이 [9, 12, 3, 6]이라면 결과는 12가 됩니다. 과정을 단계별로 살펴보겠습니다.A[1]을 A[1] – A[3] = 12 – 6 = 6으로 교체 → [9, 6, 3, 6]A[3]을 A[3] – A[2] = 6 &