하드러너 블레이크 (Hard-Learner Blake)

제로베이스 데이터 취업 스쿨 과정 학습 내용을 정리한 포스팅입니다.

📍 근삿값

특정 값과 가장 근사한 값을 배열에서 찾기

inputNum = 17
minNum = 30

num = [25, 15, 20, 10, 30]

for n in nums:
     absNum = abs(n-inputNum)
     
     if absNum < minNum:
         minNum = absNum
         nearNum = n
         
print(nearNum) # 15

- 특정값과 차이가 가장 작은 값이 근삿값이 된다(abs(n-inputNum))

- 배열을 돌면서 차이가 가장 작은 값이 나올 때, nearNum으로 저장한다.

📍 재귀

return 값으로 자신 함수를 다시 호출하는 것

def factorial(num):
    if num > 0:
        return num * factorial(num-1)
    else:
        return 1
        
        
print(factorial(10)) # 3628800

- factorial(팩토리얼)은 수를 1씩 빼면서 모두 곱하는 함수이다.

- 반복문을 사용하지 않고 바로 num-1한 값을 내 자신 함수에 넣어서 재귀적으로 호출한다.

📍 병합정렬

자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하는 정렬 방법

def mSort(nums):
    if len(nums) < 2:
        return nums

    mid_idx = len(nums) // 2
    left_nums = mSort(nums[0:mid_idx])
    right_nums = mSort(nums[mid_idx:len(nums)])

    mergedNums = []
    left_idx = 0; right_idx = 0
    while left_idx < len(left_nums) and right_idx < len(right_nums):
        if left_nums[left_idx] < right_nums[right_idx]:
            mergedNums.append(left_nums[left_idx])
            left_idx += 1
        else:
            mergedNums.append(right_nums[right_idx])
            right_idx += 1

    mergedNums = mergedNums + left_nums[left_idx:]
    mergedNums = mergedNums + right_nums[right_idx:]
    print(f'mergedNums: {mergedNums}')
    return mergedNums


nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(f'mergedNums: {mSort(nums)}') # 1, 2, 3, 4, 5, 6, 8, 10

- 좌우를 나눠서 서로 값을 비교하고, 더 작은 값을 병합해나간다.

- 좌우를 나눌 때마다 한쪽이 또 같은 함수를 적용하게 되기 때문에 재귀로 해결한다.

📍 퀵 정렬

기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합치는 정렬 방법

def qSort(nums):

    if len(nums) < 2:
        return nums

    mid_idx = len(nums) // 2
    mid_val = nums[mid_idx]

    small_nums = []
    same_nums = []
    big_nums = []


    for n in nums:
        if n < mid_val:
            small_nums.append(n)
        elif n == mid_val:
            same_nums.append(n)
        else:
            big_nums.append(n)

    return qSort(small_nums) + same_nums + qSort(big_nums)


nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(qSort(nums)) # 1, 2, 3, 4, 4, 6, 8, 8, 10

- 기준을 정하면 좌우가 아닌 크고 작은 값으로 같은 함수를 적용해야 할 대상이 정해진다.

- 기준보다 작은 쪽에 있는 수들에 같은 함수를 재귀적으로 적용하고, 기준보다 큰 쪽에 있는 수들에 같은 함수를 재귀적으로 적용해 마지막에 합쳐 준다.