[데이터 취업 스쿨 스터디 노트] 알고리즘 5 - 7

 

---

 

근삿값

: 특정 값에 가장 가까운 값을 근삿값이라고 한다.

 

평균

: 여러 수나 양의 중간값을 갖는 수를 평균이라고 한다.

 

재귀 알고리즘

: 실행 과정에서 자기 자신을 호출하는 것

# 등차수열 재귀함수 구현

start = int(input('a1 입력: '))
difference = int(input('공차 입력: '))
end = int(input('n 입력: '))

def sequence(a, ing, e):
    print(f'{e}번째 항의 값: {a}')
    print(f'{e}번째 항까지의 값: {ing}')

    if e == end:
        return
    a += difference
    ing += a

    return sequence(a, ing, e + 1)

sequence(start, start, 1)

 

하노이의 탑

answer = []

def hanoi(N, start, to, via):
    if N == 1:
        answer.append([start, to])
    else:
        hanoi(N - 1, start, via, to)
        answer.append([start, to])
        hanoi(N - 1, via, to, start)
        return answer

def solution(N):
    return hanoi(N, 1, 3, 2)

 

병합정렬

: 자료구조를 분할하고 각각 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다.

result = [8, 1, 3, 5, 7, 2, 9, 6, 4]

def merge_sort(array):
    if len(array) < 2:
        return array

    n = len(array) // 2
    left = merge_sort(array[:n])
    right = merge_sort(array[n:])

    L = R = 0
    merge_array = []
    while len(left) > L and len(right) > R:
        if left[L] < right[R]:
            merge_array.append(left[L])
            L += 1
        else:
            merge_array.append(right[R])
            R += 1
    merge_array += left[L:]
    merge_array += right[R:]
    return merge_array

print("before: ", result)
result = merge_sort(result)
print("after:", result)

# before:  [8, 1, 3, 5, 7, 2, 9, 6, 4]
# after: [1, 2, 3, 4, 5, 6, 7, 8, 9]

 

퀵 정렬

: 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.

result = [8, 1, 3, 5, 7, 2, 9, 6, 4]

def quick_sort(array):
    if len(array) < 2:
        return array

    pivot = len(array) // 2
    front, back, pivot_arr = [], [], []
    for i in array:
        if i < array[pivot]:
            front.append(i)
        elif i > array[pivot]:
            back.append(i)
        else:
            pivot_arr.append(i)
    return quick_sort(front) + quick_sort(pivot_arr) + quick_sort(back)

print("before: ", result)
result = quick_sort(result)
print("after:", result)

# before:  [8, 1, 3, 5, 7, 2, 9, 6, 4]
# after: [1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

---

내일의 학습 목표

알고리즘 문풀 1 - 5