C++ 표준 라이브러리(STL)에서 가장 자주 사용되는 알고리즘 중 하나인 std::sort()는 이름 그대로 컨테이너나 배열의 요소들을 오름차순으로 정렬해 주는 함수입니다. 겉보기에는 간단해 보이지만, 내부적으로는 상당히 정교한 알고리즘이 숨어 있습니다.std::sort()의 핵심: IntroSort 알고리즘std::sort()는 단순히 퀵 정렬(Quick Sort)만 사용하는 것이 아니라, IntroSort(Introspective Sort)라는 하이브리드 알고리즘을 기반으로 동작합니다. IntroSort는 다음 세 가지 정렬

C++ 반복자 무효화란? 이 글에서는 C++에서 자주 발생하는 반복자 무효화(iterator invalidation) 문제를 예제 코드와 함께 살펴보고, 이를 예방하는 안전한 코딩 방법까지 함께 정리합니다. 컨테이너 객체의 요소를 순회하는 도중 경계 검사 없이 컨테이너를 수정하면 반복자가 무효화될 수 있습니다. 이는 주로 컨테이너의 크기나 내부 구조가 변경될 때 발생하며, 무효화된 반복자를 사용하면 정의되지 않은 동작(undefined behavior)이 발생합니다. 문제 상황 예제 #include <bits/stdc++.h&

이 글에서는 C++ STL의 lower_bound() 함수에 대해 자세히 알아보겠습니다. C++의 lower_bound() 메서드는 컨테이너 객체에서 주어진 값보다 작지 않은(즉, 값 이상인) 첫 번째 요소를 가리키는 반복자(iterator)를 반환하는 함수입니다. 이 함수는 내부적으로 이진 탐색(binary search) 알고리즘을 기반으로 동작하기 때문에, 정확한 결과를 얻으려면 탐색 대상 컨테이너가 반드시 사전에 오름차순으로 정렬되어 있어야 합니다. lower_bound()의 동작 방식 lower_bound()는 지정된 탐색

개요이 튜토리얼에서는 C++의 STL(표준 템플릿 라이브러리)을 활용하여 크루스칼(Kruskal) 최소 신장 트리(Minimum Spanning Tree, MST) 알고리즘을 구현하는 방법을 살펴봅니다.크루스칼 알고리즘은 연결된 무방향 가중치 그래프가 주어졌을 때, 모든 정점을 연결하면서 간선 가중치의 총합이 최소가 되는 신장 트리를 찾는 대표적인 그리디(Greedy) 알고리즘입니다.알고리즘 동작 원리크루스칼 알고리즘은 다음 순서로 진행됩니다.그래프의 모든 간선을 가중치 기준 오름차순으로 정렬합니다.가중치가 가장 작은 간선부터 차례

C++로 규모가 있는 프로젝트를 개발하다 보면 여러 개의 소스 파일과 헤더 파일을 각각 컴파일하고, 이를 하나의 실행 파일로 묶는 과정이 필요합니다. 이번 글에서는 이러한 빌드 과정을 자동화해 주는 Makefile의 개념과 실제 활용 방법을 예제 코드와 함께 살펴보겠습니다. Makefile이란 무엇인가? Makefile은 make 빌드 도구가 수행할 작업을 정의하는 설정 파일입니다. 일반적으로 C++ 프로젝트는 클래스나 기능 단위로 .cpp 파일과 .h 파일을 분리해서 작성한 뒤, Makefile이 이 파일들을 컴파일하고 서로 링크

C++에서 order_of_key()란 무엇인가?이 글에서는 C++의 order_of_key() 함수에 대해 자세히 알아보겠습니다.order_of_key()는 정렬된 집합(ordered set)에서 매개변수로 전달받은 키(key)보다 작은 원소의 개수를 반환하는 함수입니다. 이 함수는 C++ 표준 라이브러리가 아닌, GCC 컴파일러가 제공하는 GNU PBDS(Policy-Based Data Structures) 라이브러리에 포함되어 있으며, 주로 경쟁 프로그래밍에서 순위 통계 기능이 필요할 때 유용하게 활용됩니다.예를 들어, 집합에

이 튜토리얼에서는 C++ STL(표준 템플릿 라이브러리)에서 제공하는 multiset의 size() 함수에 대해 자세히 알아보겠습니다.size() 함수는 해당 컨테이너에 현재 저장되어 있는 요소의 총 개수를 반환하는 멤버 함수입니다. multiset은 일반 set과 달리 중복된 값을 허용하기 때문에, 같은 값이 여러 번 삽입되면 그만큼 개수도 함께 증가한다는 점이 특징입니다.size() 함수의 주요 특징컨테이너 내 실제 요소 개수를 반환합니다.C++11 표준부터는 상수 시간 복잡도(O(1))로 동작하여 매우 빠릅니다.중복 요소도 각

이 튜토리얼에서는 C++ STL에서 제공하는 multiset 컨테이너의 max_size() 함수에 대해 자세히 알아보겠습니다.max_size() 함수란?max_size()는 해당 컨테이너가 시스템 환경 및 라이브러리 구현에 따라 저장할 수 있는 이론상 최대 요소 개수를 반환하는 함수입니다. 이 값은 실제 사용 가능한 메모리 양에 따라 달라질 수 있으며, 프로그램 실행 중에는 일반적으로 일정하게 유지됩니다.참고로 size()가 현재 실제로 저장된 요소의 개수를 반환한다면, max_size()는 컨테이너가 담을 수 있는 상한선을 의미합

이 튜토리얼에서는 C++의 negative_binomial_distribution을 이해할 수 있는 예제 프로그램을 다룹니다.negative_binomial_distribution은 음이항 이산 분포를 따르며, 이 확률 분포에 기반해 정수형 난수를 생성하는 클래스입니다. 통계학적으로 음이항 분포는 독립적인 베르누이 시행에서 k번째 성공이 나타나기 전까지 발생한 실패 횟수를 모델링하며, 매개변수 k(성공 횟수)와 p(성공 확률)에 의해 분포의 형태가 결정됩니다.예제 코드#include <bits/stdc++.h> using

C++ STL multiset upper_bound() 함수란? 이 튜토리얼에서는 C++ STL의 multiset(멀티셋) 컨테이너에서 제공하는 upper_bound() 함수의 동작 방식과 사용법을 실제 예제와 함께 자세히 살펴보겠습니다. upper_bound() 함수는 매개변수로 전달된 키(key) 값보다 큰 첫 번째 요소를 가리키는 반복자(iterator)를 반환합니다. 만약 그보다 큰 요소가 컨테이너에 존재하지 않는다면, 컨테이너의 마지막 요소를 가리키는 반복자를 반환합니다. multiset은 중복 값을 허용하는 정렬된 연관

이 글에서는 C++ STL의 multiset 컨테이너에서 제공하는 lower_bound() 함수가 어떻게 동작하는지 예제 코드를 통해 자세히 살펴보겠습니다. lower_bound() 함수란? lower_bound()는 multiset 내부에서 전달된 키(key) 값과 같은 첫 번째 원소를 가리키는 반복자(iterator)를 반환합니다. 만약 해당 값과 일치하는 원소가 존재하지 않는다면, 그 값보다 큰 첫 번째 원소를 가리킵니다. 즉, 항상 정렬된 상태를 유지하는 multiset에서 특정 값 이상인 원소 중 가장 앞쪽에 있는 위치를

이 글에서는 C++ STL(표준 템플릿 라이브러리)의 멀티셋(multiset)에 대해 자세히 알아보겠습니다. 멀티셋의 기본 개념부터 삽입, 삭제, 탐색까지 실제 예제 코드를 통해 쉽게 이해할 수 있도록 정리했습니다.멀티셋(multiset)이란?멀티셋은 연관 컨테이너(associative container)의 일종으로, 일반적인 셋(set)과 매우 유사하게 동작합니다. 두 컨테이너의 가장 큰 차이점은 다음과 같습니다.셋(set): 중복된 값을 허용하지 않습니다.멀티셋(multiset): 중복된 값도 함께 저장할 수 있습니다.멀티셋은

개요 이 튜토리얼에서는 간단한 계산기를 구현하는 메뉴 기반(menu-driven) C++ 프로그램을 만드는 방법을 단계별로 살펴보겠습니다. 이 프로그램은 사용자가 원하는 연산을 직접 선택할 수 있도록 메뉴를 제공하며, 다음과 같은 여섯 가지 수학 연산을 지원합니다. 덧셈(Sum) 뺄셈(Difference) 곱셈(Product) 나눗셈(Division) 최대공약수(HCF · GCD) 최소공배수(LCM) 여기서 HCF(Highest Common Factor)는 일반적으로 말하는 최대공약수(GCD)를 의미하고, LCM(Least C

이 튜토리얼에서는 C++ STL의 set 컨테이너를 활용하여 크기가 K인 모든 부분 배열의 최댓값을 구하는 방법을 살펴보겠습니다. 문제 개요 크기가 N인 배열과 정수 K가 주어집니다. 우리의 과제는 연속된 K개의 요소로 구성된 각 부분 배열에서 최댓값을 찾아내고, 이 값들을 모두 더한 뒤 결과를 출력하는 것입니다. 예를 들어 배열이 {4, 10, 54, 11, 8, 7, 9}이고 K가 3이라면 각 윈도우의 최댓값은 다음과 같습니다. {4, 10, 54} → 최댓값 54 {10, 54, 11} → 최댓값 54 {54, 11, 8}

이 글에서는 C++ STL의 map 컨테이너에서 제공하는 equal_range() 함수의 개념과 실제 사용 방법을 자세히 살펴봅니다. equal_range() 함수는 매개변수로 전달된 키와 동일한 키가 속한 컨테이너의 범위를 감싸는 반복자(iterator) 쌍(pair)을 반환합니다. 반환된 pair에서 first는 하한(lower bound)에 해당하는 요소를, second는 상한(upper bound)에 해당하는 요소를 가리킵니다. 여기서 하한은 해당 키보다 작지 않은 첫 번째 요소를 의미하고, 상한은 해당 키보다 큰 첫 번째

각 원소가 0 또는 1로만 이루어진 2차원 행렬 A가 있다고 가정해 보겠습니다. 여기서 이동(move)이란 임의의 행 또는 열 하나를 선택하여 해당 행(또는 열)에 속한 모든 값을 뒤집는 연산을 의미합니다. 즉, 0은 1로, 1은 0으로 바꾸는 작업입니다.원하는 만큼 이동을 수행한 뒤에는 행렬의 각 행이 하나의 이진수로 해석되며, 행렬의 점수는 이 숫자들의 총합이 됩니다. 따라서 우리의 목표는 가능한 한 가장 높은 점수를 찾는 것입니다.예를 들어 입력이 다음과 같다면 −001110101100출력은 39가 됩니다. 적절히 뒤집기 연산

이 문제에서는 주어진 수 N보다 크거나 같은 수 중에서 가장 작은 소수 회문(Prime Palindrome)을 찾아야 합니다. 회문이란 앞에서 읽으나 뒤에서 읽으나 같은 수를 의미하며, 소수 회문은 그 수가 동시에 소수이기도 한 경우를 말합니다.예를 들어 N이 13이라면, 13 이상의 수 중에서 가장 작은 소수 회문은 101입니다. 13 자체는 회문이 아니고, 그 다음 회문들인 22, 33 등은 소수가 아니기 때문입니다.해결 접근 방법이 문제는 다음과 같은 단계로 해결할 수 있습니다.만약 N이 8 이상 11 이하라면, 바로 11을

양의 정수 N이 주어졌을 때, 각 자릿수를 임의의 순서로 재배열(원래 순서 포함)하여 새로운 수를 만들려고 합니다. 단, 맨 앞자리 숫자는 0이 아니어야 한다는 조건이 있습니다. 이렇게 만든 수가 2의 거듭제곱이 될 수 있는지 판별하는 것이 이 문제의 목표입니다. 예를 들어 N이 46이라면 자릿수를 뒤집어 64(= 2⁶)를 만들 수 있으므로 답은 true입니다.접근 방법핵심 아이디어는 자릿수 구성(signature) 비교입니다. 두 수가 같은 숫자들을 같은 개수만큼 포함하고 있다면, 서로 자릿수를 재배열한 관계임을 알 수 있습니다.

문제 개요수열 X₁, X₂, ..., Xn이 다음 조건을 모두 만족할 때, 이를 피보나치 유사(fibonacci-like) 수열이라고 정의합니다.n ≥ 3i + 2 ≤ n인 모든 i에 대해 Xi + Xi+1 = Xi+2양의 정수로 구성되어 있고 값이 엄격하게 증가하는 배열 A가 주어졌을 때, A에서 가장 긴 피보나치 유사 부분수열(subsequence)의 길이를 찾아야 합니다. 해당하는 부분수열이 존재하지 않으면 0을 반환합니다.예를 들어 입력이 [1, 2, 3, 4, 5, 6, 7, 8]이라면 결과는 5입니다. 이때 가장 긴 피보

N개의 바나나 더미가 있고, i번째 더미에는 piles[i]개의 바나나가 놓여 있습니다. 경비원들은 현재 자리를 비운 상태이며 H시간 후에 돌아올 예정입니다. 코코는 시간당 바나나를 먹는 속도 K를 직접 결정할 수 있습니다.매시간 코코는 한 개의 더미를 선택해 그 더미에서 K개의 바나나를 먹습니다. 만약 해당 더미에 남은 바나나가 K개보다 적다면, 남은 바나나를 모두 먹고 그 시간 동안에는 더 이상 다른 더미를 먹지 않습니다.코코는 되도록 천천히 먹고 싶어 하지만, 동시에 경비원이 돌아오기 전까지 모든 바나나를 먹어야 한다는 조건이