겹치지 않는 축에 평행한(axis-aligned) 직사각형들의 목록 rects가 주어졌다고 가정해 보겠습니다. 우리의 목표는 이 직사각형들이 덮고 있는 공간 안에 있는 정수 좌표의 점 하나를 무작위이면서도 균등한 확률로 선택하는 pick 함수를 작성하는 것입니다.문제 조건 정리정수 점(integer point)이란 x, y 좌표가 모두 정수인 점을 의미합니다.직사각형의 경계(둘레) 위에 있는 점도 선택 가능한 공간에 포함됩니다.i번째 직사각형 rects[i]는 [x1, y1, x2, y2]로 표현되며, [x1, y1]은 왼쪽 아래

문제 소개M × N 크기의 행렬이 주어졌을 때, 모든 요소를 대각선 순서로 탐색해야 하는 문제입니다. 이때 순회는 지그재그(zigzag) 패턴으로 진행되며, 대각선마다 이동 방향이 번갈아 바뀝니다. 예를 들어 다음과 같은 3 × 3 행렬이 있다고 가정해 보겠습니다.123456789이 행렬을 대각선 순서로 탐색한 결과는 [1, 2, 4, 7, 5, 3, 6, 8, 9]가 됩니다. 1에서 시작해 오른쪽 위 방향으로 이동했다가, 다음 대각선에서는 왼쪽 아래 방향으로 진행하는 식으로 방향이 교차하며 순회가 이루어집니다.알고리즘 접근 방법핵

문제 개요문자열 s가 주어졌을 때, s 안에서 가장 긴 회문 부분 수열(palindromic subsequence)의 길이를 찾는 것이 목표입니다. 문자열의 최대 길이는 1000이라고 가정할 수 있습니다. 예를 들어 입력이 bbbab라면 출력은 4이며, 이 경우 가능한 회문 부분 수열 중 하나는 bbbb입니다.여기서 말하는 부분 수열(subsequence)은 문자열에서 일부 문자를 제거하여 얻을 수 있는 수열로, 원래 문자의 순서는 유지되지만 반드시 연속적일 필요는 없습니다.해결 전략: 최장 공통 부분 수열(LCS) 활용이 문제의

문제 이해하기 n_rows개의 행과 n_cols개의 열을 가진 이진 행렬이 있다고 가정해 보겠습니다. 모든 값은 처음에 0으로 초기화되어 있으며, 여기서 두 가지 함수를 구현해야 합니다. flip(): 값이 0인 위치 하나를 균등한 확률로 무작위로 골라 1로 바꾸고, 그 좌표 [row_id, col_id]를 반환합니다. reset(): 행렬의 모든 값을 다시 0으로 되돌립니다. 핵심 요구 사항은 시스템의 난수 생성 함수 호출 횟수를 최소화하면서 시간 복잡도와 공간 복잡도까지 최적화하는 것입니다. 예를 들어 2×3 크기의 행렬에서

문제 개요음수가 아닌 정수로 이루어진 배열과 목표 정수 k가 주어졌을 때, 크기가 최소 2 이상인 연속 부분 배열의 합이 k의 배수(즉, n × k, 여기서 n도 정수)가 되는 경우가 존재하는지 판별하는 함수를 작성해야 합니다.예를 들어 입력 배열이 [23, 2, 4, 6, 7]이고 k = 6이라면 결과는 참(True)입니다. 부분 배열 [2, 4]의 크기는 2이며, 그 합이 6으로 k의 배수이기 때문입니다.핵심 아이디어: 누적 합과 나머지 연산이 문제는 누적 합(prefix sum)과 모듈로 연산의 성질을 활용하면 선형 시간 안에

하나의 문자열과 문자열 사전(dictionary)이 주어졌을 때, 주어진 문자열에서 일부 문자를 삭제하여 만들 수 있는 사전 내 가장 긴 문자열을 찾아야 합니다. 만약 가능한 결과가 여러 개라면, 그중 길이가 같은 단어들에 대해서는 사전순(lexicographical order)으로 가장 앞서는 단어를 반환합니다. 만족하는 결과가 없다면 빈 문자열을 반환합니다.예를 들어 입력 문자열이 abpcplea이고 사전 d = [ale, apple, monkey, plea]라고 한다면, 결과는 apple이 됩니다. apple은 abpcplea

이진 배열(0과 1로만 구성된 배열)이 주어졌을 때, 0과 1의 개수가 같은 가장 긴 연속 부분 배열의 길이를 찾는 문제입니다. 예를 들어 입력이 [0,1,0]이라면 출력은 2가 됩니다. [0,1] 또는 [1,0]이 0과 1의 개수가 동일한 가장 긴 연속 배열이기 때문입니다.해결 전략: 누적 합과 맵 활용이 문제를 효율적으로 풀려면 누적 합(prefix sum)과 맵(map)을 함께 사용하는 것이 핵심입니다. 핵심 아이디어는 0을 -1로 취급하는 것입니다. 그렇게 하면 누적 합이 같은 두 지점 사이의 구간에는 반드시 0과 1의 개수

1부터 N까지의 정수 N개가 있다고 가정해 보겠습니다. 이 N개의 숫자를 모두 사용해 만든 배열에서 임의의 위치 i(1 ≤ i ≤ N)에 대해 다음 조건 중 하나라도 성립하면, 그 배열을 아름다운 배열(Beautiful Arrangement)이라고 정의합니다.i번째 위치에 있는 숫자가 i로 나누어 떨어지는 경우i가 i번째 위치에 있는 숫자로 나누어 떨어지는 경우예제 이해하기예를 들어 입력이 2라면 정답은 2가 됩니다.[1, 2]: 1번 위치(i=1)의 숫자는 1이며, 1은 i=1로 나누어 떨어집니다. 2번 위치(i=2)의 숫자는 2

양의 정수 배열 w가 주어졌을 때, 각 원소 w[i]는 인덱스 i의 가중치를 의미합니다. 이때 가중치에 비례하여 인덱스를 무작위로 선택하는 함수 pickIndex()를 구현해야 합니다.예를 들어 입력이 [1, 3]이라면, 인덱스 0은 전체 가중치의 1/4 확률로, 인덱스 1은 3/4 확률로 선택됩니다. 따라서 pickIndex()를 다섯 번 호출하면 결과가 다음과 같이 나올 수 있습니다.0, 1, 1, 1, 0해결 접근 방법: 누적 합(Prefix Sum) 활용이 문제는 누적 합(prefix sum)과 이진 탐색(binary sea

이 글에서는 수열 3, 5, 33, 35, 53…의 N번째 항을 구하는 C++ 프로그램을 살펴보겠습니다.문제 조건은 간단합니다. 하나의 숫자 N이 주어지면, 해당 위치에 있는 수열의 값을 찾아 출력하면 됩니다. 수열의 패턴 분석 먼저 이 수열이 어떻게 만들어지는지 규칙을 확인해 보겠습니다. 첫 번째 항은 3, 두 번째 항은 5입니다. 홀수 번째 항(i ≥ 3): 이전 항 arr[i/2]에 10을 곱한 뒤 3을 더합니다. 짝수 번째 항(i ≥ 4): arr[(i/2) − 1]에 10을 곱한 뒤 5를 더합니다. 즉, 이 수열은 기존

개요이 튜토리얼에서는 반복문(iteration)을 사용하여 두 수의 HCF(Highest Common Factor, 최대공약수)를 구하는 C++ 프로그램을 다룹니다.HCF란 두 수를 모두 나누어 떨어지게 하는 가장 큰 양의 정수를 의미합니다. 예를 들어 60과 96의 경우, 두 수를 모두 나눌 수 있는 가장 큰 수는 12이므로 HCF는 12가 됩니다.알고리즘 원리여기서 사용하는 방식은 유클리드 호제법(Euclidean algorithm)의 뺄셈 기반 버전으로, 재귀 호출 없이 while 반복문만으로 해결할 수 있습니다. 동작 과정은

이 튜토리얼에서는 C++를 사용하여 입력된 문자가 모음(Vowel)인지 자음(Consonant)인지 판별하는 프로그램을 다룹니다.프로그램은 하나의 문자를 입력받으며, 해당 문자가 영어의 모음(a, e, i, o, u)에 속하는지 확인한 후 그 결과를 사용자에게 출력하는 것이 목표입니다.동작 원리판별 방식은 매우 간단합니다. 조건문(if-else)을 활용하여 입력 문자가 a, e, i, o, u 중 하나와 일치하는지 비교합니다. 일치하면 모음으로, 일치하지 않으면 자음으로 출력합니다.예제 코드#include <iostream&g

이 튜토리얼에서는 C++을 사용하여 배열에서 가장 큰 요소(최댓값)를 찾는 방법을 알아보겠습니다.배열이 하나 주어졌을 때, 우리의 목표는 배열에 포함된 여러 요소들 중에서 가장 큰 숫자를 찾아내는 것입니다.접근 방법가장 기본적이고 직관적인 방법은 다음과 같습니다.1. 배열의 첫 번째 요소를 초기 최댓값으로 설정합니다.2. 두 번째 요소부터 마지막 요소까지 배열을 순회하며 현재 최댓값과 비교합니다.3. 더 큰 값을 발견하면 최댓값을 해당 값으로 갱신합니다.4. 모든 요소를 확인한 후 최종 최댓값을 반환합니다.예제 코드#include

이 문제에서는 하나의 숫자 N이 주어지며, 우리의 목표는 C++를 사용하여 N번째 피보나치 수의 마지막 자릿수를 구하는 프로그램을 작성하는 것입니다.문제 설명N번째 피보나치 수의 마지막 자릿수, 즉 최하위 자릿수(LSB)를 구해야 합니다.예시를 통해 문제를 이해해 보겠습니다.입력: N = 120출력: 1풀이 접근 방식가장 간단한 방법은 피보나치 수열의 일반항 공식을 사용하여 N번째 항을 직접 계산하는 것입니다. 하지만 N이 매우 큰 수일 경우 이 방법은 연산량과 오버플로우 문제로 인해 실용적이지 않습니다.이 문제를 해결하기 위해 피

이 문제에서는 하나의 숫자 N이 주어지며, 우리의 목표는 C++를 사용해 2^n의 마지막 두 자리 숫자를 구하는 프로그램을 작성하는 것입니다.문제 설명마지막 두 자리 숫자만 구하면 되기 때문에, 계산 과정에서도 마지막 두 자리 숫자만 곱셈에 활용하고 나머지 값은 버려서 연산량을 최소화할 수 있습니다.예시를 통해 문제를 이해해 보겠습니다.입력: N = 12출력: 96설명2^12 = 4096이므로, 마지막 두 자리인 96이 결과가 됩니다.풀이 접근 방법가장 직관적인 방법은 2^N 값을 직접 계산한 뒤, 그 값을 100으로 나눈 나머지를

이 문제에서는 두 개의 정수 N과 M이 주어집니다. 우리의 목표는 C++로 두 피보나치 수의 최소공배수(LCM)를 구하는 프로그램을 작성하는 것입니다.문제 설명N번째 피보나치 수와 M번째 피보나치 수를 각각 구한 뒤, 두 수의 최소공배수를 계산하여 그 결과를 반환합니다.피보나치 수열0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377...예시로 이해하기입력: N = 4, M = 9출력: 42풀이 과정4번째 피보나치 수는 2입니다.9번째 피보나치 수는 21입니다.따라서 두 수의 최소공배수인

이 문제에서는 하나의 수 N이 주어지며, 우리의 과제는 C++를 이용해 N번째 피보나치 수의 마지막 두 자리를 구하는 프로그램을 작성하는 것입니다.문제 설명N번째 피보나치 수의 마지막 두 자리, 즉 최하위 두 자리 숫자(LSB 2개)를 구해야 합니다. 예시를 통해 문제를 살펴보겠습니다.입력: N = 120출력: 81해결 접근 방법가장 간단한 방법은 피보나치 일반항 공식을 사용하여 N번째 항을 직접 계산하는 것입니다. 하지만 N이 매우 커지면 이 방법은 현실적으로 사용하기 어렵습니다.이러한 한계를 극복하기 위해 피보나치 수열의 중요한

이 문제에서는 기차의 길이(L)와 속도(S), 그리고 기차가 다리를 통과하는 데 걸린 시간(T)이 주어집니다. 우리의 목표는 C++을 사용하여 이 정보들로부터 다리의 길이를 계산하는 프로그램을 작성하는 것입니다.문제 설명기차의 속도, 다리를 건너는 데 걸린 시간, 그리고 기차의 길이를 이용하여 다리의 길이를 구해야 합니다.예시를 통해 문제를 이해해 보겠습니다.입력: L = 310m, S = 45m/sec, T = 12sec출력: 230m풀이 접근 방법기차가 다리를 완전히 통과하는 동안 이동한 거리는 기차가 다리에 진입하는 순간부터

문제 소개이 문제에서는 하나의 숫자 N이 주어지며, C++을 사용해 수열 1, 2, 11, 12, 21…의 N번째 항을 구하는 프로그램을 작성하는 것이 목표입니다.문제 설명다음 수열의 N번째 항을 찾아야 합니다.1, 2, 11, 12, 21, 22, 111, 112, ... (총 N개의 항)이를 위해서는 먼저 수열의 일반항을 도출해야 합니다.예시를 통해 문제를 이해해 보겠습니다.입력N = 8출력112풀이 접근 방법일반항을 유도하려면 수열을 면밀히 관찰해야 합니다. 이 수열의 값에는 오직 1과 2만 사용되며, 모든 항이 1과 2가 번

문제 개요좌표평면 위에 있는 두 점 A와 B의 좌표가 주어졌을 때, 이 두 점을 지나는 직선의 방정식을 구하는 프로그램을 C++로 작성하는 것이 이번 문제의 목표입니다.문제 설명직선을 찾기 위해서는 직선의 방정식을 활용하고, 주어진 두 점의 좌표를 대입하여 계수를 구해야 합니다.예시를 통해 문제를 이해해 보겠습니다−입력: A = (3, 3), B = (6, 1)출력: 2x + 3y = 15풀이 접근 방법직선의 방정식을 구하기 위해 다음과 같은 일반형 방정식을 사용합니다.ax + by = c이 방정식은 두 점 A(x1, y