엘리스 AI 트랙 11주차 - 알고리즘의 정석 I (3/12) 🔥

✔ 11주차. 자료구조와 알고리즘

<학습 목표>

1. 개발 역량 강화를 위한 자료구조 및 알고리즘 문제를 수행할 수 있습니다.
2. 알고리즘 문제를 만났을 때 효율적으로 접근하는 방법을 알 수 있습니다.
3. 알고리즘 문제 해결 기법의 근본적인 이해를 할 수 있습니다.

---

[01 재귀호출]

1. 알고리즘이란?
  - 알고리즘 : algorithm. 문제를 해결하는 방법. 계산을 통하여 해결할 수 있는 문제를 해결하는 방법
  - 알고리즘의 5가지 성질 : 유한성, 명확성, 입력, 출력, 효과성
  - k번째 숫자 찾기
    - 해결방법 : 숫자 입력 받기 → 지금까지 받은 숫자들을 정렬 → k번째로 작은 숫자를 출력

def findKth(myInput, k) :
    result = []
    data = []
    for element in myInput:
        data.append(element)
        data.sort()
        # data[k-1] = 찾는 값
        if len(data) < k:
            result.append(-1)
        else:
            result.append(data[k-1])

    return result

2. 재귀호출
  - 재귀호출 : 함수가 자기자신을 호출함. 
  - 팩토리얼의 재귀적 정의 : n! = n * (n-1)!

3. 수학적 귀납법
  - 수학적 귀납법 : 모든 자연수가 어떤 주어진 성질을 만족시킨다는 명제를 증명하는 방법의 하나 (출처 : 위키백과)
  # 여기서요? 갑자기요? ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 진짜 나 왜 수포자냐...
  - 명제 P(n)을 증명하는 방법
    ① N = 1 일 때 성립함을 보인다.
    ② P(k)가 성립한다고 가정할 때, P(k+1)이 성립함을 보인다.
    ③ 따라서 모든 자연수 n에 대하여 P(n)이 성립한다.
  → 수학적 귀납법이란 명제를 재귀적으로 증명하는 방법임. 
  → 재귀적 증명법이란 하나의 명제를 증명하기 위해 그 증명에 똑같은 증명을 사용하는 것.

4. 퀵 정렬
  - 퀵 정렬 : Quick Sort, 재귀호출을 이용한 대표적인 정렬.

https://qnaplus.com/implement-quick-sort-c/

  - 퀵 정렬 구현하기

def quickSort(array):
    # 기저조건 처리
    # array의 길이가 0 또는 1이라면 이미 정렬된 것 -> 정렬필요X
    if len(array) <= 1:
        return array
    
    # 기저조건이 아니라면
    pivot = array[0]
    # pivot보다 작거나 같으면 left
    left = getSmall(array[1:], pivot)
    # pivot보다 큰 값은 right
    right = getLarge(array[1:], pivot)
    
    return quickSort(left) + [pivot] + quickSort(right)

# array에서 pivot보다 작거나 같은 값을 리스트로 리턴
def getSmall(array, pivot):
    data = []
    
    for a in array:
        if a <= pivot:
            data.append(a)
    return data

# array에서 pivot보다 큰 값을 리스트로 리턴
def getLarge(array, pivot):
    data = []
    
    for a in array:
        if a > pivot:
            data.append(a)
    return data

5. 재귀함수 디자인
  - 재귀함수를 디자인 하기 위한 세가지 단계
    ① 함수의 정의를 명확히 한다. 
    ② 기저 조건 (Base condition)에서 함수가 제대로 동작하게 작성한다. 
    ③ 함수가 작은 input에 대하여 제대로 동작한다고 가정하고 함수를 완성한다.
  - 예) 올바른 괄호인지 판단하는 재귀함수 디자인
    ① isRightParenthesis(p) 함수를 정의 (p가 올바른 괄호이면 "YES", 아니면 "NO" 를 반환하는 함수)
    ② 기저조건 : 괄호가 없거나, 괄호가 하나만 있는 경우
    ③ 인접한 괄호쌍을 제거하는 방식으로 올바른 괄호인지 판단

def checkParen(p):
    '''
    괄호 문자열 p의 쌍이 맞으면 "YES", 아니면  "NO"를 반환
    
    1. 기저조건 처리
    2. p에서 인접한 괄호쌍을 찾아 제거
    3. 제거된 문자열을 checkParen 함수에 다시 확인
    '''
    
    # 기저조건 처리
    if len(p) == 0:
        return "YES"
    elif len(p) == 1:
        return "NO"
    
    # 기저조건이 아닐 경우
    for i in range(len(p)-1):
        if p[i] == "(" and p[i+1] == ")":
            q = p[:i] + p[i+2:]
            return checkParen(q)
    
    return "NO"

[02 문제 해결 절차, 완전 탐색, 시간복잡도]

1. 문제 해결의 절차
  - 문제 해결의 절차
    ① 문제를 정확히 이해한다 
    ② 문제를 해결하는 알고리즘을 개발한다 
    ③ 알고리즘이 문제를 해결한다는 것을 증명한다
    ④ 알고리즘이 제한시간내에 동작한다는 것을 보인다
    ⑤ 알고리즘을 코드로 작성한다 
    ⑥ 제출 후 만점을 받고 매우 기뻐한다

2. 시간 복잡도
  - 시간 복잡도 : 이 알고리즘이 몇 개의 명령을 수행하는지 → 프로그램의 수행 시간을 유추
  - Big-O 표기 : 최악의 경우에 수행하는 명령 수

3. 완전 탐색
  - 완전 탐색 : Brute-Force, 가능한 모든 경우를 시도해 보는 것 (가장 기초적이고 쉬운 방법).
📌문제가 주어지면 무조건 완전 탐색법으로 먼저 시도해봐야 함!
  - 멱집합 구하기 (멱집합 : 어떤 집합의 모든 부분 집합을 모은 집합)
    → n부터 n까지의 자연수가 들어있는 집합의 멱집합을 구하는 예제

# 1부터 n까지 자연수의 원소가 있을 때, k를 가장 처음으로 선택하는 경우 반환
# ex) 3,2 -> [[2], [2, 3]] / 3, 3 -> [[3]]
def getPowerSet(n, k):
    # 기저조건
    if n == k :
        return[[k]]
    
    # 기저조건이 아닐때
    result = [[k]]
    # temp에 k 다음에 올 숫자를 담아야 함
    temp = []
    
    for i in range(k + 1, n + 1):
        temp = temp + getPowerSet(n, i)
    
    for i in range(len(temp)):
        temp[i] = [k] + temp[i]
    
    return result + temp
    
def powerSet(n) :
    result = []
    
    for i in range(1, n + 1):
        result += getPowerSet(n, i)
    
    return result

4. Complexity
  - Complexity Theory : 복잡도 이론. 각 문제마다 풀이의 시간복잡도가 다름. 
  - P class  : 다항 시간안에 풀 수 있는 문제. 
  - NP class : 답을 검증하는데 다항시간이 걸리는 문제.
  - NP-Complete class : NP class 문제들 중에서도 푸는데 가장 오랜 시간이 걸리는 문제.
→ 알고리즘과정에서는 거의 대부분 P문제들을 다룬다
# 이.....거는 지금 내 레벨에서 알기 어려운 듯....

[03 분할정복법]

1. 재귀호출을 이용한 문제 해결
  - 가장 가까운 값 찾기 : 정렬된 n개의 숫자 중 정수 m과 가장 가까운 값 찾기
    → 이진탐색 사용(O(logn))

# m과 가장 가까운 값 후보인 두 값을 리턴하는 함수
def getNearestInternal(data, m):
    
    # 기저조건일 때
    if len(data) == 1:
        return(data[0], data[0])
    elif len(data) == 2:
        return(data[0], data[1])
    
    # 기저조건 아닐 때
    # 중앙값을 가르키는 mid
    mid = len(data) // 2
    
    # mid 보다 m 이하라면 mid보다 왼쪽에 있는 데이터는 버리고 재귀호출
    if data[mid] <= m:
        return getNearestInternal(data[mid:], m)
    # mid 보다 m 이 크다면 mid보다 오른쪽에 있는 데이터는 버리고 재귀호출
    else:
        return getNearestInternal(data[:mid+1], m)
    

def getNearest(data, m) :
    # 가장 가까운 값 후보인 두 값을 찾고, 더 가까운 값을 반환
    val = getNearestInternal(data, m)
    # value[0] : m 이하면서 가장 가까운 값 / value[1] : m 이상이면서 가장 가까운 값
    
    if m - val[0] <= val[1] - m:
        return val[0]
    else:
        return val[1]

  - 거듭제곱 구하기

LIMIT_NUMBER = 1000000007

def getPower(m, n):
    
    # 기저조건
    if n == 0:
        return 1
    elif n % 2 == 0:
        temp = getPower(m, n // 2)
        return (temp * temp) % LIMIT_NUMBER
    else:
        temp = getPower(m, (n - 1) // 2)
        return (temp * temp * m) % LIMIT_NUMBER

2. 분할정복법
  - 분할정복법 : 문제를 소문제로 분할 → 각각의 소문제를 해결 → 소문제의 해결 결과를 이용해 전체문제를 해결
  - 작은 문제로 분할하는 것이 어려움, 수학적 문제 해결 능력이 가장 중요, 키보드 대신 노트와 펜을 들고 생각
# 내가 풀 수 있는 문제가 아닌 것...같.....다.........
  - 합병정렬 구현 : 리스트를 분할 해 정렬 → 분할한 리스트를 다시 비교해 정렬. 시간복잡도 O(nlogn)

import math

def mergeSort(data) :
    # 기저조건
    if len(data) == 1:
        return data
    
    mid = len(data) // 2
    left = mergeSort(data[:mid])
    right = mergeSort(data[mid:])
        
    result = []
    
    leftPtr = 0
    rightPtr = 0
    
    while leftPtr < len(left) or rightPtr < len(right):
        
        leftVal = left[leftPtr] if leftPtr < len(left) else math.inf
        rightVal = right[rightPtr] if rightPtr < len(right) else math.inf
        
        if leftVal < rightVal:
            result.append(leftVal)
            leftPtr += 1
        else:
            result.append(rightVal)
            rightPtr += 1
    
    return result

  - 연속부분 최대합

def getSubsum(data) :
    n = len(data)
    
    if n == 1 :
        return data[0]
        
    # 왼쪽/오른쪽/양쪽 연속부분 최대합 구하기
    mid = n // 2
    left = getSubsum(data[:mid])
    right = getSubsum(data[mid:])
    
    Sum = 0
    leftSum = 0
    rightSum = 0
    
    for i in range(mid - 1, -1, -1):
        Sum += data[i]
        leftSum = max(Sum, leftSum)
    
    Sum = 0
    
    for i in range(mid, n):
        Sum += data[i]
        rightSum = max(Sum, rightSum)
    
    return max([left, right, leftSum + rightSum])

[04 탐욕적 기법]

1. 탐욕적 기법
  - 탐욕적 기법 : 순간의 최적의 선택이 궁극적으로 최적의 선택이다, 단순한 방법도 문제 풀이에는 충분하다 ☞더 알아보기
  - 거스름돈 # 이거 분명히 수업 들었던 건데 왤케 생소하냐...

def coinChange(n) :    
    # 동전갯수 저장
    result = 0
    # 동전 각각의 액수를 리스트에 저장
    coins = [100, 50, 10, 5, 1]
    for coin in coins:
        result += n // coin
        # 지불하고 남은 액수
        n = n % coin 

    return result

  - 기울기가 가장 큰 두 점 찾기

def getSlope(a, b):
    return abs((b[1] - a[1]) / (b[0] - a[0]))

def maxSlope(points) :    
    # 포인트를 x 축 기준으로 정렬
    points.sort()
    # 최대 기울기 저장
    result = 0
    
    # 포인트를 돌면서 x 축으로 인접한 값을 비교
    for i in range(len(points) - 1):
        result = max(result, getSlope(points[i], points[i+1]))

    return result

  - Fractional knapsack

def fKnapsack(materials, m) :
    # 물건을 가성비 순서대로 넣어야함 (무게낮고 가치높은)
    # x[0] : 무게 / x[1] : 가치
    materials = sorted(materials, key = lambda x : x[1] / x[0], reverse = True)
    weight = 0
    value = 0
    
    for i in range(len(materials)):
        # 물건을 넣어도 버틸 수 있는 무게까지 남아 있을 때
        if weight + materials[i][0] < m:
            weight += materials[i][0]
            value += materials[i][1]
        # m 만큼 무게가 꽉 찼을 때
        elif weight + materials[i][0] == m:
            weight += materials[i][0]
            value += materials[i][1]
            return value
        # 물건을 넣으면 무게를 넘어갈 때
        else:
            temp = m - weight
            value += temp * (materials[i][1] / materials[i][0])
            return value
        
    return value

---

※ 수업 자료의 출처는 K-Digital Training x 엘리스 인공지능 서비스 개발 기획 1기 (elice.io/)입니다.