이번 글에서는 흥미로운 알고리즘 문제를 하나 살펴보겠습니다. N개의 요소를 가진 배열 a가 주어졌을 때, |a[0] - x| + |a[1] - x| + ... + |a[n-1] - x| 의 값을 최소화하는 요소 x를 찾고, 그 최소화된 합계를 구하는 것이 목표입니다.예를 들어 배열이 {1, 3, 9, 6, 3}이라면 x는 3이 됩니다. 이때 합계는 다음과 같이 계산됩니다.|1 - 3| + |3 - 3| + |9 - 3| + |6 - 3| + |3 - 3| = 11이 문제의 핵심은 배열의 중앙값(median)을 x로 선택하는 것입니다

이번 글에서는 배열 관련 문제 하나를 살펴보겠습니다. 주어진 배열에서 빈도가 2회 이상인 요소를 모두 찾아 출력하는 것이 과제입니다.예를 들어 배열이 {1, 5, 2, 5, 3, 1, 5, 2, 7}이라고 가정해 봅시다. 이 배열에서 1은 2번, 5는 3번, 2는 3번 등장하고, 나머지 요소(3, 7)는 각각 1번만 나타납니다. 따라서 결과로 출력되어야 할 값은 {1, 5, 2}입니다.알고리즘moreFreq(arr, n)Begin key와 value가 모두 int 타입인 map을 정의한다 arr의 각 요소 e에 대해

배열이 하나 주어졌을 때, 그중 소수(Prime Number)번 만큼 등장하는 요소가 몇 개인지 세는 문제를 살펴보겠습니다.예를 들어 배열이 {1, 2, 2, 0, 1, 5, 2, 5, 0, 0, 1, 1}이라고 가정해 봅시다. 각 숫자의 등장 횟수는 다음과 같습니다.1은 4번 등장2는 3번 등장0은 3번 등장5는 2번 등장여기서 등장 횟수가 소수인 요소는 3번 등장한 2와 0, 그리고 2번 등장한 5로 총 3개입니다. 따라서 정답은 3이 됩니다. 참고로 4는 소수가 아니므로 1은 제외됩니다.알고리즘countPrimeOccurren

이번 글에서는 흥미로운 문제 하나를 살펴보겠습니다. 배열을 하나 입력받은 뒤, 각 요소를 바로 앞에 있는 요소로 나눈 값을 모두 더해 최종 합계를 구하는 것입니다.예를 들어 배열이 {5, 6, 7, 2, 1, 4}라고 가정해 보겠습니다. 이때 계산 과정은 다음과 같습니다.5 + (6 / 5) + (7 / 6) + (2 / 7) + (1 / 2) + (4 / 1) = 12.15238첫 번째 요소인 5는 나눌 이전 요소가 없기 때문에 그대로 더해집니다. 그럼 개념을 확실히 이해할 수 있도록 알고리즘부터 살펴보겠습니다.알고리즘divSum

이번 글에서는 흥미로운 알고리즘 문제 하나를 살펴보겠습니다. N개의 원소로 이루어진 집합이 주어졌을 때, 생성된 배열의 임의의 부분 집합에 대한 GCD(최대공약수)가 항상 주어진 원소 집합 안에 존재하도록 배열을 만들어야 합니다. 추가 제약 조건으로, 생성된 배열의 길이는 GCD 집합 길이의 3배를 초과하지 않아야 합니다.예를 들어, {2, 4, 6, 12}라는 4개의 숫자가 주어진 경우, 조건을 만족하는 배열 중 하나는 다음과 같습니다.{2, 2, 4, 2, 6, 2, 12}문제 해결 접근 방식이 문제를 풀려면 먼저 리스트를 오름

문제 개요이 글에서는 반원에 내접하는 정사각형 안에 그릴 수 있는 가장 큰 륄로(Reuleaux) 삼각형의 넓이를 구하는 방법을 알아봅니다. 륄로 삼각형은 세 개의 원호로 이루어진 곡선으로, 어느 방향으로 측정하든 폭이 일정하게 유지되는 특수한 도형입니다.편의를 위해 다음과 같이 기호를 정의합니다.반원의 반지름: R정사각형의 한 변의 길이: a륄로 삼각형의 높이: h넓이 공식 유도하기먼저, 반지름이 R인 반원에 내접하는 정사각형의 한 변의 길이는 다음과 같습니다.a = 2R / √5정사각형 안에 내접하는 륄로 삼각형의 높이는 정사각

문제 개요이 글에서는 정삼각형에 내접한 정사각형 내부에 그릴 수 있는 가장 큰 르로 삼각형(Reuleaux Triangle)의 넓이를 구하는 방법을 알아봅니다.르로 삼각형은 세 개의 원호로 이루어진 곡선 삼각형으로, 어느 방향으로 재더라도 폭이 항상 일정한 성질을 가진 대표적인 등폭 곡선입니다. 이러한 특성 때문에 정사각형 안에 가장 크게 배치할 때 르로 삼각형의 높이 h는 정사각형의 한 변의 길이 x와 같아집니다.편의상 정삼각형의 한 변의 길이를 a, 정사각형의 한 변의 길이를 x, 르로 삼각형의 높이를 h라고 정의합니다.x 값

이 글에서는 정육각형(regular hexagon) 안에 내접하는 정사각형, 그리고 그 정사각형 안에 새겨지는 가장 큰 르로 삼각형(Reuleaux triangle)의 넓이를 구하는 방법을 알아봅니다.여기서 각 변수를 다음과 같이 정의합니다.정육각형의 한 변의 길이: a정사각형의 한 변의 길이: x르로 삼각형의 높이: h기하학적 관계와 공식 유도먼저, 한 변의 길이가 a인 정육각형 안에 내접하는 정사각형의 변의 길이 x는 다음 공식으로 구할 수 있습니다.x = 1.268a흥미로운 점은 르로 삼각형의 높이 h가 정사각형의 변의 길이

이 글에서는 하나의 타원 안에 내접하는 정사각형, 그리고 그 정사각형 안에 새겨질 수 있는 가장 큰 륄로(Reuleaux) 삼각형의 넓이를 구하는 방법을 살펴봅니다. 타원의 장축 길이는 2a, 단축 길이는 2b이며, 정사각형의 한 변의 길이를 x, 륄로 삼각형의 높이를 h라고 하겠습니다.륄로 삼각형이란?륄로 삼각형은 세 개의 원호로 이루어진 곡선 삼각형으로, 어느 방향으로 측정하더라도 폭이 항상 일정하게 유지되는 도형입니다. 이러한 성질 덕분에 맨홀 뚜껑, 와블 엔진 등 다양한 분야에서 활용되고 있습니다.장축이 2a, 단축이 2b인

이 글에서는 직각삼각형 내부에 내접하는 정사각형 안에 다시 내접하는 가장 큰 륄로 삼각형(Reuleaux Triangle)의 넓이를 구하는 방법을 알아보겠습니다.먼저 기하학적 관계를 정리해 보겠습니다. 정사각형의 한 변의 길이는 a이고, 륄로 삼각형의 높이는 x입니다. 외부 직각삼각형의 밑변은 b, 높이는 l, 빗변은 h라고 가정합니다.기하학적 접근 방법높이가 l이고 밑변이 b인 직각삼각형에 내접하는 정사각형의 한 변의 길이는 다음 공식으로 구할 수 있습니다.a = (l × b) / (l + b)여기서 중요한 점은 륄로 삼각형의 높

문제 소개이 글에서는 하나의 원 안에 내접한 정사각형, 그리고 그 정사각형 안에 새겨진 가장 큰 를로 삼각형(Reuleaux Triangle)의 넓이를 구하는 방법을 알아봅니다. 참고로 를로 삼각형은 세 개의 원호로 이루어진 등폭 곡선 도형으로, 어느 방향으로 측정하더라도 폭이 같다는 독특한 성질을 가지고 있습니다.정사각형의 한 변의 길이를 a, 원의 반지름을 r이라고 설정하겠습니다.수식 유도 과정정사각형이 원에 내접해 있을 때, 정사각형의 대각선은 원의 지름과 같다는 기하학적 성질을 이용할 수 있습니다. 이를 식으로 표현하면 다음

이번 글에서는 정사각형 안에 내접하는 가장 큰 르로(Reuleaux) 삼각형의 넓이를 구하는 방법을 알아보겠습니다. 정사각형의 한 변의 길이를 a, 르로 삼각형의 높이를 h라고 합시다.르로 삼각형은 정삼각형의 각 꼭짓점을 중심으로 하는 세 개의 원호로 이루어진 등폭 곡선 도형입니다. 정사각형 안에 가장 크게 배치될 때 르로 삼각형의 높이는 정사각형의 한 변과 같아지므로 a = h가 성립합니다.르로 삼각형의 넓이 공식르로 삼각형의 넓이는 다음 공식으로 계산할 수 있습니다.넓이 = ((π − √3) × a²) / 2여기서 π는 원주율(

이 글에서는 한 변의 길이가 a인 정삼각형 안에 내접할 수 있는 가장 큰 정사각형의 크기를 구하는 방법을 살펴봅니다. 정삼각형의 한 변을 a, 내접하는 정사각형의 한 변을 x라고 하겠습니다. 기하학적 접근 방법 가장 큰 정사각형은 정삼각형의 밑변 위에 정사각형의 한 변을 놓고, 나머지 두 꼭짓점이 삼각형의 두 변에 닿도록 배치했을 때 얻을 수 있습니다. 먼저 정삼각형의 높이 h는 다음과 같습니다. h = (√3 / 2) × a 정사각형 위쪽에 남는 작은 삼각형은 원래 정삼각형과 닮음 관계에 있습니다. 닮음비를 이용하면 다음 식이 성

이번 글에서는 이진 배열과 범위 토글(range toggle) 연산을 다루는 문제를 살펴보겠습니다. 길이가 n인 이진 배열이 있으며, 각 원소는 0 또는 1입니다. 처음에는 배열의 모든 원소가 0으로 초기화되어 있습니다.여기에 총 M개의 명령이 주어집니다. 각 명령은 시작 인덱스와 끝 인덱스를 포함하며, command(a, b)는 배열의 a번째 위치부터 b번째 위치까지의 모든 원소에 적용됩니다. 명령의 역할은 해당 범위 내 값들을 토글(toggle)하는 것입니다. 즉, 0은 1로, 1은 0으로 뒤집습니다.문제 자체는 단순하지만, 알

DFA란 무엇인가?DFA(Deterministic Finite Automata, 결정적 유한 오토마타)는 주어진 문자열을 수용하거나 거부하는 유한 상태 기계(Finite State Machine)입니다. 각 입력 심볼에 대해 현재 상태에서 다음 상태로의 전이가 하나로 결정되는 것이 DFA의 핵심 특징입니다.이번 글에서는 입력 알파벳 집합 {a, b}로 구성된 문자열 중, a로 시작하고 a로 끝나는 문자열을 수용하는 DFA를 설계하고 이를 C++ 코드로 구현해 보겠습니다.수용 및 거부 조건설계하려는 DFA가 판별하는 문자열의 유효 여

정사면체(Tetrahedron)는 삼각형을 밑면으로 하는 피라미드 형태의 입체 도형입니다. 즉, 밑면이 삼각형이고 각각의 측면 역시 삼각형으로 이루어져 있으며, 세 개의 삼각형 면이 한 꼭짓점에서 만나는 구조를 가집니다.정사면체의 겉넓이 공식한 변의 길이가 a인 정사면체의 겉넓이는 다음 공식으로 계산할 수 있습니다.겉넓이 = (√3) × a²이 공식은 정사면체를 구성하는 4개의 정삼각형 면의 넓이를 모두 더한 값입니다. 각 정삼각형의 넓이는 (√3/4)a²이므로, 이를 4개 합하면 (√3)a²가 됩니다.C언어 구현 예제아래 코드는

배열의 비토닉성(Bitonicity)은 배열 내 요소들의 증가·감소 추세를 하나의 수치로 표현한 값입니다. 인접한 두 요소를 비교할 때마다 값을 더하거나 빼는 간단한 규칙으로 계산할 수 있습니다.비토닉성의 정의비토닉성은 다음과 같은 규칙에 따라 정의됩니다.Bitonicity = 0 (초기값) i는 1부터 n-1까지 반복 arr[i] > arr[i-1] 이면 : Bitonicity = Bitonicity + 1 arr[i] < arr[i-1] 이면 : Bitonicity = Bitonicity - 1 arr[i] = arr

배낭(Knapsack)은 짐을 담는 가방을 뜻합니다. 배낭 문제는 각 물건의 가치를 기준으로 가방에 어떤 물건을 넣을지 결정하는 문제로, 그 목표는 가방에 담긴 물건들의 총 가치를 최대화하는 것입니다. 특히 0-1 배낭 문제(0-1 Knapsack Problem)에서는 물건을 통째로 넣거나 아예 버리는 두 가지 선택지만 가능하며, 물건의 일부만 잘라서 넣는 것은 허용되지 않습니다.예시 문제물건들의 가치 = {20, 25, 40} 물건들의 무게 = {25, 20, 30} 가방의 수용 가능한 무게(용량) = 50무게 조합 분석가방 용량

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 자료구조입니다. 두 자식 노드는 각각 왼쪽 자식(left child)과 오른쪽 자식(right child)라고 부릅니다.BST(이진 탐색 트리, Binary Search Tree)는 왼쪽 서브트리에는 루트보다 작은 값을 가진 노드들이, 오른쪽 서브트리에는 루트보다 큰 값을 가진 노드들이 위치하는 트리 구조입니다. 이러한 정렬 특성 덕분에 탐색·삽입·삭제 연산을 평균적으로 O(log n)의 시간 복잡도로 빠르게 처리할 수 있습니다.이진 트리가

수정된 님(Modified Nim) 게임은 배열을 활용한 대표적인 최적화 게임 중 하나로, 선공 플레이어와 양측의 최적 수 선택에 따라 최종 승자를 예측하는 문제입니다. 게임 로직 이 게임에는 여러 개의 숫자가 담긴 배열이 주어지며, 두 명의 플레이어(player1과 player2)가 번갈아 가며 게임을 진행합니다. 두 플레이어의 목표는 각자 제거해야 할 숫자를 배열에서 모두 없애는 것이며, 구체적인 규칙은 다음과 같습니다. player1(A) : 3으로 나누어 떨어지는 숫자를 제거합니다. player2(B) : 5로 나누어