알고리즘 Basic -1-

1. 1 ~ N 의 합을 구하려면 반복 처리한다.
2. 수열의 값을 유지하려면 배열을 사용한다. - 피보나치 수열
3. 배열 데이터의 합을 계산하려면 더한 값을 저장할 변수를 준비한다.
4. 배열 안의 요소의 개수를 구하려면 카운터를 준비한다.
5. 배열 데이터의 평균 값은 반복 처리를 통해 합계와 개수를 구한 후 계산한다.
6. 배열 데이터의 최대 값을 구하려면 최대 값을 저장할 변수를 준비한다.
7. 배열 데이터의 최소 값을 구하려면 최소 값을 저장할 변수를 준비한다.
8. 배열 데이터에 등수를 매기려면 순위를 저장할 또 다른 배열을 준비한다.

arr = [21,14,30,45,1]
rank = [1] * 5
for i in range(len(arr)):
	for j in range(len(arr)):
    	if arr[i] < arr[j]:
        	rank[i] += 1

9. 시간의 크고 작음을 비교하려면 단위를 초 단위로 통일한다.
10. 시간차를 구할 때는 초 단위로 바꾸어 뺄셈하고, 다시 시간으로 바꾼다.
11. 두 변수의 값을 교환할 때는 임시 변수를 사용한다.
12. 두 수의 최대공약수는 유클리드 호제법으로 구한다.

    정수 X, Y 가 주어졌을 때 X 와 Y 의 최대공약수는 Y 와 X 를 Y 로 나눈 나머지 R 의 최대 공약수와 같다.

def euclidean(x, y):
    print(y)
    if y == 0:
        return x
    r = x % y
    return euclidean(y, r)

13. 정렬이란 대상을 특정한 규칙에 따라 정렬하는 것이다.
14. 빈 배열을 준비하고, 빈 배열의 인덱스와 일치하는 모든 데이터를 저장한 다음에 첫 번째 데이터부터 꺼내는 것이 버킷 정렬이다.

arr = [8, 2, 1, 5, 9, 7]
buckets = [-1 for i in range(max(arr)+1)]
sorted_arr = []

for i in range(len(arr)):
    val = arr[i]
    buckets[val] = val
    
for num in buckets:
    if num != -1:
        sorted_arr.append(num)

15. 아래 자릿수부터 윗 자릿수까지 버킷 정렬을 반복하는 것이 기수 정렬이다. 각 자릿수의 숫자 값을 기준으로 정렬한다.

import math

nums = [123, 602, 82, 777, 57, 510, 396, 196, 843, 138]

class RadixSort:
    def __init__(self):
        self.array= []
        
    # 최대 자리수 구하기
    def findMaxDigit(self, arr):
        maxNum = max(arr)
        return int(math.log10(maxNum)) + 1 if maxNum else 0
    
    # 해당 자릿수의 값 구하기 ex. 512의 첫 번째 자릿수는 2
    def getDigitNum(self, digit, num):
        return (num // (10 ** (digit - 1))) % 10
        
    def radixSort(self, arr):
        # nums 안에 있는 모든 숫자가 10진수라는 가정하에
        self.array = arr
        maxDigit = self.findMaxDigit(self.array)
        
        for i in range(maxDigit):
            buckets = [[] for i in range(10)]
            for j in range(len(self.array)):
                digitNum = self.getDigitNum(i+1, self.array[j])
                buckets[digitNum].append(self.array[j])
                
            self.unfoldArr(buckets)
        
    # 2차원 배열을 1차원 배열로
    def unfoldArr(self, arr):
        tempArr = sum(arr, [])
        self.array = tempArr

RadixSort().radixSort(nums)