피보나치 수열은 다음과 같은 형태를 가지는 수열입니다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ……이 수열에서 n번째 항은 바로 앞의 두 항, 즉 (n-1)th 항과 (n-2)th 항의 합으로 정의됩니다.피보나치 수를 구하는 가장 직관적인 방법은 재귀(recursion)를 사용하는 것이지만, 재귀 방식은 같은 값을 여러 번 반복해서 계산하게 되어 항이 커질수록 실행 시간이 급격히 늘어나는 단점이 있습니다. 반면 동적 프로그래밍(Dynamic Programming)을 활용하면 이러한 비효율을 제거하고 훨씬 빠

기수 정렬(Radix Sort)은 비교 기반이 아닌 정렬 알고리즘입니다. 이 알고리즘은 정수 키를 대상으로, 같은 자릿수와 값을 공유하는 숫자들을 그룹으로 묶는 방식으로 동작합니다. 여기서 기수(radix)란 수 체계의 밑(base)을 의미하는데, 우리가 흔히 사용하는 10진법에서는 기수가 10입니다. 따라서 10진수를 정렬하려면 각 자릿값(0~9)을 담을 수 있는 10개의 위치 저장소가 필요합니다.기수 정렬의 시간 복잡도시간 복잡도: O(nk) — n은 데이터 개수, k는 최대 자릿수공간 복잡도: O(n+k)입력 − 정렬되지 않은

버킷 정렬(Bucket Sort)은 데이터 항목들을 여러 개의 버킷에 나누어 담은 뒤, 각 버킷을 개별적으로 정렬하고, 마지막에 모든 요소를 다시 하나의 리스트로 모아 정렬된 결과를 얻는 기법입니다. 각 버킷에는 서로 비슷한 범위의 데이터가 담기며, 버킷 내부의 정렬에는 삽입 정렬이나 C++의 std::sort 같은 다른 정렬 알고리즘이 활용됩니다. 이 예제에서는 입력값이 0 이상 1 미만의 실수라고 가정합니다. 각 요소는 size * array[i]를 계산하여 버킷의 인덱스를 결정하므로, 값이 클수록 더 뒤쪽 버킷에 배치됩니다.

버블 정렬(Bubble Sort)은 비교 기반 정렬 알고리즘입니다. 인접한 두 요소를 서로 비교하고, 순서가 올바르지 않으면 교환(swap)하며 올바른 순서로 배열을 만들어 갑니다. 버블 정렬은 다른 정렬 알고리즘에 비해 구현이 매우 간단하지만 몇 가지 단점도 존재합니다. 특히 대량의 데이터 집합에는 적합하지 않으며, 정렬 작업을 완료하는 데 상당한 시간이 소요될 수 있습니다.버블 정렬의 동작 원리버블 정렬은 리스트를 처음부터 끝까지 훑으면서 인접한 두 요소를 비교합니다. 앞의 요소가 뒤의 요소보다 크면 두 요소의 위치를 바꿉니다.

힙(Heap)은 완전 이진 트리(Complete Binary Tree)의 한 형태로, 최소 힙(Min Heap)과 최대 힙(Max Heap) 두 종류가 있습니다.최대 힙(Max Heap)에서는 루트 노드의 키 값이 힙에 존재하는 모든 키 중에서 가장 커야 하며, 이 성질이 이진 트리의 모든 노드에 대해 재귀적으로 만족되어야 합니다. 반대로 최소 힙(Min Heap)은 루트 노드가 항상 트리 내의 최솟값을 갖는 자료구조입니다.주요 함수 설명void BHeap::Insert(int ele): 힙에 새로운 요소를 삽입하는 연산을 수행합니

병합 정렬(Merge Sort)이란? 병합 정렬은 분할 정복(Divide and Conquer) 기법에 기반한 대표적인 정렬 알고리즘입니다. 전체 데이터 집합을 더 작은 단위로 나누고(분할), 각 부분을 정렬한 뒤(정복), 정렬된 순서대로 다시 합쳐서(결합) 하나의 정렬된 배열을 만드는 방식으로 동작합니다. 병합 정렬의 가장 큰 장점은 최악의 경우에도 O(n log n)의 시간 복잡도를 보장한다는 점입니다. 따라서 데이터가 이미 역순으로 정렬되어 있는 등 불리한 상황에서도 퀵 정렬보다 안정적인 성능을 발휘합니다. 병합 정렬의 복잡도

선택 정렬(Selection Sort)이란?선택 정렬은 리스트를 두 부분으로 나누어 처리하는 정렬 기법입니다. 한쪽 부분에는 이미 정렬된 요소들이, 다른 쪽 부분에는 아직 정렬되지 않은 요소들이 위치합니다.먼저 배열에서 최댓값 또는 최솟값을 찾습니다. 예를 들어 최솟값을 찾았다면, 그 값을 리스트의 맨 앞에 있는 데이터와 교환하여 시작 위치에 배치합니다. 이 과정이 반복될수록 정렬해야 할 범위가 점점 줄어들며, 마지막에는 전체 배열이 오름차순으로 정렬됩니다.동작 과정 요약정렬되지 않은 영역에서 최솟값의 인덱스를 찾습니다.찾은 최솟값

삽입 정렬(Insertion Sort)은 흔히 카드를 정리하는 방식과 매우 유사한 정렬 기법입니다. 실제로 우리가 손에 든 카드를 오름차순으로 정렬할 때 사용하는 원리가 바로 삽입 정렬입니다. 이 기법에서는 데이터 집합에서 하나의 요소를 선택한 뒤, 그 요소가 들어갈 올바른 위치를 만들기 위해 앞쪽의 데이터 요소들을 한 칸씩 뒤로 밀어내고, 선택한 요소를 적절한 자리에 다시 삽입하는 방식으로 동작합니다.삽입 정렬 기법의 복잡도시간 복잡도: 최선의 경우 O(n), 평균 및 최악의 경우 O(n²)공간 복잡도: O(1)삽입 정렬은 이미

쉘 정렬(Shell Sort)은 삽입 정렬(Insertion Sort)을 기반으로 한 정렬 기법입니다. 일반적인 삽입 정렬에서는 요소를 올바른 위치에 삽입하기 위해 대량의 데이터를 한꺼번에 이동(shift)해야 하는 경우가 발생하는데, 쉘 정렬을 사용하면 이러한 과도한 이동 작업을 크게 줄일 수 있습니다.쉘 정렬은 특정 간격(gap)을 두고 요소들을 비교하며 정렬을 수행하고, 매 패스(pass)가 끝날 때마다 간격을 점차 줄여가며 최종적으로 간격이 1이 되면 완전히 정렬된 배열을 얻습니다. 이렇게 넓은 간격부터 시작해 점차 좁혀가는

카운팅 정렬(Counting Sort)은 안정 정렬(stable sort) 방식의 정렬 기법으로, 키 값이 작은 숫자 범위에 속하는 데이터를 정렬할 때 주로 사용됩니다. 이 알고리즘은 같은 키 값을 가진 데이터의 개수를 직접 세어(count) 그 정보를 활용해 정렬된 결과를 만들어냅니다. 정렬 대상 키 값들 사이의 차이가 크지 않을 때 매우 효율적으로 동작하지만, 키의 범위가 지나치게 넓으면 카운트 배열로 인해 공간 복잡도가 크게 늘어날 수 있다는 점에 유의해야 합니다.카운팅 정렬의 작동 원리배열에서 최대값을 찾고, 그 크기(max

이진 탐색(binary search)은 탐색 범위를 항상 절반씩 균등하게 나누며 진행합니다. 반면 보간 검색(interpolation search)은 보간 공식을 활용해 찾고자 하는 값이 있을 만한 위치를 직접 추정합니다. 추정한 위치를 기준으로 리스트를 다시 나누어 탐색 범위를 좁혀 나가기 때문에, 매 단계마다 실제 위치에 가장 가까운 곳을 찾으려 시도하게 되고 그만큼 탐색 시간이 크게 단축됩니다. 특히 데이터가 균등하게 분포(uniformly distributed)되어 있을 때 이 기법은 매우 빠르게 원하는 항목을 찾아냅니다.

그래프의 연결성을 확인하려면 임의의 그래프 순회 알고리즘을 이용해 모든 노드를 방문할 수 있는지 검사해야 합니다. 순회가 완료된 후에도 한 번도 방문되지 않은 노드가 남아 있다면, 그 그래프는 연결되어 있지 않은 것으로 판단합니다. 방향 그래프(directed graph)의 경우에는 상황이 조금 더 복잡합니다. 어떤 간선은 바깥쪽으로만 향하고 안쪽으로 들어오는 간선이 없을 수 있기 때문에, 다른 노드를 시작점으로 삼으면 도달할 수 없는 노드가 발생할 수 있습니다. 따라서 방향 그래프의 연결성을 제대로 확인하려면 모든 노드를 시작점

강연결 성분(Strongly Connected Components)이란? 방향 그래프(directed graph)에서 한 컴포넌트에 속한 모든 정점 쌍 사이에 서로 도달할 수 있는 경로가 존재할 때, 그 컴포넌트를 강연결 성분(Strongly Connected Component, SCC)이라고 합니다. 이 문제는 대표적으로 코사라주(Kosaraju) 알고리즘으로 해결할 수 있으며, 절차는 다음과 같습니다. DFS(깊이 우선 탐색)를 수행하여 각 정점의 종료 시간(finish time)을 스택에 기록합니다. 주어진 그래프의 모든

오일러 경로(Euler Path)란 그래프의 모든 간선을 정확히 한 번씩만 지나가는 경로를 의미합니다. 이때 정점(vertex)은 여러 번 반복해서 방문해도 무방합니다. 오일러 회로(Euler Circuit)는 오일러 경로의 특수한 형태로, 경로의 시작 정점과 마지막 정점이 서로 연결되어 있어 출발점으로 다시 돌아올 수 있는 경우를 말합니다.유향 그래프(directed graph)가 오일러 회로를 가지는지 판단하려면 아래 두 가지 조건을 모두 만족해야 합니다.그래프가 연결 그래프(connected graph)여야 합니다.모든 정점에

이번 글에서는 흥미로운 트릭 문제를 다뤄보겠습니다. 바로 세미콜론(;)을 단 한 번도 사용하지 않고 1부터 N까지의 숫자를 출력하는 방법입니다.이 문제는 크게 두 가지 방식으로 해결할 수 있습니다. 첫 번째는 반복문(iteration)을 이용하는 방법이고, 두 번째는 재귀 호출(recursion)을 이용하는 방법입니다.방법 1: 반복문 활용C언어에서 printf() 함수는 출력한 문자열의 길이를 반환합니다. 숫자를 하나 출력하면 반환값은 0이 아니므로 참(true)으로 평가됩니다. 이 성질을 이용해 조건과 논리 AND(&&a

선형 합동 생성기란?선형 합동 생성기(Linear Congruential Generator, LCG)는 난수 생성기의 가장 단순한 형태 중 하나로, 역사가 가장 오래되고 가장 널리 알려진 의사 난수 생성 알고리즘이기도 합니다. 이 방법에서 사용되는 함수는 다음과 같습니다.Xn+1 = (aXn + c) mod m여기서 X는 의사 난수 값의 수열을 의미하며, 아래와 같은 정수 상수들이 생성기의 동작을 결정합니다.m, 0 < m — 모듈러스(modulus) a, 0 < a < m — 승수(multiplier) c, 0 ≤

이 글에서는 여러 개의 문장을 작성하지 않고도 숫자의 자릿수 합을 구하는 방법을 알아봅니다. 다시 말해, 단 하나의 문장만으로 자릿수의 합을 계산하는 것이 목표입니다.자릿수의 합을 구하는 기본 원리는 다음과 같습니다. 숫자를 10으로 나눈 나머지를 이용해 마지막 자릿수를 추출하고, 그다음 숫자를 다시 10으로 나누는 과정을 반복하여 숫자가 0이 될 때까지 진행하면 전체 자릿수의 합을 얻을 수 있습니다.이러한 작업을 단일 문장으로 처리하려면 for 루프를 활용할 수 있습니다. for 루프는 세 개의 영역으로 구성되어 있는데, 이 예제

중간제곱법(Middle-Square Method)이란? 중간제곱법은 난수를 생성하는 가장 단순한 방법 중 하나로, 존 폰 노이만(John von Neumann)이 1949년경 제안한 기법입니다. 동작 원리는 매우 간단합니다. 초기값(시드)을 제곱한 뒤 그 결과에서 가운데 자릿수들을 추출해 다음 난수로 삼고, 이 과정을 반복하여 난수열을 만들어냅니다. 다만 이 방법에는 분명한 한계가 있습니다. 어느 순간부터 같은 숫자를 반복해서 출력하거나, 이미 등장했던 수열로 되돌아가 무한히 순환할 수 있습니다. n자리 난수 생성기의 주기는 최대

확률 밀도 함수(Probability Density Function, PDF)는 연속 확률 변수가 특정 값을 가질 상대적인 가능성을 나타내는 함수입니다. 흔히 연속 확률 변수의 밀도라고도 불립니다.확률 변수가 특정 범위의 값 안에 속할 확률은 해당 범위에 대한 밀도 함수의 적분값으로 계산됩니다. 즉, 이는 밀도 함수 아래 영역 중 수평축 위쪽 부분이면서 범위의 최솟값과 최댓값 사이에 해당하는 면적을 의미합니다. 확률 분포는 바로 이 확률 밀도 함수를 기반으로 정의됩니다.알고리즘시작 n을 선언한다 pdf = 0으로 초기화한다

Park-Miller 난수 생성 알고리즘은 난수를 생성하는 대표적인 방법 중 하나로, 선형 합동 생성기(Linear Congruential Generator) 계열에 속하는 기법입니다. 이 글에서는 Park-Miller 알고리즘의 기본 원리와 수식, 그리고 C++ 구현 예제까지 단계별로 살펴보겠습니다.Park-Miller 알고리즘의 기본 수식이 유형의 난수 생성기(RNG)는 다음과 같은 일반적인 수식으로 표현됩니다.X_{k+1} = g × X(k) mod n여기서 각 변수의 조건은 다음과 같습니다.n(모듈러스): 소수(prime n