이진 탐색(Binary Search) - 탐색 알고리즘

이진 탐색은 정렬된 배열에서 요소를 찾는 고전적인 알고리즘으로, 시간 복잡도가 O(log n)입니다. 각 반복마다 검색 범위를 절반으로 줄이기 때문에 정렬된 데이터셋에서 가장 효율적인 검색 방법 중 하나로 손꼽힙니다.이진 탐색 동작 원리전제 조건: 데이터셋은 오름차순 또는 내림차순으로 정렬되어 있어야 합니다.절차:목표 값을 중간 요소와 비교합니다.일치하면 검색이 완료됩니다.목표 값이 더 작으면 왼쪽 절반을 검색합니다.목표 값이 더 크면 오른쪽 절반을 검색합니다.목표 값을 찾거나 검색 공간이 비어질 때까지 반복합니다.자바 구현public class BinarySearch { public static int binarySearch(int[] arr, int target) { int left..

• format_list_bulleted 컴퓨터과학/알고리즘
• · 2025. 1. 21.
• textsms

정렬 알고리즘 (Sorting Algorithms) - 비둘기집 정렬 (Pigeonhole Sort)

Pigeonhole 정렬Pigeonhole 정렬은 특정 범위 내에 속하는 데이터를 정렬하는 데 유용한 알고리즘입니다. 주어진 데이터를 "비둘기집 원리"에 따라 분류하여 정렬합니다. 이 정렬 알고리즘은 데이터가 균일한 범위에 걸쳐 분포되어 있을 때 매우 효율적이며, 정수 기반 정렬에서 주로 사용됩니다.1. 알고리즘 특징범위 기반 정렬:데이터 값의 범위(min, max)를 기준으로 "비둘기집"이라는 버킷을 생성하여 데이터를 정렬합니다.비둘기집 원리:n개의 항목을 n개의 버킷에 배치하면 적어도 하나의 버킷에는 항목이 2개 이상 들어가게 된다는 수학적 원리를 기반으로 합니다.제약:데이터 범위가 작아야 효율적입니다.데이터가 정수 형태로 표현될 수 있어야 합니다.안정성:기본 구현은 안정적이지 않으나, 수정하여 안정..

• format_list_bulleted 컴퓨터과학/알고리즘
• · 2025. 1. 7.
• textsms

정렬 알고리즘 (Sorting Algorithms) - Comb 정렬 (Comb Sort)

Comb 정렬 (Comb Sort)Comb 정렬은 버블 정렬(Bubble Sort)의 개선된 버전으로, 기본적으로 인접한 요소 대신 서로 일정한 간격을 두고 요소를 비교하며 정렬을 진행합니다. 이 간격을 점차 줄여가며 정렬이 이루어집니다. Comb 정렬은 간격 기반의 비교와 삽입 정렬의 요소를 결합하여 성능을 개선한 정렬 방식입니다.1. 주요 특징간격 (Gap):배열 요소를 비교할 때 사용하는 간격입니다.초기값은 배열의 길이로 설정하며, 정렬 진행 중 점차 줄여 나갑니다.Shrinking Factor:간격을 줄이는 비율입니다. 일반적으로 1.3으로 설정합니다.이 비율은 알고리즘의 효율성에 영향을 줍니다.버블 정렬의 개선:인접한 두 요소만 비교하는 버블 정렬에 비해, Comb 정렬은 처음에 더 멀리 떨어진..

• format_list_bulleted 컴퓨터과학/알고리즘
• · 2025. 1. 7.
• textsms

정렬 알고리즘 (Sorting Algorithms) - 팀 정렬 (Tim Sort)

Tim Sort (팀 정렬)Tim Sort는 실질적으로 사용되는 정렬 알고리즘 중 하나로, Java의 Arrays.sort()와 Python의 sorted() 및 list.sort() 메소드의 기본 정렬 알고리즘으로 채택되었습니다. Merge Sort와 Insertion Sort의 아이디어를 결합하여 실세계 데이터를 빠르게 정렬하도록 설계되었습니다.1. 알고리즘 개요Run 분할:입력 배열을 "run"이라는 작은 부분 배열로 나눕니다. 각 run은 이미 정렬되어 있는 배열 조각이며, 이를 기준으로 정렬을 진행합니다.Run은 기본적으로 최소 길이 (minRun) 이상이어야 하며, 필요한 경우 Insertion Sort를 통해 정렬합니다.Merge 과정:나눠진 run들을 병합하며 정렬합니다. 병합은 Merge..

• format_list_bulleted 컴퓨터과학/알고리즘
• · 2025. 1. 7.
• textsms

정렬 알고리즘 (Sorting Algorithms) - 버킷 정렬 (Bucket Sort)

버킷 정렬 (Bucket Sort)버킷 정렬은 데이터를 여러 개의 그룹(버킷)으로 나눈 후, 각 버킷을 정렬하여 최종적으로 병합하는 정렬 알고리즘입니다. 주로 데이터가 균등하게 분포되어 있을 때 효율적으로 작동하며, 연속적인 값의 정렬에 적합합니다.1. 동작 원리버킷 생성: 정렬할 데이터 범위를 기준으로 여러 개의 버킷을 생성합니다.데이터 분배: 각 데이터를 해당 값에 적합한 버킷에 삽입합니다.버킷 정렬: 각 버킷 내부에서 정렬 알고리즘(보통 삽입 정렬 또는 퀵 정렬)을 사용해 정렬합니다.병합: 모든 버킷의 데이터를 순서대로 병합하여 최종적으로 정렬된 배열을 만듭니다.2. 특징시간 복잡도:평균: O(n + k) (여기서 kk는 버킷의 개수)최악: O(n^2) (모든 데이터가 한 버킷에 들어가는 경우)공간..

• format_list_bulleted 컴퓨터과학/알고리즘
• · 2025. 1. 7.
• textsms

정렬 알고리즘 (Sorting Algorithms) - 기수 정렬 (Radix Sort)

기수 정렬 (Radix Sort)기수 정렬은 비교 기반이 아닌 정렬 알고리즘으로, 숫자의 자릿수를 기준으로 가장 작은 자릿수부터 가장 큰 자릿수까지 정렬합니다. 정수 또는 고정된 길이의 문자열과 같은 데이터를 정렬하는 데 적합합니다.1. 동작 원리최대 자릿수 확인: 데이터 중 가장 큰 값의 자릿수를 확인합니다.자릿수별 정렬:가장 작은 자릿수(1의 자리)부터 시작해 각 자릿수를 기준으로 안정적인 정렬(예: 계수 정렬)을 수행합니다.이후 10의 자리, 100의 자리 등 큰 자릿수로 이동하며 정렬을 반복합니다.정렬 완료: 모든 자릿수를 기준으로 정렬이 끝나면 데이터는 정렬된 상태가 됩니다.2. 특징시간 복잡도:O(d x (n + k)), 여기서:d: 가장 큰 값의 자릿수n: 배열의 크기k: 자릿수의 범위 (일..

• format_list_bulleted 컴퓨터과학/알고리즘
• · 2025. 1. 7.
• textsms