0. Intro- 해당 게시글에서는 어떤 배열의 최솟값과 최댓값을 구할 수 있는 알고리즘을 구현하고자 한다.- 다른 알고리즘 게시글에 비해 난이도가 상당히 쉬우니까 가볍게 보고 가자. 1. minimum- 최솟값을 구하는 코드를 구현해보면 다음과 같다.def minimum(arr): min = arr[0] for i in arr[1:]: if min > i: min = i return min - 배열을 한번씩 전부 돌면서 최솟값을 갱신하는 알고리즘이다.- 시간복잡도는 O(N)이 된다. 2. maximum- 최댓값을 구하는 코드를 구현하면 다음과 같다.- 최솟값을 구하는 코드와 크게 다르지 않는다.def maximum(arr): max = arr[0] ..
알고리즘
1. Bucket Sort?- Bucket Sort는 데이터를 일정한 범위로 나눈 여러 버킷에 분배하고,- 각 버킷 내부에서 정려한 후 각 버킷을 합쳐서 전체 데이터를 정렬하는 알고리즘이다.- 마치 다음 그림과 같다. - 그림을 보면 알 수 있겠지만,- 데이터가 특정 범위 안에서 균등하게 분포된 경우 매우 효율적으로 작동한다.- 주로 0과 1사이의 실수나 버뮈가 제한된 정수를 정렬할 때 사용된다. 2. Bucket Sort의 알고리즘i) 버킷 분할:- 데이터를 특정 구간으로 나누어 각 구간을 '버킷'이라고 정의한다.- 이때 버킷의 개수는 데이터의 분포에 따라 적절히 설정하는 것이 중요하다. ex) 데이터가 0과 1사이의 실수라면 각 버킷은[0,0.1) , [0.1,0.2), ... , [0.9,1)로 설..
1. Radix Sort?- Radix Sort는 여러 개의 자리수를 가진 정수나 문자열 데이터를 정렬할 때 효과적인 정렬알고리즘.- 숫자를 비교하는 것이 아니라, 자리수를 기준으로 정렬을 수행하며, - 각 자리수의 값을 이용해 한 번에 하나의 자릿수씩 정렬을 반복해 최종적으로 정렬을 완료함.2. Radix Sort의 종류2.1. LSD(Least Significant Digit)- 가장 오른쪽 자리수(일의 자리)부터 왼쪽으로 이동하면서 정렬- 일반적으로 정수를 정렬할 때 많이 사용됨2.2. MSD(Most Significant Digit)- 가장 왼쪽 자리수부터 시작하여 오른쪽으로 이동하면서 정렬- 문자열이나 사전순으로 정렬할 때 주로 사용됨 3. Radix Sort의 알고리즘(LSD 기준)- Rad..
1. Counting Sort?- Counting Sort는 정수로 표현할 수 있는 데이터에 대해 효율적으로 작동하는 O(n) 정렬 알고리즘.- 정렬의 대상이 되는 데이터 값의 범위가 명확할 때 주로 사용.- Counting Sort는 비교 정렬 알고리즘이 아닌 분포 정렬 알고리즘이다. 2. Counting Sort 알고리즘i) 입력 배열과 범위 설정- 주어진 입력 배열이 A라고 하고, 배열의 길이를 n이라고 하자.- 데이터 값은 0 이상 k이하인 양수라고 가정해보자. (이때 k == max(A)) ii) 카운트 배열 초기화- C라는 배열을 만들고, 길이를 k+1로 설정 (또는 max(A) - min(A)로 설정)- C[i]는 입력 배열에서 값이 i인 요소가 몇 번 등장하는지 저장함- C의 초기값은 전..
