이 튜토리얼에서는 C++의 STL(표준 템플릿 라이브러리)을 사용하여 벡터(vector)를 내림차순으로 정렬하는 방법을 자세히 살펴보겠습니다.벡터를 내림차순으로 정렬하려면 STL 라이브러리에서 제공하는 sort() 함수를 사용합니다. sort() 함수는 기본적으로 오름차순으로 정렬되지만, 세 번째 인자로 greater<int>()와 같은 비교 함수자(functor)를 전달하면 손쉽게 내림차순 정렬을 구현할 수 있습니다.예제 코드#include <bits/stdc++.h> using namespace std;

이 튜토리얼에서는 C++에서 벡터(vector)의 한 칸에 데이터 세 개를 묶어 저장하는 방법, 즉 데이터 트리플렛(triplet)을 저장하는 프로그램을 살펴보겠습니다.벡터의 한 요소에 세 개의 값을 함께 저장하려면 먼저 사용자 정의 구조체(struct)를 선언한 뒤, 해당 구조체 타입으로 벡터를 생성하면 됩니다. 이렇게 하면 서로 연관된 여러 데이터를 하나의 단위로 깔끔하게 관리할 수 있습니다.예제 코드#include<bits/stdc++.h> using namespace std; struct Test{ int

C++ 표준 라이브러리의 std::swap_ranges 알고리즘을 사용하면 벡터(vector)와 리스트(list)처럼 서로 다른 컨테이너 사이에서도 특정 구간의 요소들을 손쉽게 맞바꿀 수 있습니다. 이번 글에서는 swap_ranges 함수의 기본 개념과 실제 사용 예제를 통해 두 컨테이너의 부분 범위를 교환하는 방법을 알아보겠습니다.swap_ranges란?std::swap_ranges는 <algorithm> 헤더에 정의된 함수로, 첫 번째 범위 [first1, last1)의 요소들과 second 인자가 가리키는 위치부터

이 글에서는 C++의 템플릿 특수화(Template Specialization) 개념을 예제 프로그램과 함께 자세히 살펴보겠습니다.C++에서 sort()와 같은 표준 함수는 어떤 데이터 타입에도 사용할 수 있으며, 각 타입에 대해 동일하게 동작합니다. 하지만 특정 데이터 타입(사용자가 정의한 타입 포함)에 대해서만 함수가 다르게 동작하도록 만들고 싶다면, 바로 템플릿 특수화를 활용하면 됩니다.템플릿 특수화란?템플릿 특수화는 일반 템플릿이 모든 타입에 대해 동일한 로직으로 동작하는 것과 달리, 특정 타입에 한해서 별도의 구현을 제공하

이번 튜토리얼에서는 C++에서 템플릿(template)과 정적 변수(static variable)가 어떻게 상호작용하는지 예제 프로그램을 통해 알아보겠습니다.C++에서 함수 템플릿이나 클래스 템플릿을 사용할 때 중요한 특징 중 하나는, 각각의 템플릿 인스턴스(instantiation)가 정적 변수에 대한 독립적인 복사본을 가진다는 점입니다. 즉, 동일한 템플릿이라도 타입 인자가 다르면 서로 다른 정적 변수가 생성됩니다.예제 코드#include <iostream> using namespace std; template &l

이진 트리가 하나 주어졌다고 가정해 봅시다. 우리의 목표는 이 트리를 제자리(in-place)에서 연결 리스트 형태로 평탄화(flatten)하는 것입니다.예를 들어 다음과 같은 트리가 있다면 −평탄화 작업이 끝난 후 출력되는 트리는 아래와 같은 모습이 됩니다. 모든 노드가 오른쪽 포인터를 따라 일렬로 연결된 형태입니다.해결 접근 방식이 문제는 역방향 후위 순회(reverse post-order traversal)를 활용하면 우아하게 해결할 수 있습니다. 핵심 아이디어는 오른쪽 서브트리부터 먼저 처리한 뒤 왼쪽 서브트리를

문제 개요다음과 같은 형태의 연결 리스트가 있다고 가정해 보겠습니다.l1 → l2 → l3 → l4 → … → l(n-1) → ln이 리스트를 다음과 같은 형태로 재배열해야 합니다.l1 → ln → l2 → l(n-1) → …여기서 중요한 제약 조건은 노드에 저장된 값 자체는 수정할 수 없고, 노드 간의 연결 구조만 변경할 수 있다는 점입니다.예를 들어, 입력 리스트가 [1, 2, 3, 4, 5]라면 출력 결과는 [1, 5, 2, 4, 3]이 됩니다. 즉, 앞쪽 노드와 뒤쪽 노드를 번갈아 배치하는 방식입니다.해결 전략이 문제는 크게

문제 소개연결 리스트(Linked List)가 주어졌을 때, 이를 O(n log n)의 시간 복잡도와 상수 공간 복잡도 조건 하에서 정렬하는 것이 이 글의 목표입니다. 예를 들어 입력 리스트가 [4, 2, 1, 3]이라면, 정렬 후에는 [1, 2, 3, 4]가 되어야 합니다.배열과 달리 연결 리스트는 임의 접근(random access)이 불가능하기 때문에 퀵 정렬이나 힙 정렬을 그대로 적용하기 어렵습니다. 따라서 이 문제는 병합 정렬(Merge Sort)을 활용하는 것이 가장 효율적이며, 재귀적으로 리스트를 분할한 뒤 정렬된 순서

문제 개요분자(numerator)와 분모(denominator)를 나타내는 두 개의 정수가 주어졌을 때, 이 분수를 문자열 형태의 소수로 변환하는 프로그램을 작성해야 합니다. 이때 소수 부분이 무한히 반복된다면, 반복되는 부분을 괄호로 묶어 표현해야 합니다.예를 들어 분자가 2이고 분모가 3이라면, 2 ÷ 3 = 0.6666...이므로 출력 결과는 0.(6)이 됩니다.해결 전략이 문제는 우리가 손으로 나눗셈을 계산하는 과정을 그대로 코드로 옮기는 방식으로 해결할 수 있습니다. 핵심 아이디어는 나머지(remainder)를 추적하는 것

문제 소개 n개의 원소를 가진 배열과 양의 정수 s가 주어졌다고 가정해 봅시다. 우리가 찾아야 할 것은 합이 s 이상이 되는 연속된 부분 배열 중 가장 짧은 길이입니다. 만약 조건을 만족하는 부분 배열이 하나도 존재하지 않는다면 0을 반환하면 됩니다. 예를 들어 배열이 [2,3,1,2,4,3]이고 s가 7이라면 정답은 2입니다. [4,3]이라는 부분 배열의 합이 정확히 7이 되면서, 조건을 만족하는 부분 배열 중 길이가 가장 짧기 때문입니다. 해결 전략: 슬라이딩 윈도우 이 문제는 두 개의 포인터를 활용한 슬라이딩 윈도우(Slid

문제 개요0과 1로만 채워진 2차원 이진 행렬(binary matrix)이 주어졌을 때, 1로만 구성된 가장 큰 정사각형을 찾아 그 면적을 반환하는 것이 이번 문제의 목표입니다.예를 들어 다음과 같은 행렬이 주어진 경우를 살펴보겠습니다.10100101101111110010이 행렬에서 1로만 이루어진 가장 큰 정사각형은 크기가 2×2이므로, 최종 출력값은 4가 됩니다.해결 전략: 동적 계획법(Dynamic Programming)이 문제는 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 위치에서 만들 수 있는

C++ 흔들기 정렬 II(Wiggle Sort II)란?정렬되지 않은 배열 nums가 주어졌을 때, nums[0] < nums[1] > nums[2] < nums[3] ...처럼 값이 오르내리기를 반복하는 파도 모양(교차 순서)이 되도록 재배열하는 문제입니다.예를 들어 입력이 [1,5,1,1,6,4]라면, 결과는 [1,6,1,5,1,4]가 됩니다. 즉, 짝수 번째 인덱스의 값은 양쪽 이웃보다 작고, 홀수 번째 인덱스의 값은 양쪽 이웃보다 커야 합니다.접근 방법이 문제의 핵심 아이디어는 다음과 같습니다.원본 배열을 복

문제 소개2차원 보드가 주어졌을 때, 보드 위에 있는 전함(battleship)의 개수를 세는 문제입니다. 전함은 문자 X로 표현되며, 빈 칸은 .으로 표현됩니다. 이때 다음과 같은 규칙이 성립한다고 가정할 수 있습니다.주어지는 보드는 항상 유효하며, 전함 또는 빈 칸으로만 구성되어 있습니다.전함은 가로 또는 세로 방향으로만 배치할 수 있습니다. 즉, 전함의 형태는 1xN(1행 N열) 또는 Nx1(N행 1열)이며, N은 어떤 크기든 가능합니다.두 전함 사이에는 최소 하나의 가로 또는 세로 빈 칸이 존재합니다. 즉, 서로 인접한 전함

N-ary 트리(N-ary Tree)는 각 노드가 최대 n개의 자식 노드를 가질 수 있는 트리 구조입니다. 이번 글에서는 이러한 N-ary 트리의 레벨 순회(Level Order Traversal), 즉 너비 우선 탐색(BFS) 방식으로 노드 값을 층별로 출력하는 방법을 C++ 코드와 함께 자세히 알아보겠습니다.문제 정의N-ary 트리가 주어졌을 때, 각 노드의 값을 레벨(깊이) 단위로 묶어 반환하는 것이 목표입니다. 입력은 레벨 순회 형태로 직렬화되며, 각 그룹의 자식 노드들은 null 값으로 구분됩니다.예를 들어 다음과 같은 트

여러 개의 간격(interval)이 주어졌을 때, 나머지 간격들이 서로 겹치지 않도록 만들기 위해 제거해야 하는 간격의 최소 개수를 구하는 문제입니다.예를 들어 간격이 [[1,2], [2,3], [3,4], [1,3]]과 같이 주어진 경우, [1,3]만 제거하면 나머지 간격들이 모두 겹치지 않게 되므로 출력값은 1이 됩니다.문제 해결 전략이 문제는 탐욕(Greedy) 알고리즘을 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 간격을 끝나는 시점(end) 기준으로 정렬한 뒤, 겹치지 않고 선택할 수 있는 간격의 수를 최대화하는

문제 개요이진 탐색 트리(Binary Search Tree, BST)가 주어져 있다고 가정해 보겠습니다. 하나의 키 k를 입력받아 BST에서 해당 키를 가진 노드를 삭제한 뒤, 갱신된 BST를 반환하는 것이 목표입니다.예를 들어 다음과 같은 트리가 있고,삭제할 키가 k = 3이라면, 최종 출력 트리는 다음과 같습니다.해결 접근 방법이 문제는 크게 두 단계로 나누어 해결할 수 있습니다. 먼저 루트 노드를 삭제하는 헬퍼 함수를 정의하고, 이를 활용해 트리 내부의 목표 노드를 찾아 삭제하는 방식입니다.1단계: deleteRoot() 메서

문제 이해하기2차원 공간에 여러 개의 구형 풍선이 흩어져 있다고 가정해 봅시다. 각 풍선은 수평 지름의 시작 좌표(xstart)와 끝 좌표(xend)를 가지며, 시작 좌표는 항상 끝 좌표보다 작습니다. 풍선의 개수는 최대 104개입니다.화살은 x축 위의 임의의 지점에서 정확히 수직 방향으로 발사할 수 있으며, 발사 횟수에는 제한이 없습니다. 또한 한 번 발사된 화살은 무한히 위로 계속 날아간다고 가정합니다. 위치가 xstart부터 xend까지인 풍선은 xstart ≤ x ≤ xend를 만족하는 지점 x에서 발사된 화살에 맞으면 터집

문제 개요 양수와 음수 정수로 구성된 원형 배열 nums가 있다고 가정해 보겠습니다. 특정 인덱스의 값 k가 양수라면 앞으로 k칸 이동하고, 음수(-k)라면 뒤로 k칸 이동합니다. 배열이 원형(circular)이므로 마지막 요소의 다음 요소는 첫 번째 요소가 되고, 첫 번째 요소의 이전 요소는 마지막 요소가 됩니다. 목표는 nums 안에 루프(사이클)가 존재하는지 판별하는 것입니다. 여기서 유효한 사이클은 시작과 끝이 같은 인덱스여야 하며, 길이가 1보다 커야 합니다. 예를 들어 입력이 [2,-1,1,2,2]라면 인덱스 0 → 2

문제 개요트리의 루트(root)가 주어졌을 때, 가장 빈번하게 등장하는 서브트리 합(most frequent subtree sum)을 찾아야 합니다.여기서 서브트리 합이란 특정 노드를 루트로 하는 서브트리에 포함된 모든 노드 값(해당 노드 자신 포함)의 합을 의미합니다. 만약 최빈값이 여러 개라면, 가장 높은 빈도를 가진 모든 값을 임의의 순서로 반환하면 됩니다.예를 들어 트리가 [5, 2, -5]와 같이 구성되어 있다면 결과는 [2]가 됩니다. 그 이유는 각 노드의 서브트리 합을 계산해 보면 다음과 같습니다.노드 2의 서브트리 합

이진 트리가 하나 주어졌다고 가정해 봅시다. 우리가 구해야 할 것은 이 트리의 마지막 행(가장 깊은 층)에서 가장 왼쪽에 있는 값입니다. 예를 들어 트리가 다음과 같다면 −마지막 행은 [7, 4]이고, 그중 가장 왼쪽 요소가 7이므로 출력 결과는 7이 됩니다.문제 해결 접근 방법이 문제는 깊이 우선 탐색(DFS)과 레벨 추적을 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 더 깊은 레벨에 도달할 때마다 해당 노드의 값을 정답으로 갱신하는 것입니다. 전위 순회(preorder) 순서로 왼쪽 자식을 먼저 방문하기 때