알파벳 m개와 정수 n이 주어졌다고 가정해 봅시다. 이때 m개의 알파벳으로 만들 수 있는 길이 n의 문자열 중, 길이가 1보다 큰 회문(palindrome) 부분 문자열을 하나도 포함하지 않는 문자열의 개수를 구하는 것이 문제입니다. 답이 너무 커질 경우 결과를 10^9+7로 나눈 나머지를 반환합니다.예를 들어 n = 2, m = 3이 입력으로 주어진다면 출력은 6이 됩니다. m = 3이므로 알파벳 집합이 {x, y, z}일 때 만들 수 있는 문자열은 [xx, xy, xz, yx, yy, yz, zx, zy, zz]입니다. 그런데

데카르트 좌표평면의 원점 (0, 0)에 있다고 가정해 보겠습니다. 우리는 단위 길이의 수평 이동(H)과 수직 이동(V)만을 사용하여 점 (x, y)로 이동하려고 합니다. 목적지에 도달할 수 있는 경로는 여러 가지가 있으며, 각 경로는 여러 번의 H 이동과 V 이동의 순서로 구성됩니다. 예를 들어, (0, 0)에서 (2, 2)로 이동할 때 HVVH는 가능한 경로 중 하나입니다. 여기에 값 k가 추가로 주어진다면, 사전순(lexicographic order)으로 k번째로 작은 이동 경로를 찾아야 합니다. 예를 들어 입력이 (x, y)

N개의 계단으로 이루어진 계단이 있다고 가정해 보겠습니다. 한 번에 한 계단씩 천천히 오를 수도 있고, 각 차례마다 최대 N계단까지 한 번에 뛰어넘을 수도 있습니다. 이때 구해야 하는 것은 꼭대기 층까지 도달할 수 있는 방법의 총 개수입니다. 문제는 N 값이 매우 커질 수 있다는 점인데, 그래서 우리는 방법의 수 전체가 아니라 첫 K자리와 마지막 K자리에만 관심을 둡니다. 문제 이해하기 입력이 N = 10, k = 2라고 해보겠습니다. 이때 출력은 63입니다. 계단이 10개일 때 꼭대기까지 올라가는 방법의 수를 S라고 하면, S를

n개의 A와 2n개의 B로 이루어진 문자열이 있다고 가정해 보겠습니다. 이때 문자열의 모든 접두사(prefix)와 모든 접미사(suffix)에서 B의 개수가 A의 개수보다 크거나 같도록 배열할 수 있는 경우의 수를 구하는 것이 이 글의 목표입니다.예를 들어 n = 2라고 입력하면 A가 2개, B가 4개 존재합니다. 조건을 만족하는 가능한 배치는 [BBAABB, BABABB, BBABAB, BABBAB]로 총 4가지이므로, 출력 결과는 4가 됩니다.문제 해결 접근 방법이 문제는 재귀(recursion)를 활용해 다음과 같은 단계로 해

1부터 n까지의 모든 원소를 포함하는 집합 A가 있다고 가정해 보겠습니다. P(A)는 집합 A의 원소들로 만들 수 있는 모든 순열(permutation)의 집합을 의미합니다. 이번 문제의 목표는 P(A)에 속한 순열 중에서 주어진 조건들을 만족하는 것의 개수를 구하는 것입니다. 문제의 조건 P(A)의 순열은 다음 두 가지 조건을 만족해야 합니다. 조건 1: 범위 [1, n]의 모든 i에 대해 A[i] ≠ i 입니다. 즉, 어떤 원소도 자기 자신의 위치에 있으면 안 됩니다(완전 순열, derangement). 조건 2: k개의 인

문제 이해하기노드가 n개인 무방향 그래프 G가 있다고 가정해 보겠습니다. 단순 무방향 그래프의 비용(cost)은 그래프를 구성하는 모든 노드의 비용 합계로 정의되며, 각 노드의 비용은 Dk입니다. 여기서 D는 해당 노드의 차수(degree)이고, k는 주어진 지수입니다.n과 k 값이 주어졌을 때, 노드가 n개인 모든 가능한 단순 무방향 그래프의 비용 총합을 구해야 합니다. 결과값이 매우 커질 수 있으므로 1005060097로 나눈 나머지를 반환합니다.예제입력이 n = 3, k = 2라고 해봅시다. 노드가 3개인 단순 그래프는 총 8

1부터 n까지의 수직선이 있다고 가정해 보겠습니다. 처음에는 위치 0에서 출발해 한 칸 점프하여 위치 1로 이동하고, 다음에는 두 칸 점프하여 위치 3에 도달한 뒤, 세 칸 점프하여 위치 6에 도달하는 식으로 진행합니다. 이처럼 점프 거리를 매번 1씩 늘려갈 때, 정확히 위치 n에 도달할 수 있는지 확인하는 것이 이 문제의 목표입니다.예를 들어 입력이 n = 21이라면 출력은 True가 됩니다. 1 + 2 + 3 + 4 + 5 + 6 = 21이므로, 여섯 번의 점프만으로 정확히 위치 21에 도달할 수 있기 때문입니다.문제의 핵심:

문제 개요 리스트 A가 주어져 있다고 가정해 보겠습니다. n개의 원소를 가진 리스트는 (2n − 1)개의 공집합이 아닌 부분 리스트를 가질 수 있습니다. 각 부분 리스트에 대해 원소들의 합인 sublist_sum을 계산하고, 이를 S1, S2, S3, ..., S(2N−1)로 표기합니다. 이때 다음과 같은 특별한 합 P를 정의합니다. P = 2S1 + 2S2 + 2S3 + ... + 2S(2N−1) 목표는 이 P를 구하는 것이며, P가 너무 커질 경우에는 P mod (109 + 7)을 반환하면 됩니다. 예시 입력이 A = [2, 2

숫자 삼각형이란? 아래와 같은 형태의 숫자 삼각형을 생성한다고 가정해 보겠습니다. 1 1 1 1 1 2 3 2 1 1 3 6 7 6 3 1 이 삼각형에서 각 행의 원소는 바로 위에 있는 세 개의 숫자를 더해 만들어집니다. 이제 줄 번호 l이 주어졌을 때, 해당 줄에서 첫 번째 짝수가 등장하는 위치를 구하는 것이 목표입니다. 단, 위치 값은 1부터 시작합니다. 문제 예시 예를 들어 입력이 l = 5라면 출력은 2가 됩니다. 1 1 1 1 1 2 3 2 1 1 3

문제 설명 값 n이 하나 주어졌을 때, 수열 S의 마지막 자릿수를 구해야 합니다. 수열 S는 다음 식으로 정의됩니다. $$\sum_{i=0,\: 2^{i}\leqslant n}^{\alpha } \sum_{j=0}^{n} 2^{2^{i}+2j}$$ 예를 들어 입력이 n = 2라고 가정해 보겠습니다. 조건 2i ≤ n을 만족하는 유효한 i 값은 0과 1뿐이므로, 각 항은 다음과 같이 계산됩니다. S0 = 2^(2⁰+0) + 2^(2⁰+2) + 2^(2⁰+4) = 2 + 8 + 32 = 42 S1 = 2^(2¹+0) + 2^(2¹+2

문제 개요네 개의 숫자 a, b, c, d가 주어졌을 때, 다음 방정식을 만족하는 정수 쌍 (x, y)의 개수를 구하는 프로그램을 작성해야 합니다.x² + y² = a·x + b·y단, x는 [1, c] 범위, y는 [1, d] 범위 안에 있어야 합니다.예를 들어 입력이 a = 2, b = 3, c = 2, d = 4라면 출력은 1이 됩니다. 조건을 만족하는 유일한 쌍이 (1, 1)이기 때문입니다.접근 방법모든 (x, y) 조합을 완전 탐색하는 대신, 주어진 x마다 y에 대한 이차방정식을 풀어 유효한 해의 개수를 세는 방식이 훨씬

문제 개요빠르게 증식하는 위험한 바이러스가 있다고 가정해 봅시다. 매 시간마다 바이러스 세포 수가 x배 증가할 확률은 0.5이고, y배 증가할 확률 역시 0.5입니다. 처음에 바이러스가 단 하나의 세포로 시작했다면, t시간 후의 기대 바이러스 세포 수를 계산해야 합니다. 만약 결과값이 너무 커진다면 10^9+7로 나눈 나머지를 구하면 됩니다.예를 들어 입력이 x = 2, y = 4, t = 1이라면 출력은 3이 됩니다. 초기에는 바이러스가 한 개의 세포만 가지고 있으며, 0.5의 확률로 크기가 2배(x2)가 되고, 나머지 0.5의

문제 개요요소들로 이루어진 배열 nums가 주어졌을 때, 이를 비내림차순으로 정렬하는 문제를 생각해 보겠습니다. 다만 여기서 사용하는 정렬 방식은 무작위(randomized) 기법입니다. 배열이 이미 정렬되어 있는지 검사하고, 정렬되어 있지 않다면 요소들을 무작위로 섞은(shuffle) 뒤 다시 검사합니다. 이 과정을 배열 전체가 정렬될 때까지 반복하며, 우리가 구해야 할 것은 정렬이 완성될 때까지 필요한 셔플 횟수의 기댓값입니다. 결과는 소수점 여섯째 자리까지 반올림하여 출력합니다.접근 방식핵심 아이디어는 간단합니다. 서로 다른

문제 소개n개의 행(row)과 m개의 열(column)로 이루어진 격자(grid)가 있다고 가정해 봅시다. 아말(Amal)과 비말(Bimal)은 이 격자 위에서 다음과 같은 규칙으로 게임을 진행합니다.게임 규칙아말은 맨 윗줄의 아무 곳에나 흰색 연꽃(lotus) 타일을 놓고, 비말은 맨 아랫줄의 아무 곳에나 애벌레(caterpillar) 타일을 놓습니다. 아말이 선공이며, 두 플레이어는 번갈아 가며 자신의 타일을 움직입니다.아말(연꽃): 현재 칸을 기준으로 격자 내부에 있는 인접한 8개 칸 중 어느 곳으로든 이동할 수 있습니다.비말

정다각형의 꼭짓점 색상을 나타내는 배열 colors가 있다고 가정해 보겠습니다. 이 n각형의 각 꼭짓점은 주어진 배열에 포함된 서로 다른 n가지 색상 중 하나로 무작위로 칠해져 있습니다. 우리는 다음 조건을 모두 만족하는 특수한 꼭짓점 부분 집합의 개수를 구해야 합니다.부분 집합의 크기는 최소 2 이상이어야 합니다.부분 집합에 속한 꼭짓점들을 다각형에서 제거하면(해당 꼭짓점들의 인접 변 역시 함께 제거됨), 남은 꼭짓점과 변들이 하나 이상의 연속적인 경로를 형성합니다.그 경로들 중 어느 곳에도 같은 색상의 꼭짓점이 두 개 이상 존재

문제 개요 배열 nums와 한 쌍의 값 (x, y)가 주어졌을 때, 재귀적으로 정의된 find(x, y)의 값이 짝수인지 홀수인지 판별하는 문제입니다. find() 함수는 다음과 같이 정의됩니다. x > y이면 find(x, y) = 1 그 외의 경우에는 find(x, y) = nums[x] ^ find(x + 1, y) 예제로 이해하기 입력이 nums = [3, 2, 7]이고 (x, y) = (1, 2)라고 가정해 보겠습니다. 이 경우 출력은 짝수(Even)입니다. 그 과정은 다음과 같습니다. find(1, 2) =

숫자 n이 주어졌을 때, n의 진약수(proper divisor) 중 하나를 골랐을 때 그 수가 짝수이면서 동시에 완전제곱수일 확률을 구하는 문제입니다. 예를 들어 n = 36이라면 답은 1/8입니다. 36의 진약수는 {1, 2, 3, 4, 6, 9, 12, 18}로 총 8개이고, 이 가운데 짝수이면서 완전제곱수인 수는 4 하나뿐이기 때문입니다. 접근 방법 이 문제의 핵심 아이디어는 다음과 같습니다. 모든 짝수 완전제곱수는 반드시 4의 배수입니다. 따라서 n이 4로 나누어떨어지지 않으면 n의 어떤 약수도 조건을 만족할 수 없으므

문제 개요 두 개의 큰 정수 값 최댓값(maximum)과 최솟값(minimum)이 주어져 있다고 가정해 봅시다. 우리가 찾아야 하는 것은 다음 조건을 모두 만족하는 분수 n/d입니다. 분모 d가 min ≤ d ≤ max 범위 안에 있어야 합니다. |n/d − π|의 값이 최소가 되어야 합니다. (여기서 π = 3.14159265...) 조건을 만족하는 분수가 여러 개라면, 그중 분모가 가장 작은 분수를 반환해야 합니다. 예를 들어 minimum = 1, maximum = 10이 주어지면 결과는 22/7이 됩니다. 해결 접근 방

숫자 n과 값 k가 주어졌을 때, 1부터 N까지의 자연수로 이루어진 배열 A에서 i < j를 만족하는 두 원소 A[i]와 A[j]의 합이 k로 나누어 떨어지는 쌍의 총 개수를 구하는 문제를 생각해 봅시다.예를 들어, n = 10, k = 4가 입력으로 주어지면 출력은 10이 됩니다. 합이 4로 나누어 떨어지는 쌍이 정확히 10개 존재하기 때문입니다.해당 쌍들은 다음과 같습니다: (1,3), (1,7), (2,6), (2,10), (3,5), (3,9), (4,8), (5,7), (6,10), (7,9)해결 접근 방법이 문제를

두 개의 수 n과 m이 주어졌을 때, 1이 n개 이어진 수(예: n=4라면 1111)를 m으로 나눈 나머지를 구하는 것이 목표입니다.예를 들어 n = 4, m = 27이 입력으로 주어지면 출력은 4가 됩니다. 왜냐하면 1111 mod 27 = 4이기 때문입니다.문제 해결 접근 방법n이 매우 커질 경우, 실제로 1을 n개 이어 붙인 수를 만드는 것은 비효율적이거나 불가능할 수 있습니다. 따라서 다음과 같은 수학적 성질을 활용합니다.1이 n개 이어진 수(레퓨닛, Repunit)는 다음과 같이 표현할 수 있습니다.R(n) = (10^n