알고리즘/자료구조

유클리드 호제법은 두 개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘입니다. 유클리드 호제법을 통해 최대공약수와 함께 최소공배수를 구할 수 있으며, 이를 활용하는 방법에 대해 정리하려고 합니다. 최대공약수(GCD) & 최소공배수(LCM) 유클리드 호제법을 말하기 전에 최대공약수와 최소공배수의 개념을 간단하게 설명해 보겠습니다. 최대공약수(GCD, Greatest Common Divisor) 두 개 이상의 수가 가지는 공통된 약수 중 가장 큰 수를 의미합니다. 예를 들어, 12와 18의 최대공약수는 6입니다. 12와 18의 공약수는 1, 2, 3, 6이며, 이 중 가장 약수가 6이기 때문입니다. 최소공배수(LCM, Least Common Multiple) 두..

우선순위 큐(Priority Queue)란? 우선순위 큐(Priority Queue)는 데이터를 저장하고 관리하는 자료구조 중 하나입니다. 일반적인 큐(Queue)와 유사하게 요소를 저장하는 방식으로 FIFO(First In First Out)의 구조를 가집니다. 그러나 우선순위 큐(Priority Queue)는 삽입된 순서로 요소를 처리하는 것이 아니라, 우선순위에 따라 정렬되어 우선순위가 높은 요소가 먼저 처리됩니다. 우선순위 큐(Priority Queue) 특징 요소들이 우선순위에 따라 정렬되어 저장된다. 즉 가장 높은 우선순위를 갖는 요소가 가장 먼저 처리된다. 내부 요소가 Heap으로 구성되어 이진트리 구조로 이루어져 있다. 빠른 삽입과 삭제 연산을 빠르게 수행할 수 있다. 시간 복잡도는 0(N..

피보나치 수열은 다양한 알고리즘에서 사용되며 재귀의 좋은 예시를 제공합니다. 해당 포스팅을 통해 피보나치의 수열을 이해하고 활용 방법에 대해 정리하려고 합니다. 피보나치 수열(Fibonacci numbers)이란? 이전 두 항의 합이 다음 항이 되는 수열을 의미합니다. 첫 번째와 두 번째 항이 1이고, 세 번째 항부터는 이전 두 항의 합으로 이루어지는 규칙을 따릅니다. 피보나치 수열의 첫 번째 항은 f(0), 두 번째 항을 f(1)으로 정의합니다. f(0) = 1 f(1) = 1 이때 n번 째 항은 (n - 1)번째 항 + (n - 2)번째 항입니다. f(n) = f(n-1) + f(n-2) 피보나치 수열의 첫 번째 항부터 순서대로 예시를 본다면 1, 1, 2, 3, 5, 8, 13, 21, 34, 55..