두 개의 점 (p1, q1)과 (p2, q2)가 주어졌다고 가정해 봅시다. 이 두 점을 지나는 직선을 그렸을 때, 그 직선 위에 존재하는 정수 좌표(x 값과 y 값이 모두 정수인 점)의 개수를 구하는 것이 목표입니다.예를 들어 입력이 p1 = 3, q1 = 3, p2 = 6, q2 = 6이라면 출력은 2가 됩니다. 두 점을 잇는 직선을 그려 보면 (5, 5)와 (6, 6)이라는 점이 직선 위에 위치하는 것을 확인할 수 있습니다.문제 해결 접근 방법이 문제는 최대공약수(GCD)를 활용하면 아주 간단하게 해결할 수 있습니다. 두 점의

네 개의 정수 p, q, r, k가 주어졌을 때, 러시아 농민 곱셈(Russian Peasant Multiplication) 기법을 활용하여 복소수 거듭제곱 (p + qi)r = r + si를 계산하고, 그 결과인 r mod k와 s mod k를 구하는 프로그램을 만들어 보겠습니다.예를 들어 입력값이 p = 3, q = 0, r = 8, k = 10000이라면 출력은 (6561, 0)이 됩니다. 38 = 6561이고, q = 0이므로 허수 부분이 0이기 때문입니다.해결 접근 방법이 문제는 거듭제곱을 반복적으로 제곱 형태로 분해하여

문제 소개길 위에 일렬로 놓인 블록이 있고, 한 작업자가 이 블록들에 색타일을 붙이고 있다고 가정해 보겠습니다. 작업자는 블록 번호가 4 또는 2로 나누어떨어지면서 42로는 나누어떨어지지 않는 경우에만 그 블록에 색타일을 붙입니다. 이때 작업자가 k개의 색타일을 가지고 시작한다면, 최대 몇 번째 블록까지 덮을 수 있는지 구하는 것이 이 프로그램의 목표입니다.예를 들어 입력이 k = 16이라면 출력은 32가 됩니다. 2, 4, 6, ..., 32처럼 짝수 번호의 블록에 차례대로 타일을 붙였을 때, 16번째 타일이 32번 블록에 놓이기

문제 소개모든 값이 0으로 초기화된 n × m 크기의 행렬이 있다고 가정해 보겠습니다. 그리고 특정 행 위치와 열 위치를 담고 있는 쌍(pair)들의 목록이 주어집니다. 목록의 각 항목 i에 대해, 행 번호가 해당 항목의 행 값보다 작고, 열 번호가 해당 항목의 열 값보다 작은 모든 셀의 값이 1씩 증가합니다.목록의 모든 요소를 순회한 후에는, 행렬에서 최댓값을 포함하는 셀이 몇 개인지 구해야 합니다. (행과 열 인덱스는 0부터 시작합니다.)예를 들어 입력이 input_list = [[3, 5], [4, 6], [5, 3]]이라면

정점이 n개인 다각형이 있다고 가정해 보겠습니다. 이 다각형에는 n개의 뒤집기 축(flipping axis)과 n개의 회전점이 존재하며, 뒤집기 축과 회전점은 다음과 같은 성질을 가집니다. n이 홀수라면, 각 뒤집기 축은 하나의 정점과 반대편 변의 중점을 지난합니다. n이 짝수라면, 절반의 축은 마주 보는 한 쌍의 정점을 지나고, 나머지 절반의 축은 마주 보는 한 쌍의 변을 지난합니다. 인접한 두 축 사이의 각도는 360/2n도입니다. 이제 주어진 다각형에 회전 연산을 적용해 보겠습니다. 다각형에는 서로 다른 n가지 종류의 회전

n개의 공이 있다고 가정해 보겠습니다. 공들은 처음에 1, 2, 3, 4, ..., n 순서대로 정렬되어 있습니다. 먼저 전체 공의 순서를 역순으로 뒤집으면 n, n-1, n-2, ..., 2, 1이 됩니다. 그다음 다시 뒤집기를 수행하는데, 이번에는 1번 위치부터 n번 위치까지만 뒤집으므로 순서는 n, 1, 2, ..., n-1처럼 바뀝니다. 이러한 뒤집기 과정을 총 n번 반복하되, 매번 뒤집기 시작 위치를 오른쪽으로 한 칸씩 이동시킵니다. 우리의 목표는 모든 뒤집기가 끝난 뒤, 처음에 index 위치에 있던 공이 최종적으로 어

문제 소개하나의 숫자 n이 주어졌다고 가정해 봅시다. [1, 2, ..., n]과 같이 연속된 값들이 있을 때, 이 n개의 서로 다른 값을 노드로 사용하여 만들 수 있는 BST(이진 탐색 트리)의 총 개수를 구해야 합니다. 단, 결과값이 너무 커질 수 있으므로 109+7로 나눈 나머지를 반환합니다.예를 들어 입력이 n = 3이라면 출력은 14가 됩니다.접근 방법이 문제는 카탈란 수(Catalan Number) 계산과 유사한 동적 계획법(Dynamic Programming)으로 해결할 수 있습니다. 작은 부분 문제의 결과를 누적해가며

문제 개요 함수 f(x)가 있다고 가정해 보겠습니다. 이 함수는 아래 조건을 모두 만족하는 (p, q) 쌍의 개수를 세는 역할을 합니다. 1 < p <= q <= x p와 q는 서로소 (최대공약수가 1) p × q = x 하나의 숫자 n이 주어지면, 1부터 n까지의 모든 x에 대해 f(x) 값의 합을 구해야 합니다. 예를 들어 입력이 12라면 결과는 3이 됩니다. x의 범위가 1부터 12까지이기 때문인데, 실제로 유효한 쌍이 만들어지는 경우는 다음과 같습니다. x = 6일 때: 유효한 쌍은 (2, 3) → f(

문제 설명 두 개의 숫자 n과 k가 주어졌을 때, n이 정확히 k개의 소수(素數)의 합으로 표현될 수 있는지 판별하는 프로그램을 만들어 보겠습니다. 예를 들어 입력이 n = 30, k = 3이라면 결과는 True입니다. 30을 2 + 11 + 17처럼 세 개의 소수의 합으로 나타낼 수 있기 때문입니다. 해결 전략 이 문제는 경우를 나누어 다음과 같이 접근할 수 있습니다. n < 2k인 경우: 소수 중 가장 작은 값은 2이므로, k개의 소수의 합은 최소 2k입니다. 따라서 n이 2k보다 작으면 표현이 불가능하며 False를

문제 이해하기Ajob 언어라는 아주 특이한 언어가 있다고 가정해 봅시다. 이 언어는 무한히 많은 글자를 가지고 있으며, 우리는 이 언어로 작성된 n개의 단어를 알고 있습니다.여기서 흥미로운 규칙이 존재합니다.첫 번째 단어의 길이는 1, 두 번째 단어의 길이는 2와 같이 i번째 단어의 길이는 i입니다.각 단어를 이루는 모든 글자는 서로 중복되지 않습니다(유니크).이때 n개의 단어 중 하나를 골라 부분 수열(subsequence)을 만들려고 합니다. 조건은 다음과 같습니다.선택한 단어의 길이를 L이라 할 때, 부분 수열의 길이는 반드시

문제 개요숫자 A가 주어졌을 때, 이 숫자를 n번 반복해 이어 붙여 아주 큰 수 X를 생성하고, 그 값의 X mod m(m으로 나눈 나머지)을 구하는 것이 목표입니다.예를 들어 입력이 A = 15, n = 3, m = 8이라면, 이어 붙인 수 X는 151515가 되며, 151515 ÷ 8의 나머지는 3이므로 출력값은 3입니다.접근 방법X는 자릿수가 매우 커질 수 있으므로 실제로 문자열을 이어 붙이는 것은 비효율적입니다. 대신 수학적 성질을 활용하면 다음과 같이 정리할 수 있습니다.k를 A의 자릿수라고 하면, X = A × (10^(

문제 설명 크기가 n인 수열 nums가 주어져 있다고 가정해 봅시다. 이때 수열에서 추출할 수 있는 부분 수열(subsequence) 중, 모든 쌍 (p, q)이 좋은 쌍(nice pair)을 이루는 부분 수열의 최대 크기를 구해야 합니다. 두 수가 좋은 쌍이 되려면 아래 조건 중 적어도 하나를 만족해야 합니다. 소수 인수 개수의 홀짝성 일치: p의 서로 다른 소수 인수(distinct prime divisor) 개수가 홀수인지 짝수인지가 q와 같아야 합니다. 예를 들어 18은 2와 3, 두 개의 서로 다른 소수 인수를 가집니다.

문제 소개 2차원 평면상에 놓여 있는 두 개의 축에 평행한 직사각형이 차지하는 전체 면적을 구하는 프로그램을 만들어 보겠습니다. 여기서 각 직사각형은 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점의 좌표로 정의됩니다. 첫 번째 직사각형은 왼쪽 아래 점 (A, B)와 오른쪽 위 점 (C, D)로 정의되고, 두 번째 직사각형은 왼쪽 아래 점 (E, F)와 오른쪽 위 점 (G, H)로 정의됩니다. 접근 방법 핵심 아이디어는 단순합니다. 두 직사각형의 넓이를 각각 계산하여 더한 뒤, 두 직사각형이 겹치는 부분이 있다면 그 겹친 영역의 넓이를 한

조합(nCr) 값을 여러 번 계산해야 하는 상황을 가정해 보겠습니다. 이 문제는 매우 효율적으로 해결할 수 있습니다. 핵심 아이디어는 작은 값의 nCr 결과를 저장해 두면 이를 재활용하여 더 큰 값을 쉽게 구할 수 있다는 점입니다. 즉, n이 주어졌을 때 nC0부터 nCn까지의 전체 목록을 한 번에 구하는 것이 목표입니다. 만약 계산 결과가 너무 커진다면 10^9로 나눈 나머지를 반환하면 됩니다.예를 들어 입력이 n = 6이라면 출력은 [1, 6, 15, 20, 15, 6, 1]이 됩니다.해결 접근 방식조합의 성질을 이용하면 다음과

문제 개요₹1, ₹2, ₹5, ₹10 네 가지 액면가의 동전이 각각 제한된 수량만 있다고 가정해 봅시다. 이 동전들을 조합하여 정확히 ₹n을 만들 수 있는 방법이 총 몇 가지인지 구하는 것이 이번 문제의 목표입니다. 각 액면가별 보유 수량은 크기 4의 배열 count에 담겨 있으며, count[0]은 ₹1 동전의 개수, count[1]은 ₹2 동전의 개수를 나타내는 식입니다.예를 들어 n = 25이고 count = [7, 3, 2, 2]라면, 즉 ₹1 동전 7개, ₹2 동전 3개, ₹5 동전 2개, ₹10 동전 2개를 가지고 ₹25

문제 개요문자열 s가 주어졌을 때, 이 문자열의 글자들로 만들 수 있는 모든 가능한 조합을 찾는 프로그램을 작성해야 합니다. 단, 다음과 같은 조건이 있습니다.동일한 문자 집합을 가진 두 문자열이 존재한다면, 사전순(lexicographically)으로 가장 작은 것만 결과에 포함합니다.문자열 s를 구성하는 각 문자는 모두 고유(unique)합니다.입력 및 출력 예시예를 들어 입력이 s = pqr이라면, 출력은 다음과 같습니다.[r, qr, q, pr, pqr, pq, p]해결 접근 방법이 문제는 뒤에서부터 문자를 하나씩 처리하면서

두 개의 리스트 nums1과 nums2가 있다고 가정해 보겠습니다. 이때 병합 과정에서 각 리스트 내부 요소들의 상대적인 순서는 그대로 유지되어야 한다는 제약 조건이 있습니다.예를 들어 [1,2,3]과 [4,5,6]을 병합한다면, [1,4,2,3,5,6]이나 [1,2,3,4,5,6]처럼 유효한 병합 결과가 여러 가지 존재할 수 있습니다. 두 리스트의 크기가 각각 N과 M일 때, 유효한 병합 결과를 만들 수 있는 총 경우의 수를 구해야 합니다. 만약 답이 너무 커진다면 10^9 + 7로 나눈 나머지를 반환하면 됩니다.예를 들어 입력이

문제 이해하기n개의 공이 있고, 각 공은 크기가 n인 배열 nums의 값으로 번호가 매겨져 있다고 가정해 보겠습니다. 즉, nums[i]는 i번째 공의 번호를 나타냅니다. 여기에 또 하나의 값 k가 주어지며, 매 차례마다 n개의 서로 다른 공 중에서 k개를 골라 그 번호들의 최댓값과 최솟값의 차이를 표에 기록합니다. 그다음 k개의 공을 다시 항아리에 넣고, 가능한 모든 조합을 선택할 때까지 이 과정을 반복합니다. 마지막으로 표에 기록된 모든 차이의 합을 구하되, 결과가 너무 커질 경우 109+7로 나눈 나머지를 반환하면 됩니다.예시

문제 개요배열 nums가 주어졌을 때, nums[i]와 nums[j]의 값이 서로 같으면서 인덱스 i와 j는 서로 다른 쌍(i, j)의 개수를 구하는 문제입니다.예를 들어 입력이 nums = [1, 3, 1, 3, 5]라면 출력은 4가 됩니다. 조건을 만족하는 쌍은 (0, 2), (2, 0), (1, 3), (3, 1)이기 때문입니다.해결 접근 방법이 문제는 각 값이 배열에 몇 번 등장하는지 먼저 세어 놓으면 효율적으로 해결할 수 있습니다. 순서는 다음과 같습니다.등장 횟수를 저장할 빈 딕셔너리(맵) d를 생성합니다.nums의 각

문제 이해하기 배열 nums와 값 k가 주어졌을 때, 합이 k로 나누어 떨어지는 연속 부분 수열(연속된 원소로 이루어진 부분 배열)의 개수를 구해야 합니다. 예를 들어 k = 3, nums = [1,2,3,4,1]이라면 출력은 4가 됩니다. 조건을 만족하는 부분 수열이 [3], [1,2], [1,2,3], [2,3,4]로 총 4개이기 때문입니다. 접근 방법: 누적 합의 나머지 활용 모든 부분 배열을 일일이 확인하는 브루트 포스 방식은 O(n²)의 시간이 걸리지만, 누적 합(prefix sum)의 나머지를 활용하면 O(n)으로 효율