[TIL] 알고리즘 패러다임

Jeris·2023년 4월 13일
algorithm
0

코드잇 부트캠프 0기

목록 보기
33/107

Topic

Brute Force
Divide and Conquer
Dynamic Programming
Greedy Algorithm


What I Learned

Brute Force

  1. Algorithmic paradigm 알고리즘 클래스 설계의 기초가 되는 일반화된 모델

  2. Brute Force 가능한 모든 경우의 수를 시도하는 알고리즘 패러다임

    • 장점: 직관적이고, 명확하고, 확실하게 답을 찾을 수 있다.
    • 단점: 비효율적이다.
    • 의의: 효율적인 알고리즘을 찾는 과정의 출발점 역할을 한다.

  3. Trapping Rain Water 문제

    def trapping_rain(buildings):
    max_height = max(buildings)
    min_height = min(buildings)
    total_cell = 0
    for height in range(max_height, min_height, -1):
        count = 0
        start = 0
        end = 0
        for i in range(len(buildings)):
            if buildings[i] >= height:
                if count == 0:
                    start = i
                end = i
                count += 1
        # height 값에 해당하는 층에 빗물이 있는 셀 갯수
        adding_cell = end - start - count + 1
        total_cell += adding_cell
    return total_cell

# test
print(trapping_rain(\[3, 0, 0, 2, 0, 4]))
print(trapping_rain(\[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
    10
6
    • m = max_height - min_height
    • Worst-case time complexity: O(mn)
    • Best-case time complexity: O(mn)
    • Average time complexity: O(mn)
    • Worst-case Space complexity: O(1)
    • Time complexity를 더 줄일 수 있을 것 같습니다.
      • for i in range(len(buildings)) 부분에서 이미 count된 빌딩을 반복문에서 다시 조회하지 않도록 코드를 수정한다면, Best-case time complexity는 확실히 줄어들 것입니다.

Divide and Conquer

  1. Divide and Conquer 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘 패러다임

    • divide 문제를 두 개 이상의 부분 문제로 재귀적으로 분류하는 과정
    • conquer 문제가 직접 해결될 수 있을 정도로 간단해진 부분 문제의 솔루션을 구하는 과정
    • combine 부분 문제에 대한 솔루션을 결합하여 원래 문제의 답을 구하는 과정

  2. Merge Sort

    • divide 배열을 반으로 나눕니다.
    • conquer 왼쪽 배열과 오른쪽 배열을 각각 정렬한다.
    • combine 정렬된 두 배열을 하나의 정렬된 배열로 합병한다.
    • solution
    def merge(list1, list2):
    merged_list = []
    counter = 0
    for i in range(len(list1) + len(list2)):
        if counter == len(list1):
            merged_list.append(list2[i - counter])
        elif (i - counter) == len(list2):
            merged_list.append(list1[counter])   
            counter += 1         
        elif list1[counter] < list2[i - counter]:
            merged_list.append(list1[counter])
            counter += 1
        else:
            merged_list.append(list2[i - counter])
    return merged_list

def merge_sort(my_list):
    if len(my_list) < 2 :
        return my_list
    mid = len(my_list) // 2
    return merge(merge_sort(my_list[:mid]), merge_sort(my_list[mid:]))

# test
print(merge_sort([1, 3, 5, 7, 9, 11, 13, 11]))
print(merge_sort([28, 13, 9, 30, 1, 48, 5, 7, 15]))
print(merge_sort([2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]))
    [1, 3, 5, 7, 9, 11, 11, 13]
[1, 5, 7, 9, 13, 15, 28, 30, 48]
[1, 1, 2, 2, 4, 4, 4, 5, 6, 6, 7, 7, 10, 11, 13, 15]
    • Worst-case time complexity: O(nlog(n))
    • Best-case time complexity: O(nlog(n))
    • Average time complexity: O(nlog(n))
    • Worst-case Space complexity: O(n)

  3. Quick Sort

    • divide 배열 중 요소 하나를 pivot으로 정하고, pivot 앞에는 pivot보다 값이 작은 모든 요소들이 오고, pivot 뒤에는 pivot보다 값이 큰 모든 원소들이 오도록 분할(partition)합니다.
    • conquer pivot의 왼쪽 요소들을 모은 배열과 오른쪽 요소들을 모은 배열을 정렬합니다.
    • combine 없습니다.
    • solution
    def swap_elements(my_list, index1, index2):
    temp = my_list[index1]
    my_list[index1] = my_list[index2]
    my_list[index2] = temp

def partition(my_list, start, end):
    p = end
    b = start
    for i in range(start, end):
        if my_list[i] < my_list[p]:
            swap_elements(my_list, i, b)
            b += 1
    swap_elements(my_list, b, p)
    p = b
    return p

def quicksort(my_list, start = 0, end = None):
	if end == None:
    	end = len(my_list) - 1

	if start < end:
        p = partition(my_list, start, end)
        quicksort(my_list, start, p - 1)
		quicksort(my_list, p + 1, end)

# test
list1 = [1, 3, 5, 7, 9, 11, 13, 11]
quicksort(list1)
print(list1)

list2 = [28, 13, 9, 30, 1, 48, 5, 7, 15]
quicksort(list2)
print(list2)

list3 = [2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]
quicksort(list3)
print(list3)
    [1, 3, 5, 7, 9, 11, 11, 13]
[1, 5, 7, 9, 13, 15, 28, 30, 48]
[1, 1, 2, 2, 4, 4, 4, 5, 6, 6, 7, 7, 10, 11, 13, 15]
    • Worst-case time complexity: O(n^2)
    • Best-case time complexity: O(nlog(n))
    • Average time complexity: O(nlog(n))
    • Worst-case Space complexity: O(nN)

Dynamic Programming

  1. Dynamic Programming

    • Optimal Substructure, Overlapping Subproblems를 가지고 있는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘 패러다임
    • Memorization 또는 Tabulation 방법으로 구현할 수 있다.

  2. Optimal Substructure

    • 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있는 구조

  3. Overlapping Subproblems

    • 부분 문제의 답이 여러 번 재사용될 수 있는 구조

  4. Memorization

    • 함수 호출 결과를 캐시 메모리에 저장하고 함수가 동일한 입력으로 다시 호출될 경우 캐시 메모리에 저장한 값을 리턴하는 Top-down 접근 방법
    • 피보나치 수열 Memorization
    def fib_memo(n, cache):
    # base case
    if n < 3:
        return 1

	# recursive case
    if n in cache:
        return cache[n]
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)

    return cache[n]

def fib(n):
    # n번째 피보나치 수를 담는 사전
    fib_cache = {}

    return fib_memo(n, fib_cache)

# test
print(fib(10))
print(fib(50))
print(fib(100))
    55
12586269025
354224848179261915075
    • Worst-case time complexity: O(N)
    • Best-case time complexity: O(N)
    • Average time complexity: O(N)
    • Worst-case Space complexity: O(N)

  5. Tabulation

    • 부분 문제의 답을 Table에 저장하고 전체 문제를 해결할 때까지 이러한 결과를 사용하여 더 큰 부분 문제를 해결하는 bottom-up 접근 방법
    • 피보나치 수열 Tabulation
    def fib_tab(n):
    table = []
    for i in range(n):
        if i < 2:
            table.append(1)
        else:
            table.append(table[i - 1] + table[i - 2])
    return table[n - 1]

# test
print(fib_tab(10))
print(fib_tab(56))
print(fib_tab(132))
    55
225851433717
1725375039079340637797070384
    • Worst-case time complexity: O(N)
    • Best-case time complexity: O(N)
    • Average time complexity: O(N)
    • Worst-case Space complexity: O(N)
    • 아래 처럼 공간 최적화를 할 수 있다.
    def fib_tab(n):
    current = 1
    previous = 0

    for i in range(1, n):
        current, previous = current + previous, current

    return current

# 테스트 코드
print(fib_tab(16))
print(fib_tab(53))
print(fib_tab(213))
    987
53316291173
146178119651438213260386312206974243796773058
    • Worst-case time complexity: O(N)
    • Best-case time complexity: O(N)
    • Average time complexity: O(N)
    • Worst-case Space complexity: O(1)

  6. Memorization vs Tabulation

    • Memorization
      • Top-down 접근법
      • 부분 문제의 답을 캐싱한다.
      • 재귀적 구현
      • 콜 스택이 계속 쌓이기 때문에 StackOverflow가 발생할 수 있다.
      • 상대적으로 인풋이 작은 문제에 적합하다.
      • 부분 문제가 다른 부분 문제에 overlap될 때 사용한다.
    • Tabulation
      • Bottom-up 접근법
      • 부분 문제의 답을 Table에 저장한다.
      • 반복문으로 구현
      • 전체 문제에 필요 없는 부분 문제의 계산을 하게 될 수 있다.
      • 상대적으로 인풋이 큰 문제에 적합하다.
      • 부분 문제가 다른 부분 문제에 overlap되지 않을 때 사용한다.

  7. Maximizing Profit Problem

    • Problem: 갖고 있는 사탕으로 벌어들일 수 있는 최대 수익을 구하라.
      • count 판매할 사탕 개수
      • price_list 개수별 가격이 정리되어 있는 배열
      • 예를 들어, count가 5, price_list가 [0, 100, 400, 800, 900, 1000]이라면 한 사람에게 3개를 팔고 다른 사람에게 2개를 팔아서 최대 1,200의 수익을 낼 수 있다.
    • solution (Memorization)
    def max_profit_memo(price_list, count, cache):
    # base case
    if count < 2:
        cache[count] = price_list[count]
        return cache[count]

    # recursive case
    if count in cache:
        return cache[count]

    # profit: count개를 팔아서 가능한 최대 수익
    if count < len(price_list):
        profit = price_list[count]
    else:
        profit = 0
    for i in range(1, count // 2 + 1):
        profit = max(profit, max_profit_memo(price_list, i, cache)
        + max_profit_memo(price_list, count - i, cache))

    cache[count] = profit

    return profit

def max_profit(price_list, count):
	# cache: 개수별 최대 수익이 저장되어 있는 사전
    max_profit_cache = {}

    return max_profit_memo(price_list, count, max_profit_cache)

# test
print(max_profit([0, 100, 400, 800, 900, 1000], 5))
print(max_profit([0, 100, 400, 800, 900, 1000], 10))
print(max_profit([0, 100, 400, 800, 900, 1000, 1400, 1600, 2100, 2200], 9))
    1200
2500
2400
    • solution (Tabulation)
    def max_profit(price_list, count):
  profit_table = [0]

  for i in range(1, count + 1):
      # profit: count개를 팔아서 가능한 최대 수익
      if i < len(price_list):
          profit = price_list[i]
      else:
          profit = 0

      for j in range(1, i // 2 + 1):
          profit = max(profit, profit_table[j] + profit_table[i - j])

      profit_table.append(profit)

  return profit_table[count]
    2000
2400
1800

Greedy Algorithm

  1. Greedy Algorithm 각 단계에서 국소적으로 최적의 선택을 하는, problem-solving heuristics을 따르는 알고리즘 패러다임

    • heuristic 체계적이면서 합리적인 판단을 할 수 없거나 필요하지 않을 때 빠르게 사용할 수 있는 간편추론의 방법
    • 장점: 간단하고 빠르다.
    • 단점: 일반적으로 최적의 답이 보장되지 않는다.
    • Optimal Substructure, Greedy Choice Property를 가지고 있는 문제는 Greedy Algorithm으로 최적의 답을 보장할 수 있다.

  2. Greedy Choice Property globally optimal solution이 locally optimal choice로부터 얻어질 수 있는 특성

  3. 최소 동전으로 거슬러 주기 문제

    • Problem: 총 동전 갯수가 제일 적게 돈을 거슬러 주어라.
      • value 거슬러 줘야 하는 총액
      • coin_list 사용 가능한 동전 금액 리스트
    def min_coin_count(value, coin_list):
    # count: 누적 동전 개수
    count = 0

    for coin in sorted(coin_list, reverse=True):
        count += (value // coin)

        value %= coin

    return count

# 테스트 코드
default_coin_list = [100, 500, 10, 50]
print(min_coin_count(1440, default_coin_list))
print(min_coin_count(1700, default_coin_list))
print(min_coin_count(23520, default_coin_list))
print(min_coin_count(32590, default_coin_list))
    10
5
49
70

  4. 최대 곱 구하기 문제

    • Problem: 카드 게임 각 플레이어는 3장의 카드를 들고 있다. 한 사람당 카드를 하나씩 뽑아서 모두 곱했을 때 가능한 최대 곱을 구하라.
    def max_product(card_lists):
    product = 1

    for card_list in card_lists:
        product *= max(card_list)

    return product

# test
test_cards1 = [[1, 6, 5], [4, 2, 3]]
print(max_product(test_cards1))

test_cards2 = [[9, 7, 8], [9, 2, 3], [9, 8, 1], [2, 8, 3], [1, 3, 6], [7, 7, 4]]
print(max_product(test_cards2))

test_cards3 = [[1, 2, 3], [4, 6, 1], [8, 2, 4], [3, 2, 5], [5, 2, 3], [3, 2, 1]]
print(max_product(test_cards3))

test_cards4 = [[5, 5, 5], [4, 3, 5], [1, 1, 1], [9, 8, 3], [2, 8, 4], [5, 7, 4]]
print(max_product(test_cards4))

  5. 수강 신청 문제

    • Problem: 최대한 많은 수업을 들을 수 있는 수업 조합을 찾아라.
      [(4, 7), (2, 5), (1, 3), (8, 10), (5, 9), (2, 6), (13, 16), (9, 11), (1, 8)]
      • 리스트에 담겨있는 튜플들은 각각 하나의 수업을 나타낸다.
      • 각 튜플의 0번째 항목은 해당 수업의 시작 교시, 그리고 1 번 항목은 해당 수업이 끝나는 교시이다.
      • course_selection 파라미터로 전체 수업 리스트를 받고 가능한 많은 수업을 담은 리스트를 리턴하는 함수
    def course_selection(course_list):
    # 수업을 끝나는 순서로 정렬한다
    sorted_list = sorted(course_list, key=lambda x: x[1])

    # 가장 먼저 끝나는 수업은 무조건 듣는다
    my_selection = [sorted_list[0]]

    # 이미 선택한 수업과 안 겹치는 수업 중 가장 빨리 끝나는 수업을 고른다
    for course in sorted_list:
        # 마지막 수업이 끝나기 전에 새 수업이 시작하면 겹친다
        if course[0] > my_selection[-1][1]:
            my_selection.append(course)

    return my_selection

# 테스트 코드
print(course_selection([(6, 10), (2, 3), (4, 5), (1, 7), (6, 8), (9, 10)]))
print(course_selection([(1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9)]))
print(course_selection([(4, 7), (2, 5), (1, 3), (8, 10), (5, 9), (2, 5), (13, 16), (9, 11), (1, 8)]))
    [(2, 3), (4, 5), (6, 8), (9, 10)]
[(1, 2), (3, 4), (5, 7), (8, 9)]
[(1, 3), (4, 7), (8, 10), (13, 16)]

Feedback

  • 같은 문제를 다른 풀이법으로 풀어보고 비교해보자
  • Complexity 계산법을 찾아보자.
  • 다른 알고리즘 패러다임을 찾아보자.
  • 알고리즘 모듈, 라이브러리을 찾아보자.
  • 다른 언어로도 풀어보자.

Reference

profile
Jeris
job's done
이전 포스트

AJAX

다음 포스트

시간 복잡도와 공간 복잡도

0개의 댓글