[스터디 노트] Week4_2일차 [unit19 ~ 34] - 알고리즘

1. 알고리즘_5 [unit 19 ~ 24]

---

📍 근삿값

• 특정 값(참값)에 가장 가까운 값을 근삿값이라고 한다.

import random
nums = random.sample(range(0, 50), 20)
print(f"nums : {nums}")

input_num = int(input("input num: "))
print(f"input num: {input_num}")

near_num = 0
min_num = 50

for n in nums:
    abs_num = abs(n - input_num)

    
    if abs_num < min_num:
        min_num = abs_num
        near_num = n
        
print(f"near_num: {near_num}")
>>>
nums : [15, 27, 0, 1, 32, 31, 6, 36, 35, 39, 37, 33, 4, 41, 24, 46, 21, 22, 13, 25]
input num: 11
input num: 11
near_num: 13

---

📍 평균

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

# 다음은 어떤 체조선수의 점수이다.평균을 구하고 순위를 정하는 알고리즘을 만들어보자.
score_list = [8.9, 7.6, 8.2, 9.1, 8.8, 8.1, 7.9, 9.4, 7.2, 8.7]
sum_score = 0
grade_score = {}
score_list.sort(reverse = True)

for idx, value in enumerate(score_list):
    grade_score[idx+1] = value
    sum_score += value

print(f"전체 평균: {sum_score}")

for num in grade_score:
    print(f"{num}위 -> {grade_score[num]}")
>>>
전체 평균: 83.9
1위 -> 9.4
2위 -> 9.1
3위 -> 8.9
4위 -> 8.8
5위 -> 8.7
6위 -> 8.2
7위 -> 8.1
8위 -> 7.9
9위 -> 7.6
10위 -> 7.2

---

📍 재귀

• 재귀 함수(recursive function)란 함수 내에서 자기 자신을 다시 호출하는 함수를 의미합니다.
• 재귀 함수는 일반적으로 문제를 더 작은 하위 문제(sub-problems)로 분해하고, 이 하위 문제를 해결함으로써 원래 문제를 해결하는 방식으로 작동합니다.
• 재귀 함수를 이해하고 설계하는 데는 두 가지 주요 요소가 있습니다.
  • 기본 케이스(base case)
  • 재귀 케이스(recursive case)

• 재귀 함수를 사용하면 복잡한 알고리즘을 간결하게 표현할 수 있지만, 잘못 사용하면 스택 오버플로우(stack overflow)와 같은 문제를 일으킬 수 있으므로 주의가 필요합니다.
• 따라서 재귀 함수를 사용할 때는 항상 기본 케이스가 존재하도록 하여 재귀가 끝날 수 있도록 해야 합니다

⚡️ 팩토리얼 함수는 재귀 함수를 사용하여 쉽게 구현할 수 있는 고전적인 예입니다.

• 팩토리얼 n!은  n * (n-1) * (n-2) * ... * 1  이며, 재귀적으로 정의할 수 있습니다.
• factorial(n - 1) 호출은 함수가 자기 자신을 호출하는 재귀적 부분입니다.
• n이 0이나 1이 되면 재귀 호출이 중지되고 1이 반환되는데, 이 부분이 기본 케이스입니다.

def star_print(n):
    
    if n == 0 :
        return 1
    
    else:
        print("*"*n)
        return star_print(n - 1)
    
star_print(10)
>>>
**********
*********
********
*******
******
*****
****
***
**
*

⚡️ 유클리드 호제법

• 유클리드 호제법의 기본 아이디어는 두 수 a, b (a > b)의 최대 공약수는 'a를 b로 나눈 나머지'와 'b'의 최대 공약수와 같다는 것입니다

def gcd(a, b):
    
    if b == 0:
        return a 
    else:
        return gcd(b, a % b)
        
print(gcd(96, 40))
>>>
8

---

2. 알고리즘_6 ~ 7 [unit 25 ~ 30]

---

📍 하노이의 탑

• 세 개의 기둥과 이 기둥 중 하나에 꿴 원반이 있다고 가정합니다. 이 원반들은 크기 순서대로 꿰어져 있으며 가장 큰 원반이 가장 아래에, 가장 작은 원반이 가장 위에 있습니다. 목표는 모든 원반을 다른 기둥으로 옮기는 것입니다. 그러나 원반을 옮길 때는 다음과 같은 규칙을 따라야 합니다.

 

⚡️ 문제 해결 방법

• 위의 각 단계 역시 재귀적으로 실행할 수 있습니다. 각 단계에서 원반의 개수가 1개인 경우는 기본 경우(base case)로, 해당 원반을 바로 목표 기둥으로 옮기면 됩니다

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"{n}블럭: {source}에서 {target}(으)로 이동!!")
    
    else:
        # 1. n-1개의 원반을 보조 기둥으로 옮깁니다.
        hanoi(n - 1, source, auxiliary, target)

        # 2. 남아있는 원반을 목표 기둥으로 옮깁니다.
        print(f"{n}블럭: {source}에서 {target}(으)로 이동!!")

        # 3. 보조 기둥에 있는 원반을 목표 기둥으로 옮깁니다.
        hanoi(n - 1, auxiliary, target, source)

# 3개의 원반을 사용하는 하노이의 탑 문제를 해결합니다.
'''
원반을 옮기는 순서가 출력됩니다. 
처음에는 3개의 원반이 'A' 기둥에 있고, 
최종적으로 모든 원반이 'C' 기둥으로 옮겨지는 과정을 보여줍니다.
'''
hanoi(3, 'A', 'C', 'B')
>>>
1블럭: A에서 C(으)로 이동!!
2블럭: A에서 B(으)로 이동!!
1블럭: C에서 B(으)로 이동!!
3블럭: A에서 C(으)로 이동!!
1블럭: B에서 A(으)로 이동!!
2블럭: B에서 C(으)로 이동!!
1블럭: A에서 C(으)로 이동!!

---

📍 병합 정렬

• 병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 전략을 사용하는 효율적인 정렬 알고리즘입니다.
• 병합 정렬은 원래 배열을 두 부분으로 분할하고 각 부분을 정렬한 다음 병합하는 과정을 반복하여 작동합니다.
• 이 알고리즘은 O(n log n)의 시간 복잡도를 가지며, 안정적인 정렐 알고리즘으로 알려져 있습니다.

⚡️ 병합 정렬의 주요 단계

import random

def merge_sort(array):
    # 재귀 종료 조건: 배열의 길이가 1 이하일 때
    if len(array) <= 1:
        return array

    # 분할
    mid = len(array) // 2
    left = merge_sort(array[:mid])  # 왼쪽 반을 재귀적으로 정렬
    right = merge_sort(array[mid:]) # 오른쪽 반을 재귀적으로 정렬

    # 정렬된 두 배열을 병합
    merged = []
    l = r = 0
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            merged.append(left[l])
            l += 1
        else:
            merged.append(right[r])
            r += 1

    # 남아있는 원소들을 결과 리스트에 추가
    merged.extend(left[l:])
    merged.extend(right[r:])
    return merged

num_r = random.sample(range(1, 11), 10)
print(num_r)
sorted_array = merge_sort(num_r)
print(sorted_array)
>>>
[8, 7, 1, 6, 4, 9, 2, 3, 5, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

---

📍 퀵 정렬

• 퀵 정렬(Quick Sort)은 효율적이면서도 간단한 분할 정복(divide and conquer) 정렬 알고리즘입니다.
• 이 알고리즘의 기본 아이디어는 배열의 한 요소를 선택합니다. (이를 '피벗'이라고 부릅니다)
• 퀵 정렬의 평균 시간 복잡도는 O(n log n) 입니다.
• 그러나 피벗 선택이 잘못되었을 때(예: 이미 정렬된 배열에서 맨 처음이나 맨 마지막 요소를 피벗으로 선택한 경우) 최악의 경우 시간 복잡도는 O(n^2)가 됩니다.

⚡️ 문제 해결 방법

def partition(array, low, high):
    pivot = array[high]
    i = low - 1
    for j in range(low, high):
        if array[j] < pivot:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[high] = array[high], array[i + 1]
    return i + 1

def quick_sort(array, low=0, high=None):
    if high is None:
        high = len(array) - 1
    if low < high:
        pi = partition(array, low, high)
        quick_sort(array, low, pi - 1)
        quick_sort(array, pi + 1, high)

# 테스트
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr)
print(arr)  # [1, 5, 7, 8, 9, 10]
>>>
[1, 5, 7, 8, 9, 10]

❗️ 주의

• 피벗 선택 전략에 따라 퀵 정렬의 성능이 크게 달라질 수 있습니다.
• 일반적으로 중간값을 피벗으로 선택하거나, 무작위로 피벗을 선택하는 전략이 효과적인 경우가 많습니다.
• 이런 전략을 사용하면 퀵 정렬의 평균적인 성능을 더욱 향상시킬 수 있습니다.