rows × cols 크기의 화면과 비어 있지 않은 단어들로 구성된 문장이 주어졌을 때, 이 문장 전체가 화면에 몇 번 온전히 들어갈 수 있는지 구하는 문제입니다. 이 문제에는 다음과 같은 제약 조건이 있습니다. 단어는 두 줄에 걸쳐 나뉘어질 수 없습니다. 문장 안에서 단어의 순서는 절대 바뀌지 않습니다. 두 단어 사이에는 공백이 정확히 하나만 존재합니다. 문장을 이루는 단어의 총 개수는 100개를 초과하지 않습니다. 각 단어의 길이는 0보다 크고 10보다 작습니다. 1 ≤ rows, cols ≤ 20,000 입니다. 예를 들

문제 소개구간(interval)들의 배열이 주어져 있고, 각 구간 i에 대해 시작점이 구간 i의 끝점보다 크거나 같은 다른 구간 j가 존재하는지 확인해야 합니다. 이때 구간 j를 구간 i의 "오른쪽(right)"에 있다고 표현합니다.모든 구간 i에 대해, 조건을 만족하는 구간 j 중에서 시작점이 가장 작은 구간의 인덱스를 저장해야 하며, 만약 조건을 만족하는 구간이 하나도 없다면 -1을 저장합니다. 최종적으로 각 구간에 저장된 값을 배열 형태로 출력하면 됩니다.예를 들어 입력이 [[3,4], [2,3], [1,2]

임의로 중첩된 삼항 표현식(ternary expression)을 나타내는 문자열이 주어졌을 때, 해당 표현식의 최종 결과를 계산하는 문제를 살펴보겠습니다. 입력으로 주어지는 표현식은 항상 유효하며, 숫자 0~9, ?, :, T, F 다섯 종류의 문자로만 구성됩니다. 여기서 T와 F는 각각 참(True)과 거짓(False)을 의미합니다.문제의 제약 조건주어진 문자열의 길이는 10,000 이하여야 합니다.각 숫자는 한 자리(0~9)로만 구성됩니다.조건식은 오른쪽에서 왼쪽 방향(right-to-left)으로 그룹화됩니다.조건 부분은 항상

문제 개요n개의 정수로 이루어진 수열 a₁, a₂, ..., aₙ이 주어졌을 때, 132 패턴은 인덱스 조건 i < j < k를 만족하면서 값의 조건 aᵢ < aₖ < aⱼ를 만족하는 부분 수열 aᵢ, aⱼ, aₖ를 의미합니다. 즉, 가장 작은 값, 가장 큰 값, 그리고 그 사이에 있는 값의 순서로 배치된 부분 수열을 찾아야 합니다.우리의 목표는 n개의 숫자 목록을 입력으로 받아 이 목록 안에 132 패턴이 존재하는지 확인하는 알고리즘을 설계하는 것입니다.예를 들어 입력이 [-1, 3, 2, 0]이라면 출력은

100 만들기라는 게임을 상상해 봅시다. 두 플레이어가 번갈아 가며 누적 합계에 1부터 10 사이의 정수를 하나씩 더하고, 누적 합계를 처음으로 100 이상 만든 플레이어가 승리합니다. 그렇다면 규칙을 바꿔 이미 사용한 숫자는 다시 쓸 수 없다면 어떻게 될까요? 예를 들어 두 플레이어가 1부터 15까지의 숫자가 담긴 공용 풀에서 중복 없이 번갈아 숫자를 꺼내, 누적 합계가 100 이상이 될 때까지 게임을 진행한다고 가정해 봅시다. 정수 maxChoosableInteger(선택 가능한 최대 숫자)와 정수 desiredTotal(목표

문제 이해하기문자열 s를 알파벳 abcdefghijklmnopqrstuvwxyz가 무한히 반복되는 순환(wraparound) 문자열이라고 가정해 보겠습니다. 이때 s는 다음과 같은 형태를 갖습니다....zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....이제 또 다른 문자열 p가 주어졌을 때, p의 고유한(중복되지 않는) 비어 있지 않은 부분 문자열 중 문자열 s에 포함되는 것의 개수를 구하는 것이 우리의 과제입니다. 즉, 입력으로 문자열 p가 주어지면, p의 서로 다른 비어

순서대로 연결했을 때 하나의 다각형을 이루는 점들의 목록이 주어졌을 때, 이 다각형이 볼록 다각형(convex polygon)인지 판별하는 문제입니다. 이때 점의 개수는 최소 3개에서 최대 10,000개이며, 각 좌표 값은 -10,000부터 10,000 사이의 범위에 있다는 조건이 주어집니다.주어진 점들로 형성되는 다각형은 항상 단순 다각형(simple polygon)이라고 가정할 수 있습니다. 즉, 각 꼭짓점에서 정확히 두 개의 변이 만나고, 그 외의 경우에는 변들이 서로 교차하지 않는다는 것이 보장됩니다. 예를 들어 입력이 [[

문제 소개 여러 개의 구절(phrase)로 이루어진 목록이 주어졌을 때, 이를 조합하여 만들 수 있는 전후 퍼즐(Before and After Puzzles) 목록을 생성하는 문제를 살펴보겠습니다. 여기서 구절이란 소문자 알파벳과 공백으로만 구성된 문자열을 의미하며, 시작과 끝에는 공백이 없고 연속된 공백도 존재하지 않는다고 가정합니다. 전후 퍼즐은 두 구절을 병합하여 만든 문장입니다. 이때 첫 번째 구절의 마지막 단어와 두 번째 구절의 첫 번째 단어가 서로 같아야 하며, 겹치는 단어는 하나만 남기고 이어 붙입니다. 모든 구절 쌍

값이 1, 2, 3 세 가지 색상으로만 이루어진 배열 colors가 있다고 가정해 보겠습니다. 여기에 여러 개의 쿼리(query)가 주어지며, 각 쿼리는 두 개의 정수 i(인덱스)와 c(목표 색상)로 구성됩니다. 우리가 해야 할 일은 인덱스 i와 색상 c 사이의 최단 거리를 찾는 것이고, 만약 해당 색상이 배열에 존재하지 않아 해가 없다면 -1을 반환해야 합니다.예를 들어 색상 배열이 [1,1,2,1,3,2,2,3,3]이고, 쿼리 배열이 [[1,3],[2,2],[6,1]]이라면 출력은 [3,0,3]이 됩니다.인덱스 1에서 가장 가까

소문자 알파벳과 괄호로 구성된 문자열 s가 주어졌다고 가정해 봅시다. 우리가 해야 할 작업은 가장 안쪽 괄호부터 시작하여 서로 짝을 이루는 각 괄호 쌍 내부의 문자열을 뒤집는 것이며, 최종 결과에는 괄호가 남아 있으면 안 됩니다.예를 들어 입력이 (hel(lowo)rld)라고 한다면, 출력은 dlrlowoleh가 됩니다. 변환 과정은 다음과 같이 진행됩니다.(hel(lowo)rld) → (helowolrld) → dlrowoleh해결 접근 방법이 문제는 스택(Stack)을 활용한 방향 전환 기법으로 효율적으로 해결할 수 있습니다.

문제 소개 좌표가 -∞에서 +∞까지 뻗어 있는 무한 체스판을 상상해 봅시다. 나이트는 [0, 0] 위치에서 출발하며, 아래 그림과 같이 총 8가지 방향으로 이동할 수 있습니다. 각 이동은 한 축 방향으로 두 칸, 그에 수직인 방향으로 한 칸 움직이는 형태입니다. 우리의 목표는 나이트를 목표 좌표 [x, y]로 옮기는 데 필요한 최소 이동 횟수를 구하는 것입니다. 문제 조건상 답은 항상 존재한다고 보장됩니다. 예시 입력이 x = 5, y = 5라면 출력은 4가 됩니다. 실제 이동 경로는 다음과 같습니다. [0,0] → [2,1] →

문제 소개모든 행이 비내림차순(오름차순)으로 정렬된 행렬 mat이 주어졌을 때, 모든 행에 공통으로 존재하는 가장 작은 요소를 찾아야 합니다. 만약 그러한 공통 요소가 하나도 없다면 -1을 반환하면 됩니다.예를 들어 다음과 같은 행렬이 있다고 가정해 보겠습니다.1234524581035791113579네 개의 행을 모두 살펴보면 5만이 모든 행에 등장하므로, 출력 결과는 5입니다.풀이 접근 방법이 문제는 맵(Map)을 활용한 빈도 카운팅으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 요소가 몇 번째 행까지 연속해서 등장했는지

이번 글에서는 n번째 못생긴 수(Ugly Number)를 찾는 프로그램을 C++로 구현해 보겠습니다. 여기서 말하는 못생긴 수란 a, b 또는 c 중 하나 이상으로 나누어 떨어지는 양의 정수를 의미합니다.예를 들어 n = 3, a = 2, b = 3, c = 5라고 가정해 보겠습니다. 이 경우 못생긴 수는 [2, 3, 4, 5, 6, 8, 9, 10] 순서로 나열되며, 세 번째 값인 4가 출력 결과가 됩니다.문제 해결 접근 방법이 문제는 포함-배제 원리(Inclusion-Exclusion Principle)와 이진 탐색(Binary

문자열 s와 인덱스 쌍 배열 pairs가 주어집니다. pairs[i] = [a, b]는 문자열에서 0부터 시작하는 두 인덱스를 의미하며, 우리는 이 쌍에 해당하는 위치의 문자들을 원하는 만큼 몇 번이든 자유롭게 교환할 수 있습니다. 목표는 이러한 교환 연산을 통해 만들 수 있는 문자열 중 사전순으로 가장 작은(lexicographically smallest) 문자열을 찾는 것입니다. 예를 들어 입력이 s = dcab, pairs = [[0,3], [1,2]]라면 출력은 bacd입니다. 먼저 s[0]과 s[3]을 교환하여 s = b

문제 개요길이가 같은 두 문자열 s와 t가 주어진다고 가정해 봅시다. 우리는 s를 t로 바꾸고자 합니다. 이때 s의 i번째 문자를 t의 i번째 문자로 변경하는 비용은 |s[i] - t[i]|, 즉 두 문자의 ASCII 값 차이의 절댓값으로 정의됩니다. 추가로 정수 maxCost가 주어지며, 총 비용이 maxCost 이하인 조건 안에서 s의 부분 문자열을 t의 대응되는 부분 문자열과 동일하게 변환할 수 있는 최대 길이를 구해야 합니다.예를 들어 입력이 s = abcd, t = bcdf이고 maxCost가 3이라면, s의 abc를 bc

문제 설명정확히 n개의 좌석이 있는 비행기에 n명의 승객이 탑승한다고 가정해 보겠습니다. 이때 첫 번째 승객은 항공권을 분실하여 자리에 상관없이 무작위로 좌석을 선택합니다.그 후 나머지 승객들은 다음과 같은 규칙에 따라 자리를 찾아갑니다.자신의 항공권에 적힌 좌석이 아직 비어 있다면, 그 좌석에 앉는다.자신의 좌석이 이미 다른 사람에게 차지되어 있다면, 남은 좌석 중에서 무작위로 하나를 선택한다.우리가 구해야 할 것은 바로 n번째 승객이 자신의 원래 좌석에 앉을 확률입니다.예를 들어 입력이 2라면 출력은 0.5가 됩니다. 첫 번째

문제 개요불변(immutable) 연결 리스트가 하나 주어져 있다고 가정해 보겠습니다. 이 리스트는 수정할 수 없기 때문에 일반적인 방법처럼 포인터를 조작해 뒤집을 수 없으며, 대신 주어진 인터페이스를 활용해 각 노드의 값을 역순으로 모두 출력해야 합니다.ImmutableListNode — 불변 연결 리스트의 인터페이스이며, 리스트의 머리(head) 노드가 입력으로 주어집니다.연결 리스트에 접근할 수 있는 함수는 아래 두 가지뿐입니다.printValue() — 현재 노드의 값을 출력합니다.getNext() — 다음 노드를 반환합니다

이 튜토리얼에서는 C++의 입력 반복기(Input Iterator)에 대해 자세히 알아보겠습니다.입력 반복기는 STL(표준 템플릿 라이브러리)에서 제공하는 다섯 가지 반복기 중 하나로, 그중에서도 가장 단순하고 기능이 제한적인 반복기입니다. 주로 순차 입력 작업에 사용되며, 값을 하나씩 읽은 후 반복기가 다음 요소로 이동하는 방식으로 동작합니다.입력 반복기의 특징입력 반복기는 다음과 같은 특징을 가지고 있습니다.값을 읽기만 가능하며, 참조된 요소를 수정할 수 없습니다.단방향으로만 이동할 수 있어 한 번 지나간 요소를 다시 접근할 수

이 튜토리얼에서는 C++의 STL set 컨테이너에서 요소를 삽입하고 삭제하는 방법을 예제 코드와 함께 자세히 살펴보겠습니다.set 컨테이너란?set은 STL에서 제공하는 연관 컨테이너(associative container)입니다. 다음과 같은 특징을 가지고 있습니다.중복 불가: 동일한 값을 가진 요소를 하나만 저장할 수 있습니다.자동 정렬: 요소들이 항상 정렬된 상태로 유지되므로, 순회 시 항상 오름차순으로 값에 접근할 수 있습니다.빠른 검색: 내부적으로 균형 이진 탐색 트리(레드-블랙 트리) 기반으로 구현되어 있어 삽입, 삭제

이번 튜토리얼에서는 C++ STL(표준 템플릿 라이브러리)을 활용하여 삽입 정렬(Insertion Sort)을 구현하는 방법을 살펴보겠습니다.일반적인 삽입 정렬은 이중 반복문을 사용하지만, STL을 활용하면 훨씬 간결하고 안전한 코드를 작성할 수 있습니다. 핵심 아이디어는 다음과 같습니다.std::upper_bound를 사용해 현재 원소가 들어가야 할 올바른 위치(정렬된 구간 내에서 처음으로 더 큰 값이 나오는 지점)를 찾습니다.std::rotate를 사용해 배열의 미정렬 구간을 회전시켜 해당 원소를 올바른 자리에 삽입합니다.예제