이 튜토리얼에서는 한 숫자의 세트 비트(set bits)를 주어진 범위 내에서 다른 숫자로 복사하는 프로그램을 구현해 보겠습니다. 두 개의 정수가 주어졌을 때, 첫 번째 숫자의 비트를 하나씩 살펴보고 해당 비트가 지정된 범위 안에 있다면 두 번째 숫자의 같은 위치 비트도 1로 설정해야 합니다. 최종적으로 수정된 숫자를 출력하는 것이 목표입니다. 문제 해결 접근 방법 비트 마스크(bit mask)를 활용하면 이 문제를 간단히 해결할 수 있습니다. 지정된 범위의 각 비트 위치마다 마스크를 생성하고, 원본 숫자(y)의 해당 비트가 1로

개요 이 글에서는 주어진 점들의 집합에 대해 볼록 껍질(Convex Hull)을 구하는 C++ 프로그램을 소개합니다. 볼록 껍질이란 주어진 모든 점을 경계선 위 또는 내부에 포함하는 가장 작은 볼록 다각형을 의미합니다. 컴퓨터 그래픽스, 지리 정보 시스템(GIS), 충돌 감지 등 다양한 분야에서 활용되는 기본적인 기하학 알고리즘입니다. 그레이엄 스캔 알고리즘의 동작 원리 그레이엄 스캔(Graham Scan)은 다음과 같은 단계로 진행됩니다. 기준점 선택: y 좌표가 가장 작은 점을 찾습니다. y 좌표가 같은 점이 여러 개라면 x

이 튜토리얼에서는 주어진 점들의 집합에 대한 볼록 껍질(Convex Hull)을 구하는 프로그램을 다룹니다.볼록 껍질이란, 주어진 모든 점들을 경계선 위 또는 내부에 포함하는 가장 작은 볼록 다각형을 의미합니다. 이를 효율적으로 계산하기 위해 널리 사용되는 방법이 바로 모노톤 체인(Monotone Chain) 알고리즘, 즉 Andrew의 알고리즘입니다.알고리즘의 핵심 아이디어모노톤 체인 알고리즘은 다음과 같은 순서로 동작합니다.1. 모든 점을 x좌표, 그다음 y좌표 기준으로 사전순(lexicographically) 정렬합니다.2.

이 튜토리얼에서는 분할 정복(Divide and Conquer) 기법을 활용해 주어진 점 집합의 볼록 껍질(Convex Hull)을 구하는 C++ 프로그램을 살펴봅니다.볼록 껍질이란?볼록 껍질은 주어진 모든 점을 경계선 위 또는 내부에 포함하는 가장 작은 볼록 다각형을 의미합니다. 마치 고무줄을 모든 못에 걸어 팽팽하게 당겼을 때 만들어지는 형태라고 생각하면 쉽게 이해할 수 있습니다.알고리즘 개요이 프로그램은 전체 점 집합을 작은 그룹으로 반복적으로 나누고(분할), 각 그룹에 대해 브루트 포스 방식으로 부분 볼록 껍질을 계산한 뒤,

이 튜토리얼에서는 주어진 좌표 점들이 모두 내부에 포함되는 사각형의 좌표를 구하는 프로그램을 다룹니다.여러 개의 좌표 점이 주어졌을 때, 우리가 해야 할 일은 모든 점을 내부에 포함하면서 변이 좌표축(X축, Y축)에 평행한 가장 작은 사각형을 찾는 것입니다.접근 방법핵심 아이디어는 매우 간단합니다. 사각형의 변이 좌표축에 평행해야 하므로, 다음 네 가지 값만 구하면 됩니다.X 좌표들 중 최솟값(Xmin)X 좌표들 중 최댓값(Xmax)Y 좌표들 중 최솟값(Ymin)Y 좌표들 중 최댓값(Ymax)이 네 값을 조합하면 사각형의 네 꼭짓점

개요이 글에서는 C++을 사용하여 초(second) 단위의 값을 일(day), 시간(hour), 분(minute), 초(second)로 변환하는 프로그램을 다룹니다.임의의 초 값이 주어졌을 때, 이를 며칠 몇 시간 몇 분 몇 초 형태로 변환하는 것이 목표입니다. 이러한 변환은 타이머, 스케줄러, 로그 처리 등 다양한 프로그래밍 상황에서 유용하게 활용됩니다.변환 원리변환은 나눗셈 연산자(/)와 나머지 연산자(%)를 활용하면 간단히 구현할 수 있습니다. 기본 단위는 다음과 같습니다.1일 = 24 × 3600 = 86,400초1시간 =

이 글에서는 자비스 알고리즘(Jarviss Algorithm)을 사용하여 주어진 점 집합의 볼록 껍질(Convex Hull)을 찾는 방법을 C++ 코드와 함께 살펴봅니다. 볼록 껍질(Convex Hull)이란? 볼록 껍질은 주어진 모든 점을 경계 위에 포함하거나 내부에 담을 수 있는 가장 작은 볼록 다각형을 의미합니다. 쉽게 비유하면, 평면 위에 여러 개의 못을 박고 고무줄을 팽팽하게 늘어뜨렸을 때 만들어지는 외곽 형태라고 생각하면 이해하기 쉽습니다. 자비스 알고리즘(선물 포장 알고리즘)의 동작 원리 자비스 알고리즘은 선물을 포장하

개요 이 튜토리얼에서는 1부터 3999 사이의 로마 숫자를 10진수(정수)로 변환하는 C++ 프로그램을 작성하는 방법을 살펴봅니다. 임의의 로마 숫자가 입력으로 주어졌을 때, 이를 해당하는 10진수 값으로 변환하는 것이 목표입니다. 로마 숫자 변환의 기본 원리 로마 숫자는 다음 일곱 가지 기호로 구성되며, 각 기호는 고유한 값을 가집니다. I = 1 V = 5 X = 10 L = 50 C = 100 D = 500 M = 1000 일반적으로 기호의 값을 왼쪽에서 오른쪽으로 더해가지만, 작은 값이 큰 값 앞에 위치하는 경우(예:

이 튜토리얼에서는 append(추가)와 delete(마지막 요소 삭제) 연산만을 사용하여 하나의 문자열을 다른 문자열로 변환할 수 있는지 판별하는 프로그램을 다룹니다.두 개의 문자열이 주어졌을 때, 우리의 목표는 정확히 k번의 추가 및 삭제 연산을 수행하여 첫 번째 문자열을 두 번째 문자열로 변환하는 것이 가능한지 계산하는 것입니다.문제 해결 접근 방식이 문제를 해결하려면 다음과 같은 논리를 적용합니다.먼저 두 문자열 길이의 합이 k보다 작은 경우를 확인합니다. 이 경우 남은 연산 횟수를 모두 소모하여 조건을 만족시킬 수 있으므로

이 튜토리얼에서는 최소한의 변경만으로 배열을 엄격하게 증가하는 정수 배열로 변환하는 프로그램을 살펴보겠습니다.정수 배열이 하나 주어지며, 우리의 과제는 배열의 원소를 가능한 한 적은 횟수만 변경하여 전체 배열이 엄격하게 증가하는 순서, 즉 각 원소가 바로 앞 원소보다 반드시 커지도록 만드는 것입니다.접근 방법이 문제는 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 알고리즘을 응용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.변경하지 않고 그대로 유지할 수 있는 원소들의

이 튜토리얼에서는 주어진 숫자의 모든 자릿수를 3과 8로만 이루어지도록 변환하는 프로그램을 C++로 구현해 보겠습니다.문제 개요임의의 숫자가 하나 주어집니다. 우리의 목표는 이 숫자의 각 자릿수를 3 또는 8로 만드는 것입니다. 이때 사용할 수 있는 연산은 두 가지입니다.숫자 전체에 1을 더하거나 빼기특정 자릿수를 원하는 숫자로 직접 변경하기여기서 구해야 할 값은 모든 자릿수를 3 또는 8로 만들기 위해 필요한 최소 연산 횟수입니다.접근 방법가장 효율적인 방법은 간단합니다. 숫자의 각 자릿수를 차례대로 검사하면서, 3이나 8이 아닌

이 튜토리얼에서는 1부터 3999 사이의 10진수를 로마 숫자(Roman Numerals)로 변환하는 프로그램을 C++로 구현하는 방법을 알아보겠습니다.프로그램은 임의의 정수를 입력받아, 해당 숫자에 대응하는 로마 숫자 문자열을 출력하는 것이 목표입니다. 예를 들어 3949가 입력되면 MMMCMXLIX를 출력해야 합니다.변환 원리로마 숫자는 기본 기호(I, V, X, L, C, D, M)와 이들을 조합한 형태(IV, IX, XL, XC, CD, CM 등)로 구성됩니다. 변환 알고리즘은 다음과 같이 동작합니다.값이 큰 단위(1000,

문제 개요주어진 문자열의 문자들을 재배열하여 모음과 자음이 번갈아 위치하도록 만드는 것이 이번 문제의 목표입니다. 단, 다음 조건을 반드시 지켜야 합니다.모음끼리의 상대적인 순서와 자음끼리의 상대적인 순서는 원래 문자열에서의 순서 그대로 유지해야 합니다.조건에 맞게 재배열하는 것이 불가능한 경우에는 no such string을 출력합니다.가능한 결과가 여러 개라면 그중 사전순으로 가장 작은 문자열을 출력합니다.예시입력 : Tutorial출력 : Tutorila입력 : onse출력 : nose두 번째 예시에서는 nose와 ones라는

문제 정의주어진 문자열에서 짝수 위치에 있는 모든 요소를 문자열의 끝으로 이동하는 것이 목표입니다. 이때 요소를 옮기는 과정에서 짝수 위치 요소들끼리, 그리고 홀수 위치 요소들끼리는 서로의 상대적인 순서가 유지되어야 합니다.예를 들어, 입력 문자열이 a1b2c3d4e5f6g7h8i9j1k2l3m4라면, 이를 제자리(in-place)에서 O(n) 시간 복잡도로 abcdefghijklm1234567891234 형태로 변환해야 합니다.알고리즘의 핵심 단계3^k + 1 형태의 가장 큰 접두사 부분 문자열 분리: 먼저 3^k + 1이 문자열

하나의 원에서 현(chord)과 접선(tangent)이 특정 점에서 만나고, 대체 세그먼트(alternate segment)의 각도가 주어져 있다고 가정해 봅시다. 이 문제의 핵심은 바로 현과 접선 사이의 각도를 구하는 것입니다.예시입력: z = 40출력: 40도입력: z = 60출력: 60도접근 방법각 QPR을 대체 세그먼트에서 주어진 각이라고 합니다.현과 접선 사이의 각을 각 RQY = a라고 둡니다.접선 위의 점에서 중심으로 그은 선은 접선에 수직이므로,각 CQR = 90° − a 입니다.CQ = CR = 원의 반지름이므로,각

구조체 대입과 배열 멤버의 복사 방식C/C++에서는 같은 타입의 구조체(struct) 변수를 다른 변수에 대입할 수 있습니다. 이때 구조체 변수를 대입하면 해당 변수의 모든 멤버가 다른 구조체 변수로 복사됩니다. 그렇다면 구조체 내부에 배열이 포함되어 있을 때는 어떻게 동작할까요?배열 멤버는 자동으로 깊은 복사된다여기서 중요한 핵심은 배열 멤버는 얕은 복사(shallow copy)가 아니라, 컴파일러가 자동으로 깊은 복사(deep copy)를 수행한다는 점입니다.아래 예제 프로그램의 구조체 test는 배열 멤버 str1[20]을 가

이 기법에서는 연결 리스트를 순회하면서 키 값이 모음인 노드는 앞쪽으로, 자음인 노드는 뒤쪽으로 이동시킵니다. 중요한 점은 이동 과정에서 각 노드들의 원래 상대적 순서가 그대로 유지된다는 것입니다(안정 정렬 방식).동작 예시입력: A-M-A-Z-O-N출력: A-A-O-M-Z-N시간 복잡도: O(N), 공간 복잡도: O(1)위 예시에서 A, A, O는 모음이므로 앞쪽으로 이동하고, M, Z, N은 자음이므로 뒤쪽으로 이동합니다. 각 그룹 내부에서는 입력 순서가 유지되는 것을 확인할 수 있습니다.알고리즘 설명구현 방식은 다음과 같습니다

정수 m과 위치 배열 position[](1 ≤ length(position[]) ≤ 2m)이 주어졌을 때, 길이가 2m인 올바른 괄호 표현식(proper bracket expression)을 만들 수 있는 경우의 수를 구하는 문제입니다. 단, 지정된 위치에는 반드시 여는 괄호가 와야 합니다.참고: position[] 배열은 1 기반 인덱싱 형태의 [0, 1, 1, 0]과 같이 제공됩니다. 값이 1인 위치에는 반드시 여는 괄호가 배치되어야 하며, 값이 0인 위치에는 여는 괄호 또는 닫는 괄호 중 어느 것이든 자유롭게 배치할 수 있습

빈 패킹(Bin Packing) 문제란 서로 다른 무게를 가진 m개의 원소와 각각 용량이 C인 빈(bin)들이 주어졌을 때, 모든 원소를 빈에 할당하면서 사용되는 빈의 총 개수를 최소화하는 문제입니다. 단, 모든 원소의 무게는 빈의 용량보다 작다는 조건을 전제로 합니다.빈 패킹 문제의 실제 응용 분야여러 디스크에 데이터 배치하기트럭 등 컨테이너 화물 적재라디오/TV 방송의 고정 광고 시간대에 광고 배치하기작업(Job) 스케줄링문제 예시입력: weight[] = {4, 1, 8, 1, 4, 2} 빈 용량 c = 10 출력: 2 모든

일반적인 숫자 배열(flat array)과 비교했을 때, 펜윅 트리(Fenwick Tree)는 요소 업데이트와 접두사 합(prefix sum) 계산이라는 두 연산 사이에서 훨씬 더 나은 균형을 제공합니다.m개의 숫자를 담고 있는 평면 배열의 경우, 요소 자체를 저장하거나 접두사 합을 저장하는 두 가지 방식 중 하나를 선택해야 합니다. 전자의 경우 접두사 합을 계산하는 데 선형 시간(O(m))이 소요되고, 후자의 경우 배열 요소를 수정·업데이트하는 데 선형 시간이 걸립니다. 물론 두 경우 모두 나머지 하나의 연산은 상수 시간에 수행할