그놈 정렬(Gnome Sort)이란?그놈 정렬은 삽입 정렬(Insertion Sort)과 유사한 정렬 알고리즘입니다. 다만, 각 원소를 올바른 위치로 이동시킬 때 인접한 원소끼리 반복적으로 교환(swap)하는 방식을 사용한다는 점에서 버블 정렬(Bubble Sort)과 비슷합니다. 알고리즘의 동작 방식이 화분을 하나씩 옮기며 정리하는 정원 난쟁이(garden gnome)의 움직임과 닮았다고 해서 이런 이름이 붙었습니다.Input: 53421 Output: 12345동작 원리그놈 정렬은 단순한 루프만으로 구현할 수 있으며, 로직은 다

두 개의 정수 X와 K가 주어집니다. 여기서 K는 자릿수를 의미합니다. 이 문제의 목표는 X로 나누어 떨어지는 가장 큰 K자리 수를 찾는 것입니다.입력: X = 30, K = 3 출력: 980문제 풀이 접근 방법30으로 나누어 떨어지는 가장 큰 세 자리 수는 980입니다.이 문제를 해결하는 핵심 아이디어는 다음과 같습니다.먼저 10을 K제곱한 값에서 1을 빼면 가장 큰 K자리 수를 구할 수 있습니다. 예를 들어 K가 3이라면 10³ − 1 = 999가 됩니다.그다음 이 최댓값에서 X로 나눈 나머지를 빼주면, X의 배수 중에서 해당

배열에서 인덱스 i부터 j까지의 요소 합계를 계산해야 하는 상황을 생각해 봅시다. 문제는 이러한 쿼리가 여러 번 반복해서 실행될 수 있다는 점입니다. 매번 반복문으로 구간을 순회하면 비효율적이기 때문에, 접두사 합(Prefix Sum) 배열을 활용하면 각 쿼리를 상수 시간에 처리할 수 있습니다.입력 및 출력 예시입력: arr[] = {5, 6, 3, 4, 1}, i = 1, j = 3 출력: 13동작 원리 설명인덱스 1부터 3까지의 요소는 6, 3, 4이므로 합계는 다음과 같습니다.6 + 3 + 4 = 13가장 단순한 방법은 i부터

버블 정렬(Bubble Sort)은 인접한 두 요소를 비교하여 순서가 잘못되어 있으면 서로 교환하는 방식으로 배열을 정렬하는 대표적인 알고리즘입니다. 일반적인 버블 정렬은 반복문을 사용하지만, 재귀 버블 정렬은 자기 자신을 다시 호출하는 재귀 함수를 활용한다는 점이 특징입니다. 재귀 버블 정렬의 동작 원리 재귀(자기 호출) 함수는 한 번의 호출에서 인접한 두 요소를 비교하고, 순서가 잘못되어 있으면 교환하는 작업을 수행합니다. 그런 다음 배열의 크기를 하나 줄여 스스로를 다시 호출하며, 이 과정이 배열 전체가 오름차순으로 정렬될 때

경쟁 프로그래밍(코딩 테스트)에서는 제한 시간 안에 문제를 해결해야 하기 때문에 코드를 빠르고 간결하게 작성하는 것이 매우 중요합니다. 이번 글에서는 반복되는 긴 코드를 줄여 생산성을 높이는 대표적인 기법인 typedef와 #define 매크로의 활용 방법을 예제와 함께 살펴보겠습니다.1. typedef로 타입 이름 축약하기경쟁 프로그래밍에서는 큰 정수를 다루기 위해 long long 타입을 자주 사용합니다. 하지만 이 타입 이름을 매번 길게 입력하는 것은 번거롭습니다. 아래 기본 코드를 확인해 보세요.기본 코드#include &l

C++ STL(표준 템플릿 라이브러리)에는 잘 알려지지 않았지만 알아두면 코딩 생산성을 크게 높일 수 있는 숨겨진 기능들이 많습니다. 이 글에서는 실전에서 바로 활용할 수 있는 대표적인 트릭들을 예제 코드와 함께 소개합니다.1. 중괄호({})로 pair 값 간편하게 초기화하기pair 객체에 값을 할당할 때 make_pair() 함수 대신 중괄호를 사용하면 코드를 더 간결하게 작성할 수 있습니다. 이 방법은 tuple에도 동일하게 적용됩니다.pair<int, int> my_pair = make_pair(10, 20); pa

C++에서는 배열(array)과 벡터(vector) 모두 여러 데이터를 순차적으로 저장할 수 있지만, 두 자료구조는 동작 방식과 사용 편의성에서 큰 차이를 보입니다. 이 글에서는 배열 대신 벡터를 사용할 때 얻을 수 있는 장점과 함께, 몇 가지 주의할 점까지 코드 예제와 함께 정리해 보겠습니다.1. 언어 구조 vs 템플릿 클래스벡터는 std::vector라는 템플릿 클래스로, C++에만 존재하는 고유 기능입니다.반면 배열은 C++뿐 아니라 C, Java 등 다양한 언어에 존재하는 언어 차원의 내장 구조(built-in constru

이번 글에서는 흥미로운 알고리즘 문제를 하나 살펴보겠습니다. 몇 개의 원소를 가진 배열과 하나의 목표 합(sum) 값이 주어졌을 때, 배열 안에서 세 원소를 골라 그 합이 목표 합과 일치하는 모든 고유한 삼중항(triplet)을 찾아내는 것이 과제입니다.예를 들어 배열이 {4, 8, 63, 21, 24, 3, 6, 1, 0}이고 목표 합 S = 18이라면, 조건을 만족하는 삼중항은 {4, 6, 8}입니다. 만약 조건을 만족하는 삼중항이 여러 개 존재한다면, 그 모두를 출력해야 합니다.알고리즘이 문제는 정렬 + 투 포인터(Two Po

이 글에서는 세 변의 길이가 주어진 임의의 삼각형에 대해 그 외접원(circumcircle)의 넓이를 구하는 방법을 알아봅니다. 삼각형의 각 변을 AB = a, BC = b, CA = c라고 하고, 외접원의 반지름을 r이라고 하겠습니다.외접원 반지름 계산 원리외접원의 반지름 r은 다음 과정을 통해 구할 수 있습니다.먼저 헤론의 공식(Herons formula)을 이용해 삼각형의 넓이를 구합니다. 세 변의 길이의 합을 2로 나눈 값을 s(반둘레)라 할 때, 삼각형의 넓이는 다음과 같습니다.삼각형의 넓이 = √(s × (s − a) ×

문제 개요 이번 글에서는 주어진 타원 안에 내접할 수 있는 가장 큰 정사각형의 넓이를 구하는 방법을 알아보겠습니다. 두 반축의 길이 a와 b로 표현되는 타원이 주어졌을 때, 그 안에 그릴 수 있는 정사각형 중 면적이 최대인 것의 크기를 수학적으로 유도한 뒤, 이를 C++ 코드로 구현해 보겠습니다. 수학적 접근 중심이 원점에 있고 반축의 길이가 각각 a, b인 타원의 방정식은 다음과 같습니다. x2/a2 + y2/b2 = 1 참고로 이 타원 전체의 넓이는 πab 입니다. 타원에 내접하는 정사각형은 원점을 기준으로 대칭이므로, 한 꼭

이번 글에서는 정육각형에 내접하는 가장 큰 삼각형의 넓이를 구하는 방법을 알아보겠습니다. 정육각형의 한 변의 길이를 a, 내접하는 삼각형의 한 변의 길이를 b라고 하겠습니다.정육각형의 마주 보는 세 꼭짓점을 이으면 가장 큰 정삼각형이 만들어집니다. 육각형의 각 변은 이 삼각형의 변을 두 부분으로 나누며, 그 사이에는 직각삼각형 두 개가 형성됩니다.수식 유도 과정피타고라스 정리를 적용하면 다음과 같은 관계식을 얻을 수 있습니다.(b/2)² + (a/2)² = a²이 식을 정리하면 삼각형의 한 변의 길이는 다음과 같습니다.b = √3

C++ STL 배열 알고리즘이란? C++11 표준이 도입되면서 STL(표준 템플릿 라이브러리)에는 컨테이너와 배열을 더욱 편리하게 다룰 수 있는 다양한 함수들이 추가되었습니다. 이 함수들은 대부분 <algorithm> 헤더 파일에 정의되어 있으며, 복잡한 반복문을 직접 작성하지 않고도 조건 검사, 요소 복사, 값 초기화 등을 간결하게 처리할 수 있습니다. 이 글에서는 실무에서 자주 활용되는 대표적인 배열 알고리즘 함수들을 예제 코드와 함께 하나씩 살펴보겠습니다. 1. all_of() – 모든 요소가 조건을 만족하는지 확

문제 소개 n개의 원소를 가진 배열이 하나 주어졌다고 가정해 봅시다. 우리가 찾아야 하는 것은 특정 인덱스로, 그 인덱스를 기준으로 왼쪽에 있는 짝수의 개수와 오른쪽에 있는 짝수의 개수가 같거나, 왼쪽에 있는 홀수의 개수와 오른쪽에 있는 홀수의 개수가 같은 지점입니다. 만약 조건을 만족하는 인덱스가 존재하지 않는다면 -1을 반환합니다. 예를 들어 배열이 {4, 3, 2, 1, 2, 4}라고 해보겠습니다. 이때 출력 결과는 2입니다. 인덱스 2의 원소는 2이며, 이 원소의 왼쪽에는 홀수가 하나(3), 오른쪽에도 홀수가 하나(1) 있

이 문제에서는 하나의 트리와 합계 S가 주어집니다. 우리가 해야 할 일은 나머지 모든 간선에 가중치를 할당하되, 가중치 기준으로 가장 긴 경로가 가능한 한 짧아지도록 만드는 것입니다. 단, 할당된 가중치의 총합은 반드시 S와 같아야 한다는 조건이 있습니다. 문제 해결 접근법 풀이 아이디어는 의외로 간단합니다. 결정적인 열쇠는 트리의 한 가지 성질, 즉 트리의 어떤 경로에도 리프 노드는 최대 2개까지만 포함될 수 있다는 사실입니다. 이 성질을 활용하면 다음과 같은 전략을 세울 수 있습니다. 리프 노드에 연결된 간선에만 가중치를

이진 탐색 트리(BST)에 새 노드를 삽입할 때는 일반적으로 재귀 방식을 사용하며, 각 서브트리의 루트 주소를 반환하는 형태로 구현합니다. 이번 글에서는 또 다른 접근 방식을 소개합니다. 바로 부모(parent) 포인터를 함께 유지하는 방법입니다. 부모 포인터는 특정 노드의 조상(ancestor)을 찾는 등 다양한 트리 연산에서 매우 유용하게 활용됩니다.핵심 아이디어는 왼쪽과 오른쪽 서브트리의 주소를 저장해 두었다가, 재귀 호출이 반환된 후 해당 포인터들의 부모 포인터를 설정하는 것입니다. 이렇게 하면 삽입 과정에서 모든 부모 포인

delete 연산자는 변수가 차지하고 있는 저장 공간을 해제(deallocate)하는 데 사용되는 연산자입니다.this 포인터는 비정적(non-static) 멤버 함수 내부에서만 접근할 수 있는 특수한 포인터로, 해당 멤버 함수를 호출한 객체의 주소를 가리킵니다. 쉽게 말해, this 포인터는 현재 객체 자신의 주소를 담고 있으며 클래스의 현재 객체를 가리킨다고 할 수 있습니다.객체를 통해 멤버 함수를 호출할 때마다 컴파일러는 내부적으로 호출된 객체의 주소를 멤버 함수의 첫 번째 매개변수로 암묵적으로 전달하며, 이것이 바로 this

C++ 프로그래밍에서 상수를 선언하는 방법은 여러 가지가 있습니다. 그중 대표적인 세 가지가 바로 static const, #define, enum입니다. 각 방식은 동작 원리와 용도가 다르기 때문에 상황에 맞게 선택하는 것이 중요합니다. 이 글에서는 세 가지 방식의 개념과 차이점을 예제 코드와 함께 자세히 살펴보겠습니다. "static const"란 무엇인가? static const는 저장 지정자(storage specifier)인 static과 타입 한정자(type qualifier)인 const의 조합입니다.

순환 정렬(Cycle Sort)은 제자리(in-place) 정렬이면서 불안정(unstable)한 비교 기반 정렬 알고리즘입니다. 다른 어떤 제자리 정렬 알고리즘과 달리, 원본 배열에 수행되는 쓰기(write) 연산의 총 횟수가 이론적으로 최적(optimal)이라는 점이 가장 큰 특징입니다.순환 정렬의 핵심 아이디어는 다음과 같습니다. 정렬해야 할 순열(permutation)은 여러 개의 사이클(cycle)로 분해할 수 있으며, 각 사이클을 개별적으로 회전시키면 정렬된 결과를 얻을 수 있습니다.순환 정렬의 핵심 특징거의 모든 다른 정

자연수란 무엇인가?양의 정수 1, 2, 3, 4, ... 와 같은 수들을 자연수(natural number)라고 부릅니다.이 프로그램은 사용자로부터 양의 정수 n을 하나 입력받은 뒤, 다음과 같은 처음 n개의 자연수 세제곱의 합을 계산하여 화면에 출력합니다.13 + 23 + 33 + ... + n3실행 결과 예시입력: n = 3출력: 36동작 원리 설명n이 3으로 주어진 경우, 프로그램은 1부터 3까지 각 자연수를 세제곱한 값들을 모두 더합니다.13 + 23 + 33 = 1 + 8 + 27 = 36따라서 최종 결과값인 36이 출력됩

주어진 숫자가 2의 거듭제곱인지 확인하는 프로그래밍 문제는 코딩 테스트와 알고리즘 학습에서 자주 등장하는 기본 문제입니다. 이 글에서는 C++을 활용해 숫자가 2의 거듭제곱인지 판별하는 여러 가지 방법을 소개합니다.2의 거듭제곱이란?2의 거듭제곱은 2를 여러 번 곱한 수를 의미합니다. 대표적인 예는 다음과 같습니다.2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 ...22 = 425 = 32210 = 1024판별 방법숫자가 2의 거듭제곱인지 확인하는 대표적인 방법은 두 가지가 있습니다.첫 번째 방