문제 개념주어진 N개의 숫자에 대해, 남은 숫자들의 GCD(최대공약수)가 처음 N개 숫자의 GCD보다 커지도록 만들기 위해 제거해야 하는 원소의 최소 개수를 구하는 것이 목표입니다. 만약 GCD를 증가시키는 것이 불가능하다면 NO를 출력합니다.입력 예시 1b[] = {1, 2, 4}출력1첫 번째 원소인 1을 제거하면 새로운 GCD는 2가 되며, 이는 초기 GCD인 1보다 큽니다.입력 예시 2b[] = {6, 9, 15, 30}출력2초기 GCD는 3입니다. 6과 9를 제거하면 남은 {15, 30}의 GCD는 15가 되어 3보다 커집니

문제 개요n개의 양의 정수로 구성된 배열 arr[]가 주어졌을 때, 조합 값 arr[i]Carr[j]가 가능한 한 최대가 되도록 만드는 두 원소 arr[i]와 arr[j]를 찾는 것이 목표입니다. 조건을 만족하는 쌍이 여러 개 존재하는 경우에는 그중 하나만 출력하면 됩니다.입력 예시:arr[] = {4, 1, 2}출력 예시:4 2배열에서 만들 수 있는 조합 값을 하나씩 살펴보면 다음과 같습니다.4C1 = 4 → 쌍 (4, 1)4C2 = 6 → 쌍 (4, 2)2C1 = 2 → 쌍 (1, 2)세 경우를 비교했을 때 4C2가 가장 크므로

핵심 개념이 글에서는 루트가 있는 트리에서 두 노드의 LCA(Lowest Common Ancestor, 최소 공통 조상)를 찾는 문제를 RMQ(Range Minimum Query, 구간 최솟값 쿼리) 문제로 변환하여 해결하는 방법을 소개합니다.LCA란?루트가 있는 트리 T에서 두 노드 a와 b의 최소 공통 조상(LCA)은 a와 b를 모두 자손으로 가지면서 루트로부터 가장 멀리 떨어진 노드를 의미합니다.예를 들어 아래 그림에서 노드 D와 노드 I의 LCA는 노드 B입니다.LCA 문제를 해결하는 방법은 매우 다양하며, 각 방식은 시간

개념이 글에서는 주어진 이진 트리(Binary Tree) 안에서 가장 큰 완전 이진 서브트리(Complete Binary Sub-tree)의 크기를 찾는 방법을 다룹니다.완전 이진 트리(Complete Binary Tree)란? 모든 레벨이 완전히 채워져 있고 마지막 레벨만 비어 있을 수 있으며, 마지막 레벨의 노드들은 최대한 왼쪽에 몰려 있는 이진 트리를 말합니다. 모든 포화 이진 트리(Perfect Binary Tree)는 반드시 완전 이진 트리이지만, 그 역은 성립하지 않습니다. 또한 어떤 트리가 완전 이진 트리가 아니라면 포

개념주어진 숫자 N이 있을 때, 우리의 목표는 N에서 최소한의 자릿수(0개일 수도 있음)를 삭제하여 만들 수 있는 가장 큰 완전세제곱수(perfect cube)를 찾는 것입니다. 주어진 숫자의 어떤 자릿수든 삭제하여 목표 값을 만들 수 있습니다.어떤 수 A가 임의의 정수 B에 대해 A = B³ 관계를 만족한다면, A를 완전세제곱수라고 부릅니다.만약 아무리 자릿수를 삭제해도 완전세제곱수를 만들 수 없다면 -1을 출력해야 합니다.예시N = 1025인 경우: 숫자에서 0을 삭제하면 125가 남습니다. 125 = 5 × 5 × 5이므로,

개념(, ), {, }, [, ] 여섯 가지 문자로 이루어진 문자열 str이 주어졌을 때, 이 문자열의 괄호가 균형 잡혀 있는지(balanced) 판별하는 것이 목표입니다.괄호가 균형 잡혀 있다고 판단되는 조건은 다음과 같습니다.열린 괄호는 반드시 같은 종류의 괄호로 닫혀야 합니다.열린 괄호는 올바른 순서에 따라 닫혀야 합니다.입력 − str = (()){}출력 − Yes입력 − str = ))(([][출력 − No풀이 방법비교 대상이 되는 두 괄호의 위치를 추적하기 위해 두 개의 변수 a와 b를 사용합니다.여는 괄호를 만나면 값이

개념레드-블랙 트리(Red-Black Tree)에서 특정 노드의 최대 높이는 최소 높이의 최대 2배를 넘지 않습니다. 따라서 주어진 이진 탐색 트리(Binary Search Tree)가 이 성질을 만족하는지 검증해야 합니다.즉, 모든 노드에 대해 리프 노드에서 해당 노드까지의 가장 긴 경로의 길이가, 노드에서 리프까지의 가장 짧은 경로에 포함된 노드 수의 2배를 초과하지 않아야 합니다.예시13 41 \ / \ 15 11 101 \ / \ 17 61 151위 트리는 노드 13의 최대 높이가 1,

개념주어진 이진 트리가 힙(heap) 속성을 만족하는지 검증해야 하는 경우가 있습니다. 이진 트리가 힙이 되기 위해서는 다음 두 가지 조건을 모두 충족해야 합니다.이진 트리는 완전 이진 트리(complete tree)여야 합니다. 즉, 마지막 레벨을 제외한 모든 레벨이 꽉 차 있어야 합니다.최대 힙(max-heap)을 기준으로 할 때, 트리의 모든 노드 값은 자식 노드의 값보다 크거나 같아야 합니다.예시다음 트리는 힙 속성을 만족하는 예입니다.반면 아래 트리는 힙 속성을 만족하지 않습니다.접근 방법위 두 조건은 각각 독립적으로 검증

연결된 그래프가 주어졌을 때, 해당 그래프가 이분 그래프(Bipartite Graph)인지 확인하는 문제를 살펴보겠습니다. 이분 그래프란 그래프의 모든 정점을 두 가지 색으로 칠할 때, 인접한 정점끼리는 서로 다른 색을 갖도록 칠하는 것이 가능한 그래프를 의미합니다. 즉, 같은 색의 정점들이 하나의 집합을 이루도록 나눌 수 있는 그래프입니다.문제 예시예를 들어 다음과 같은 그래프가 입력으로 주어진다고 가정해 보겠습니다.이 경우 출력 결과는 True(1)가 됩니다.접근 방법: DFS 기반 2-색칠하기이 문제는 깊이 우선 탐색(DFS)

문제 개념주어진 문자열이 유효한 숫자(numeric)인지 판별하는 프로그램을 작성해야 합니다. 단순히 숫자 형태처럼 보이는지만 확인하는 것이 아니라, 소수점과 지수 표기까지 포함해 엄격하게 검증해야 합니다.입력 − str = 12.5출력 − true입력 − str = def출력 − false입력 − str = 2e5출력 − true입력 − str = 10e4.4출력 − false접근 방법문자열이 유효한 숫자인지 확인하려면 코드에서 다음과 같은 경우들을 반드시 처리해야 합니다.문자열 앞뒤에 있는 선행·후행 공백은 무시합니다.문자열 시

개념크기가 N인 배열 arr1[]과 키 값 X, 그리고 세그먼트 크기 K가 주어졌을 때, 키 X가 배열 내 크기 K를 가진 모든 세그먼트에 존재하는지 판별하는 것이 이 문제의 목표입니다.입력 예제 1arr1[] = { 4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4 }X = 4K = 3출력Yes위 배열에는 크기 K(=3)인 겹치지 않는 세그먼트가 총 4개 존재합니다: {4, 6, 3}, {5, 10, 4}, {2, 8, 4}, {12, 13, 4}. 네 개의 세그먼트 모두에 4가 포함되어 있으므로 결과는 Yes입

무한히 넓은 체스판 위에서 일반 체스와 동일한 규칙이 적용된다고 가정해 봅시다. 이때 체스판 위에 배치된 N개의 나이트 좌표(-10^9 ≤ x, y ≤ 10^9)와 킹의 좌표가 주어졌을 때, 킹이 더 이상 유효한 이동을 할 수 없는 상태, 즉 체크메이트인지 확인하는 것이 이 문제의 목표입니다. 입력 및 출력 예시 입력 1 a1[] = { { 2, 1 }, { 1, 3 }, { 3, 6 }, { 5, 5 }, { 6, 1 }, { 7, 3 } }, king -> {4, 3} 출력 1 Yes 킹이 체크메이트 상태이기 때문에 어떤

문제 개요2차원 좌표 평면 위에 n개의 서로 다른 점 (Xi, Yi)이 주어져 있고, 각 점에는 가중치 Wi가 부여되어 있습니다. 이때 기울기가 45도인 직선을 하나 그어서, 직선 양쪽에 위치한 점들의 가중치 합이 서로 같아지도록 만들 수 있는지 확인해야 합니다.예를 들어 입력이 [[-1,1,3], [-2,1,1], [1,-1,4]]라면 출력은 True입니다.핵심 아이디어기울기가 45도인 모든 직선은 x − y = c 꼴의 방정식으로 표현할 수 있습니다. 상수 c의 값을 조정하면 직선을 대각선 방향으로 평행 이동시킬 수 있습니다.

개념주어진 수 n이 트로이 수(Trojan Number)인지 판별하는 것이 이 글의 목표입니다. 트로이 수란 완전 거듭제곱(perfect power)이 아닌 강한 수(strong number)를 의미합니다.여기서 강한 수란, 수 n의 모든 소인수 p에 대해 p² 역시 n의 약수가 되는 수를 말합니다. 다르게 표현하면, 모든 소인수가 적어도 두 번 이상 나타나야 한다는 뜻입니다.주의할 점은 모든 트로이 수는 반드시 강한 수이지만, 그 역은 성립하지 않는다는 것입니다. 즉, 모든 강한 수가 트로이 수인 것은 아니며, ab(a와 b는 1

아킬레스 수란?주어진 양의 정수 n이 아킬레스 수인지 판별하는 것이 이 글의 목표입니다. n이 아킬레스 수라면 YES를, 그렇지 않다면 NO를 출력해야 합니다.아킬레스 수: 수학에서 아킬레스 수는 강수(powerful number)이면서 동시에 완전 거듭제곱수가 아닌 수로 정의됩니다. 여기서 강수란, 모든 소인수 p에 대해 p² 역시 그 수를 나누어 떨어지게 하는 수를 의미합니다.처음 등장하는 아킬레스 수들은 다음과 같습니다.72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 9

개념주어진 양의 정수 n이 프리모리얼 소수(Primorial Prime)인지 판별하는 것이 과제입니다. n이 프리모리얼 소수라면 YES를 출력하고, 그렇지 않다면 NO를 출력해야 합니다.프리모리얼 소수란? 수학에서 프리모리얼 소수는 pN# + 1 또는 pN# − 1 형태로 표현되는 소수를 의미합니다. 여기서 pN#은 프리모리얼(primorial)로, 처음 N개의 소수를 모두 곱한 값입니다.예시 입력과 출력입력: n = 7출력: YES7은 N=2일 때 pN + 1 형태의 프리모리얼 소수입니다. 프리모리얼 값은 2 × 3 = 6이며,

문제 이해주어진 그림의 여덟 개 빈 칸에 숫자 1, 2, 3, 4, 5, 6, 7, 8을 하나씩 배치하려고 합니다. 단, 수열에서 서로 이웃한 숫자(1과 2, 2와 3 등)가 그리드에서 인접한 칸에 놓여서는 안 됩니다. 인접 판단에는 상하좌우뿐 아니라 대각선 방향도 포함됩니다.예를 들어 입력이 다음과 같은 3×4 그리드라면, 값 0은 사용하지 않는 칸, -1(NOTCONSIDERED)은 아직 숫자가 채워지지 않은 칸을 의미합니다.0-1-10-1-1-1-10-1-10이때 출력 결과는 다음과 같습니다.해결 접근 방법이 문제는 전형적인

문제 설명N개의 정수로 이루어진 배열이 주어졌을 때, 각 요소의 합이 N으로 나누어 떨어지는 비어 있지 않은 부분 집합을 찾아야 합니다. 조건을 만족하는 부분 집합이 존재한다면, 해당 부분 집합의 크기와 함께 원본 배열에서의 인덱스를 출력해야 합니다.예를 들어 입력 배열이 [3, 2, 7, 1, 9]이고 N = 5라고 가정해 보겠습니다. 첫 번째와 두 번째 요소를 선택하면 3 + 2 = 5이므로 5로 나누어 떨어집니다. 따라서 출력은 다음과 같습니다.21 2해결 접근 방식이 문제는 접두사 합(prefix sum)과 나머지 연산을 활

개념음이 아닌 정수로 구성된 배열 Arr[]가 주어졌을 때, 다음 식의 합계를 최소로 만드는 정수 X를 찾는 것이 이 글의 목표입니다.(Arr[0] XOR X) + (Arr[1] XOR X) + … + (Arr[n-1] XOR X)입력 예시Arr[] = {3, 4, 5, 6, 7}출력 결과X = 7, Sum = 10접근 방법배열의 모든 수를 이진수로 표현했을 때 각 비트 자리 i를 하나씩 검사하고, 해당 비트가 1로 설정된(set) 수의 개수를 셉니다. 이미 설정된 비트가 많을수록 XOR 연산 결과가 커져 오히려 합계를 증가시키는

무방향 그래프(undirected graph)와 정점 집합이 하나 주어져 있다고 가정해 봅시다. 이때 우리가 해야 할 일은, 주어진 집합에 포함된 모든 정점으로부터 도달 가능한(reachable) 모든 노드를 찾아내는 것입니다.문제 예시예를 들어 입력이 아래 그림과 같은 그래프라고 해보겠습니다.이 경우 출력은 [1, 2, 3]과 [4, 5]가 됩니다. 이는 각각 하나의 연결 요소(connected component)를 나타내며, 같은 컴포넌트 안의 노드들끼리만 서로 도달할 수 있기 때문입니다.해결 접근 방법핵심 아이디어는 각 정점에