Skip to content

Latest commit

ย 

History

History
909 lines (614 loc) ยท 39.1 KB

8-algorithm.md

File metadata and controls

909 lines (614 loc) ยท 39.1 KB

๐Ÿ“Œ ์งˆ๋ฌธ์€ WeareSoft๋‹˜์˜ tech-interview๋ฅผ ์ฐธ๊ณ ํ•˜์˜€์Šต๋‹ˆ๋‹ค.

Table of Contents


#1

์‹œ๊ฐ„, ๊ณต๊ฐ„ ๋ณต์žก๋„

๋ณต์žก๋„๋ž€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์„ฑ๋Šฅ์„ ํ‰๊ฐ€ํ•˜๋Š” ์ฒ™๋„๋กœ ์‹œ๊ฐ„ ๋ณต์žก๋„(Time Complexity)์™€ ๊ณต๊ฐ„ ๋ณต์žก๋„(Space Complexity)๋กœ ๋‚˜๋‰œ๋‹ค.

  • ์‹œ๊ฐ„ ๋ณต์žก๋„(Time Complexity): ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์‚ฌ์šฉ๋˜๋Š” ์—ฐ์‚ฐ ํšŸ์ˆ˜์˜ ์ด๋Ÿ‰
  • ๊ณต๊ฐ„ ๋ณต์žก๋„(Space Complexity): ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์‚ฌ์šฉ๋˜๋Š” ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์˜ ์ด๋Ÿ‰

์ฆ‰, ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ์†๋„์— ๋Œ€ํ•œ ๋ถ„์„ ๊ฒฐ๊ณผ์ด๊ณ , ๊ณต๊ฐ„ ๋ณต์žก๋„๋Š” ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰์— ๋Œ€ํ•œ ๋ถ„์„ ๊ฒฐ๊ณผ์ด๋‹ค.

์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๋ณต์žก๋„๋Š” ์ ๊ทผ์  ํ‘œ๊ธฐ๋ฒ•์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋Š”๋ฐ, ์ ๊ทผ์  ํ‘œ๊ธฐ๋ฒ•์—๋Š” ๋Œ€ํ‘œ์ ์œผ๋กœ O(๋น…์˜ค), โ„ฆ(์˜ค๋ฉ”๊ฐ€), ฮ˜(์„ธํƒ€)๊ฐ€ ์žˆ๋‹ค.

  • O Notation (๋น…์˜ค ํ‘œ๊ธฐ๋ฒ•): ์ ๊ทผ์  ์ƒํ•œ์„  / ์ตœ์•…์˜ ๊ฒฝ์šฐ
  • ฮฉ Notation (์˜ค๋ฉ”๊ฐ€ ํ‘œ๊ธฐ๋ฒ•): ์ ๊ทผ์  ํ•˜ํ•œ์„  / ์ตœ์ƒ์˜ ๊ฒฝ์šฐ
  • ฮธ Notation (์„ธํƒ€ ํ‘œ๊ธฐ๋ฒ•): ์ ๊ทผ์  ์ƒํ•œ์„ ๊ณผ ์ ๊ทผ์  ํ•˜ํ•œ์„ ์˜ ๊ต์ง‘ํ•ฉ / ํ‰๊ท ์˜ ๊ฒฝ์šฐ

์ผ๋ฐ˜์ ์œผ๋กœ ์ตœ์•…์˜ ๊ฒฝ์šฐ์˜ ์„ฑ๋Šฅ์„ ์ธก์ •ํ•˜๋Š” ๋น…์˜ค ํ‘œ๊ธฐ๋ฒ•์„ ๋งŽ์ด ์‚ฌ์šฉํ•œ๋‹ค.

References


#2-1

Bubble Sort

๋ฒ„๋ธ” ์ •๋ ฌ(Bubble Sort)์€ ๋ฐฐ์—ด์˜ 0๋ฒˆ๋ถ€ํ„ฐ N-1๋ฒˆ๊นŒ์ง€ ํƒ์ƒ‰์„ ํ•˜๋ฉด์„œ ์ธ์ ‘ํ•œ ์นธ๊ณผ ๋น„๊ตํ•˜์—ฌ swap์„ ํ•˜๋Š” ๋ฐฉ์‹์˜ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

์œ„์˜ ๊ณผ์ •์ด ๋ฒ„๋ธ” ์ •๋ ฌ์„ 1ํšŒ ์‹ค์‹œํ•˜๊ณ  ๋‚˜์„œ์˜ ๊ฒฐ๊ณผ์ด๋‹ค. j๋ฒˆ์งธ ๊ฐ’๊ณผ j+1๋ฒˆ์งธ ๊ฐ’์„ ๋น„๊ตํ•ด์„œ ๋งŒ์•ฝ j๋ฒˆ์งธ ๊ฐ’์ด ๋” ํฌ๋‹ค๋ฉด swap์„ ํ•ด์ฃผ๋Š” ์‹์œผ๋กœ ๋™์ž‘ํ•œ๋‹ค.

์‹œ๊ฐ„ ๋ณต์žก๋„

$$ O(N^2) $$

ํŒŒ์ด์ฌ ๊ตฌํ˜„

def bubbleSort(alist):
    for passnum in range(len(alist)-1, 0, -1):
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

References


#2-2

Selection Sort

์„ ํƒ ์ •๋ ฌ(Selection Sort)์€ ์œ„์น˜ ๋ณ€๊ฒฝ ํšŸ์ˆ˜๋ฅผ ์ค„์—ฌ, ๋ฒ„๋ธ” ์ •๋ ฌ์„ ์ผ๋ถ€ ๊ฐœ์„ ํ•œ ๊ธฐ๋ฒ•์ด๋‹ค. ์ฃผ์–ด์ง„ ๋ฐฐ์—ด ์ค‘์— ์ตœ๋Œ“๊ฐ’์„ ์ฐพ์•„ ์ •๋ ฌ๋˜์ง€ ์•Š์€ ๋ฐฐ์—ด์˜ ๋งจ ๋’ค์˜ ๊ฐ’๊ณผ ์ž๋ฆฌ๋ฅผ ๋ฐ”๊พธ์–ด๋‚˜๊ฐ€๋Š” ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๋ฐฐ์—ด์˜ ๋งจ ๋’ค๋ถ€ํ„ฐ ์ฐจ๋ก€๋กœ ์ •๋ ฌ์ด ๋œ๋‹ค.

๋ฒ„๋ธ” ์ •๋ ฌ์€ ์™ผ์ชฝ์— ์žˆ๋Š” ๊ฐ’์ด ๋น„๊ต ๋Œ€์ƒ์ธ ์˜ค๋ฅธ์ชฝ์— ์žˆ๋Š” ๊ฐ’๋ณด๋‹ค ํฌ๋ฉด ์ž๋ฆฌ๋ฅผ ๋ฐ”๊ฟ”์คฌ๋Š”๋ฐ ๋ฐ˜ํ•ด, ์„ ํƒ ์ •๋ ฌ์€ ์ผ๋‹จ ์ตœ๋Œ“๊ฐ’(ํ˜น์€ ์ตœ์†Ÿ๊ฐ’)์„ ์ฐพ์€ ๋’ค์—์•ผ ์ด ๊ฐ’์„ ์ •ํ•ด์ง„ ์œ„์น˜๋กœ ๋ณด๋‚ด์ฃผ๊ฒŒ ๋œ๋‹ค. ๋‹ค์‹œ ๋งํ•ด ๋น„๊ต ํšŸ์ˆ˜ ์ธก๋ฉด์—์„œ๋Š” ๋ฒ„๋ธ” ์ •๋ ฌ๊ณผ ์„ ํƒ ์ •๋ ฌ์ด ๊ฐ™๊ณ  ๋‘˜ ๋ชจ๋‘ $O(n^2)$์˜ ๊ณ„์‚ฐ ๋ณต์žก์„ฑ์„ ๊ฐ–์ง€๋งŒ ์ž๋ฆฌ ์ด๋™(swap)์ธก๋ฉด์—์„œ๋Š” ์„ ํƒ ์ •๋ ฌ์ด ํšจ์œจ์ ์ด๋‹ค.

์‹œ๊ฐ„ ๋ณต์žก๋„

$$ O(N^2) $$

ํŒŒ์ด์ฌ ๊ตฌํ˜„

def selectionSort(alist):
   for fillslot in range(len(alist)-1, 0, -1):
       positionOfMax = 0
       for location in range(1, fillslot+1):
           if alist[location] > alist[positionOfMax]:
               positionOfMax = location

       temp = alist[fillslot]
       alist[fillslot] = alist[positionOfMax]
       alist[positionOfMax] = temp

References


#2-3

Insertion Sort

์‚ฝ์ž… ์ •๋ ฌ(Insertion Sort)์€ ๋ฐฐ์—ด์˜ ๋ชจ๋“  ์š”์†Œ๋ฅผ ๋ฐฐ์—ด์˜ ์‹œ์ž‘๋ถ€ํ„ฐ ๋๊นŒ์ง€ ํ˜„์žฌ ๋ฐฐ์—ด์˜ ์š”์†Œ๋“ค๊ณผ ๋น„๊ตํ•ด ๊ฐ€๋ฉด์„œ ์ ์ ˆํ•œ ์œ„์น˜์— ์‚ฝ์ž…ํ•˜๋Š” ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

์‹œ๊ฐ„ ๋ณต์žก๋„

  • ์ตœ์•…์˜ ๊ฒฝ์šฐ(Worst): $O(N^2)$
  • ํ‰๊ท ์ ์ธ ๊ฒฝ์šฐ(Average): $O(N^2)$
  • ์ตœ์„ ์˜ ๊ฒฝ์šฐ(Best): $O(N)$

ํŒŒ์ด์ฌ ๊ตฌํ˜„

def insertion_sort(collection):
    for index in range(1, len(collection)):
        while 0 < index and collection[index] < collection[index - 1]:
            collection[index], collection[
                index - 1] = collection[index - 1], collection[index]
            index -= 1

    return collection

References


#2-4

Merge Sort

ํ•ฉ๋ณ‘ ์ •๋ ฌ(Merge Sort)๋Š” ๋ฐฐ์—ด์„ ์ž˜๊ฒŒ ์ชผ๊ฐ  ๋’ค ๋‘˜์”ฉ ํฌ๊ธฐ๋ฅผ ๋น„๊ตํ•ด ์ •๋ ฌํ•˜๊ณ  ๋ถ„๋ฆฌ๋œ ๋ฆฌ์ŠคํŠธ๋ฅผ ์žฌ๊ท€์ ์œผ๋กœ ํ•ฉ์ณ์„œ ์ •๋ ฌ์„ ์™„์„ฑํ•˜๋Š” ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๋ถ„ํ• ๋œ ๋ฐฐ์—ด์„ ์ €์žฅํ•ด๋‘˜ ๊ณต๊ฐ„์ด ํ•„์š”ํ•ด ๋ฉ”๋ชจ๋ฆฌ ์†Œ๋ชจ๋Ÿ‰์ด ํฐ ํŽธ์ด๋‹ค. ๋ฌธ์ œ๋ฅผ ๋ถ„๋ฆฌํ•˜๊ณ  ๊ฐ๊ฐ์„ ํ•ด๊ฒฐํ•œ ํ›„ ๋‹ค์‹œ ํ•ฉ์น˜๋Š” Divide & Conquer ๋ฐฉ์‹์„ ์‚ฌ์šฉํ•œ๋‹ค.

  • Divide: ์ดˆ๊ธฐ ๋ฐฐ์—ด์„ 2๊ฐœ์˜ ๋ฐฐ์—ด๋กœ ๋ถ„ํ• ํ•œ๋‹ค.
  • Conquer: ๊ฐ ๋ถ€๋ถ„ ๋ฐฐ์—ด์„ ์žฌ๊ท€์ ์œผ๋กœ ๋ณ‘ํ•ฉ ์ •๋ ฌ์„ ์‚ฌ์šฉํ•˜์—ฌ ์ •๋ ฌํ•œ๋‹ค.
  • Merge: ๋ถ€๋ถ„ ๋ฐฐ์—ด์„ ํ•˜๋‚˜์˜ ๋ฐฐ์—ด๋กœ ๊ฒฐํ•ฉํ•œ๋‹ค.

์‹œ๊ฐ„ ๋ณต์žก๋„

$$ O(N \log N) $$

ํŒŒ์ด์ฌ ๊ตฌํ˜„

def merge_sort(list):
    if len(list) <= 1:
        return list
    mid = len(list) // 2
    leftList = list[:mid]
    rightList = list[mid:]
    leftList = merge_sort(leftList)
    rightList = merge_sort(rightList)
    return merge(leftList, rightList)

References


#2-5

Heap Sort

ํž™ ์ •๋ ฌ(Heap Sort)์€ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๋กœ ๊ตฌํ˜„๋˜๋Š” ์ •๋ ฌ ๋ฐฉ์‹์œผ๋กœ, ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ ํž™ ์†์„ฑ(๊ฐ ๋…ธ๋“œ์˜ ๊ฐ’์ด ์ž์‹ ์˜ ์ž์‹ ๋…ธ๋“œ ๊ฐ’๋ณด๋‹ค ํฐ ์ด์ง„ ํŠธ๋ฆฌ)์„ ๋งŒ์กฑํ•˜๋„๋ก ์žฌ๊ท€์ ์œผ๋กœ ํŠธ๋ฆฌ ๊ตฌ์กฐ๋ฅผ ๋งŒ๋“ค์–ด ์ •๋ ฌ์„ ์™„์„ฑํ•˜๋Š” ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

๋™์ž‘ ์›๋ฆฌ

  1. ์ฃผ์–ด์ง„ ์›์†Œ๋“ค๋กœ ์ตœ๋Œ€ ํž™์„ ๊ตฌ์„ฑํ•œ๋‹ค.
  2. ํ˜„์žฌ ํž™์˜ ๋ฃจํŠธ ๋…ธ๋“œ์—๋Š” ์ตœ๋Œ€๊ฐ’์ด ์กด์žฌํ•˜๊ฒŒ ๋œ๋‹ค. ๋ฃจํŠธ์˜ ๊ฐ’์„ ๋งˆ์ง€๋ง‰ ์š”์†Œ์™€ ๋ฐ”๊พผ ํ›„, ํž™์˜ ์‚ฌ์ด์ฆˆ๋ฅผ ํ•˜๋‚˜ ์ค„์ธ๋‹ค.
  3. ํž™์˜ ์‚ฌ์ด์ฆˆ๊ฐ€ 1๋ณด๋‹ค ํฌ๋ฉด ์œ„ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค.

์‹œ๊ฐ„ ๋ณต์žก๋„

$$ O(N \log N) $$

ํŒŒ์ด์ฌ ๊ตฌํ˜„

def heapify(unsorted, index, heap_size):
    largest = index
    left_index = 2 * index + 1
    right_index = 2 * index + 2
    if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
        largest = left_index
    if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
        largest = right_index
    if largest != index:
        unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
        heapify(unsorted, largest, heap_size)

def heap_sort(unsorted):
    n = len(unsorted)
    for i in range(n//2-1, -1, -1):
        heapify(unsorted, i, n)
    for i in range(n-1, 0, -1):
        unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
        heapify(unsorted, 0, i)
    return unsorted

References


#2-6

Quick Sort

ํ€ต ์ •๋ ฌ(Quick Sort)๋Š” pivot์„ ๊ธฐ์ค€์œผ๋กœ pivot ์•ž์—๋Š” pivot๋ณด๋‹ค ์ž‘์€ ๊ฐ’, ๋’ค์—๋Š” ํฐ ๊ฐ’์ด ์˜ค๋„๋ก ํ•˜์—ฌ ๋ฐฐ์—ด์„ ๋ถ„ํ• ํ•˜๊ณ , ๋ถ„ํ• ๋œ ๋‘ ๊ฐœ ๋ฐฐ์—ด ๊ฐ๊ฐ์— ์žฌ๊ท€์ ์œผ๋กœ ์ด ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•ด ์ •๋ ฌ์„ ์™„์„ฑํ•˜๋Š” ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ํ•ฉ๋ณ‘ ์ •๋ ฌ๊ณผ ๋‹ฌ๋ฆฌ ์ฃผ์–ด์ง„ ๋ฐฐ์—ด์„ ์ž„์˜๋กœ ๋‚˜๋ˆ„์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ๋Œ€๊ฐœ๋Š” ํšจ์œจ์ ์ด์ง€๋งŒ, pivot์ด ์ž˜๋ชป ์„ ํƒ๋˜๋ฉด ๋ณต์žก๋„๊ฐ€ $O(n^2)$์ด ๋  ์ˆ˜๋„ ์žˆ๋‹ค.

์œ„์˜ ๊ณผ์ •์ด ํ€ต ์ •๋ ฌ์„ 1ํšŒ ์‹ค์‹œํ•˜๊ณ  ๋‚˜์„œ์˜ ๊ฒฐ๊ณผ์ด๋‹ค. 54(pivot)๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋‘ ๊ฐœ์˜ ๋ฐฐ์—ด๋กœ ๋‚˜๋‰œ๋‹ค.

์‹œ๊ฐ„ ๋ณต์žก๋„

  • ์ตœ์•…์˜ ๊ฒฝ์šฐ(Worst): $O(N^2)$
  • ํ‰๊ท ์ ์ธ ๊ฒฝ์šฐ(Average): $O(N \log N)$
  • ์ตœ์„ ์˜ ๊ฒฝ์šฐ(Best): $O(N \log N)$

ํŒŒ์ด์ฌ ๊ตฌํ˜„

def quickSort(alist):
   quickSortHelper(alist, 0, len(alist)-1)

def quickSortHelper(alist, first, last):
   if first < last:

       splitpoint = partition(alist, first, last)

       quickSortHelper(alist, first, splitpoint-1)
       quickSortHelper(alist, splitpoint+1, last)


def partition(alist, first, last):
   pivotvalue = alist[first]

   leftmark = first + 1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp

   return rightmark

References


#2-7

Counting Sort

๊ณ„์ˆ˜ ์ •๋ ฌ(Counting Sort)์€ ์ž…๋ ฅ๊ฐ’์˜ ๋นˆ๋„๋ฅผ ์„ธ์–ด์„œ ์ด๋ฅผ ๊ฒฐ๊ณผ ๋ฆฌ์ŠคํŠธ์˜ ์ธ๋ฑ์Šค๋กœ ํ™œ์šฉํ•˜๊ณ  ์ž…๋ ฅ ๋ฆฌ์ŠคํŠธ์˜ ์š”์†Œ๊ฐ’์— ํ•ด๋‹นํ•˜๋Š” ๊ฒฐ๊ณผ ๋ฆฌ์ŠคํŠธ ์ธ๋ฑ์Šค ์œ„์น˜์— ์ฑ„์›Œ ๋„ฃ๋Š” ๋ฐฉ์‹์œผ๋กœ ์ •๋ ฌ์„ ์™„์„ฑํ•˜๋Š” ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ์ž…๋ ฅ ๋ฆฌ์ŠคํŠธ์˜ ์ตœ๋Œ“๊ฐ’(k)์ด ์ปค์งˆ์ˆ˜๋ก ๋ณต์žก๋„๊ฐ€ ํฌ๊ฒŒ ๋†’์•„์ง„๋‹ค.

๋™์ž‘ ์›๋ฆฌ

  1. ๊ฐ ๋ฐ์ดํ„ฐ์˜ ๊ฐœ์ˆ˜๋ฅผ ๋ชจ๋‘ count ํ•œ๋‹ค.
  2. ์ตœ์†Ÿ๊ฐ’๋ถ€ํ„ฐ ๊ฐ ๊ฐ’๊นŒ์ง€์˜ count ๋ˆ„์ ํ•ฉ์„ ๊ตฌํ•œ๋‹ค.
  3. ์ƒˆ๋กœ์šด ๋ฐฐ์—ด์— ๋ˆ„์ ํ•ฉ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ค„์—ฌ์ฃผ๋ฉฐ ์ €์žฅํ•œ๋‹ค.

์‹œ๊ฐ„ ๋ณต์žก๋„

$$ O(N+k) $$

($k$: ๋ฐ์ดํ„ฐ์˜ ์ตœ๋Œ“๊ฐ’)

ํŒŒ์ด์ฌ ๊ตฌํ˜„

def counting_sort(A, k):
    B = [-1] * len(A)
    C = [0] * (k + 1)

    for a in A:
        C[a] += 1

    for i in range(k):
        C[i+1] += C[i]

    for j in reversed(range(len(A))):
    	B[C[A[j]] - 1] = A[j]
    	C[A[j]] -= 1

    return B

References


#2-8

Radix Sort

๊ธฐ์ˆ˜ ์ •๋ ฌ(Radix Sort)์€ ์ž…๋ ฅ๊ฐ’์˜ ์ž๋ฆฟ์ˆ˜(d) ๊ฐ๊ฐ์— ๋Œ€ํ•ด ์นด์šดํŒ… ์ •๋ ฌ์„ ์ ์šฉํ•˜์—ฌ ์ž…๋ ฅ ๋ฐ์ดํ„ฐ์˜ ์ตœ๋Œ“๊ฐ’์ธ k๊ฐ€ ์ปค์งˆ์ˆ˜๋ก ํšจ์œจ์ด ๋–จ์–ด์ง€๋Š” ์นด์šดํŒ… ์ •๋ ฌ์˜ ๋‹จ์ ์„ ๋ณด์™„ํ•œ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. 10์ง„๋ฒ•์œผ๋กœ ํ‘œํ˜„๋œ ์ž…๋ ฅ๊ฐ’์— ๊ธฐ์ˆ˜ ์ •๋ ฌ์„ ์ ์šฉํ•˜๋ฉด k ๊ฐ’์ด 9๋กœ ์ž‘์•„์ง„๋‹ค.

์‹œ๊ฐ„ ๋ณต์žก๋„

$$ d \times O(N) $$

($d$: ์ž…๋ ฅ๊ฐ’์˜ ์ž๋ฆฟ์ˆ˜)

ํŒŒ์ด์ฌ ๊ตฌํ˜„

from math import log

def get_digit(number, d, base):
    return (number//base**d) % base

def counting_sort_with_digit(A, d, base):
    k = base - 1
    B = [-1] * len(A)
    C = [0] * (k + 1)
    for a in A:
        C[get_digit(a, d, base)] += 1
    for i in range(k):
        C[i+1] += C[i]
    for j in reversed(range(len(A))):
        B[C[get_digit(A[j], d, base)]-1] = A[j]
        C[get_digit(A[j], d, base)] -= 1
    return B

def radix_sort(list, base=10):
    digit = int(log(max(list), base)+1)
    for d in range(digit):
        list = counting_sort_with_digit(list, d, base)
    return list

References


#3

Divide and Conquer

๋ถ„ํ•  ์ •๋ณต(Divide and Conquer)์€ ๋ฌธ์ œ๋ฅผ ๋ถ„ํ• ํ•ด์„œ ๋ถ„ํ• ํ•œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•œ ๋‹ค์Œ ๊ฒฐ๊ณผ๋ฅผ ์กฐํ•ฉํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ํฐ ๋ฌธ์ œ๋ฅผ ์ž‘์€ ๋ฌธ์ œ๋กœ ๋ถ„ํ• ํ•œ๋‹ค๋Š” ๊ด€์ ์—์„œ ํ•˜ํ–ฅ์‹ ์ ‘๊ทผ ๋ฐฉ๋ฒ•์œผ๋กœ ๋ฌธ์ œ๋ฅผ ํ‘ผ๋‹ค๊ณ  ๋ณผ ์ˆ˜ ์žˆ๋‹ค.

  • ๋ถ„ํ• : ๋ฌธ์ œ๋ฅผ ๋™์ผํ•œ ์œ ํ˜•์˜ ์—ฌ๋Ÿฌ ํ•˜์œ„ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ„๋Š” ๊ฒƒ
  • ํ•ด๊ฒฐ: ๊ฐ€์žฅ ์ž‘์€ ๋‹จ์œ„์˜ ํ•˜์œ„ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๊ฒƒ
  • ์กฐํ•ฉ: ํ•˜์œ„ ๋ฌธ์ œ์— ๋Œ€ํ•œ ๊ฒฐ๊ณผ๋ฅผ ์›๋ž˜ ๋ฌธ์ œ์— ๋Œ€ํ•œ ๊ฒฐ๊ณผ๋กœ ์กฐํ•ฉํ•˜๋Š” ๊ฒƒ

๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ณดํ†ต ์žฌ๊ท€๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๊ตฌํ˜„ํ•œ๋‹ค. ๋‹ค์Œ์€ ๋ถ„ํ•  ์ •๋ณต์˜ ๋Œ€ํ‘œ์ ์ธ ๋ฌธ์ œ์ธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด ์ฝ”๋“œ์ด๋‹ค.

def fibb(n):
  if n <= 1:
    return 1
  return fibb(n-1) + fibb(n-2)

References


#4

Dynamic Programming

๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ(Dynamic Programming)์€ ์ค‘๋ณต๋œ ํ•˜์œ„ ๋ฌธ์ œ๋“ค์˜ ๊ฒฐ๊ณผ๋ฅผ ์ €์žฅํ•œ ํ›„ ์›๋ž˜ ๋ฌธ์ œ์˜ ๊ฒฐ๊ณผ์™€ ํ•ฉํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ๊ณผ ๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํฐ ์ฐจ์ด์ ์€ ์ค‘๋ณต๋œ ๋ฌธ์ œ์˜ ์ฐจ์ด์ด๋‹ค. ๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•œ ๋ณ‘ํ•ฉ ์ •๋ ฌ์ด๋‚˜ ํ€ต ์ •๋ ฌ์˜ ๊ฒฝ์šฐ ํ•˜์œ„ ๋ฌธ์ œ๋“ค์ด ์ค‘๋ณต๋˜์ง€ ์•Š๋Š”๋‹ค. ๋ฐ˜๋ฉด ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์€ ์ค‘๋ณต๋œ ํ•˜์œ„ ๋ฌธ์ œ๋“ค์˜ ๊ฒฐ๊ณผ๋ฅผ ์ €์žฅํ•จ์œผ๋กœ์จ ์ค‘๋ณต ๊ณ„์‚ฐ์„ ํ”ผํ•œ๋‹ค. ๋งŒ์•ฝ ๋ฌธ์ œ๊ฐ€ ์ค‘๋ณต๋œ ํ•˜์œ„ ๋ฌธ์ œ๊ฐ€ ์—†๋‹ค๋ฉด ๊ทธ ๋ฌธ์ œ๋Š” ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์œผ๋กœ ํ’€ ์ˆ˜ ์—†๋‹ค.

๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์€ ํฌ๊ฒŒ ์ƒํ–ฅ์‹๊ณผ ํ•˜ํ–ฅ์‹ ์ ‘๊ทผ๋ฒ•์œผ๋กœ ๋‚˜๋‰œ๋‹ค.

์ƒํ–ฅ์‹ ์ ‘๊ทผ๋ฒ•: ํƒ€๋ทธ๋ ˆ์ด์…˜(Tabulation)

์ƒํ–ฅ์‹ ์ ‘๊ทผ๋ฒ•(Bottom-Up Approach)๋Š” ์ž‘์€ ๋ฌธ์ œ์˜ ์ •๋‹ต์„ ์ด์šฉํ•ด ํฐ ๋ฌธ์ œ์˜ ์ •๋‹ต์„ ํ‘ธ๋Š” ๋ฐฉ์‹์ด๋‹ค. ๋ฐ์ดํ„ฐ๋ฅผ ํ…Œ์ด๋ธ” ํ˜•ํƒœ๋กœ ์ €์žฅํ•˜๊ธฐ ๋•Œ๋ฌธ์— ํƒ€๋ทธ๋ ˆ์ด์…˜(Tabulation)์ด๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค.

def fibb(n):
  table = [1] * (n+1)
  for i in range(2, n+1):
    table[i] = table[i-1] + table[i-2]
  return table[n]

ํ•˜ํ–ฅ์‹ ์ ‘๊ทผ๋ฒ•: ๋ฉ”๋ชจ์ด์ œ์ด์…˜(Memoization)

ํ•˜ํ–ฅ์‹ ์ ‘๊ทผ๋ฒ•(Top-Down Approach)๋Š” ์ž‘์€ ๋ฌธ์ œ์˜ ๊ฒฐ๊ณผ๋ฅผ ์–ป์—ˆ๋Š”์ง€ ํ™•์ธํ•ด๊ฐ€๋ฉฐ ๋ฌธ์ œ๋ฅผ ์žฌ๊ท€๋กœ ํ’€์–ด๊ฐ€๋Š” ๋ฐฉ์‹์ด๋‹ค. ๋ถ„ํ•  ์ •๋ณต์—์„œ์˜ ์žฌ๊ท€ ๋ฐฉ์‹๊ณผ ์œ ์‚ฌํ•˜๋‚˜ ์ด๋ฏธ ํ‘ผ ๋ฌธ์ œ์ธ์ง€ ๊ฒ€์‚ฌํ•œ๋‹ค. ์ด์™€ ๊ฐ™์€ ๋ฐฉ์‹์„ ๋ฉ”๋ชจ์ด์ œ์ด์…˜(Memoization)์ด๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค.

# ์ „์—ญ ๋ณ€์ˆ˜๋กœ table๊ณผ n์ด ๋ฏธ๋ฆฌ ์„ ์–ธ๋จ
def fibb(n):
  if n <= 1:
    return 1
  if table[n]:
    return table[n]
  table[n] = fibb(n-1) + fibb(n-2)
  return table[n]

References


#5

Greedy Algorithm

๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ˜„์žฌ ๋‹จ๊ณ„์—์„œ ์ตœ์„ ์˜ ๋ฐฉ๋ฒ•์„ ์„ ํƒํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๊ฐ€์žฅ ํฐ ๊ฐ’๋งŒ ์„ ํƒ, ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’๋งŒ ์„ ํƒ ๋“ฑ ํ•œ ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์„ ์ •ํ•ด๋†“๊ณ  ๋‹ค์Œ ๋‹จ๊ณ„๋กœ ๋‚˜์•„๊ฐ€์„œ๋„ ๊ฐ™์€ ๋ฐฉ์‹์œผ๋กœ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•œ๋‹ค. ๋‹จ, ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ ์šฉํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ํ•ญ์ƒ ์ ์šฉ๋  ์ˆ˜ ์žˆ๋Š”์ง€ ์ •๋‹น์„ฑ์„ ํ™•์ธํ•ด์•ผ ํ•œ๋‹ค.

๊ฐ€์žฅ ์ ์€ ๋™์ „ ๊ฐœ์ˆ˜๋ฅผ ๊ฑฐ์Šฌ๋Ÿฌ์ฃผ๋Š” ๋™์ „ ๊ฑฐ์Šค๋ฆ„๋ˆ ๋ฌธ์ œ๋ฅผ ์ƒ๊ฐํ•ด๋ณด์ž.

1, 5, 10์›์˜ ๊ฑฐ์Šค๋ฆ„๋ˆ์ด ์žˆ๋‹ค๋ฉด, ํฐ ๊ฐ’ ๋จผ์ € ๊ทธ๋ฆฌ๋””ํ•˜๊ฒŒ 10์›์งœ๋ฆฌ ๋™์ „ ๋จผ์ € ๋˜๋Š”๋Œ€๋กœ ์ฃผ๊ณ , ๋‹ค์Œ์œผ๋กœ 5์›, ๋‚จ๋Š” ๋ˆ์€ 1์›์œผ๋กœ ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ๋‹ค. ์ด ๊ฒฝ์šฐ, ๊ฐ’์ด ํฐ ๋™์ „๋“ค์€ ๊ฐ’์ด ์ž‘์€ ๋™์ „์œผ๋กœ ๋‚˜๋ˆ ์งˆ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ์ž‘์€ ๋™์ „์œผ๋กœ ์ƒˆ๋กœ์šด ๋‹จ์œ„๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์— ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์„ฑ๋ฆฝํ•œ๋‹ค.

๋งŒ์•ฝ ์œ„ ๋ฌธ์ œ์—์„œ ๊ฑฐ์Šค๋ฆ„๋ˆ์ด 1, 7, 10์›์ด๋ผ๋ฉด ์–ด๋–ป๊ฒŒ ๋ ๊นŒ? 14์›์„ ๊ฑฐ์Šฌ๋Ÿฌ์ฃผ๊ธฐ ์œ„ํ•ด ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์“ด๋‹ค๋ฉด 10์› 1๊ฐœ, 1์› 4๊ฐœ ์ด 5๊ฐœ์˜ ๋™์ „์„ ์“ธ ๊ฒƒ์ด๋‹ค. ํ•˜์ง€๋งŒ ์˜ฌ๋ฐ”๋ฅธ ๋‹ต์€ 7์› 2๊ฐœ ์ด 2๊ฐœ๊ฐ€ ํ•„์š”ํ•˜๋‹ค. ์ด ๊ฒฝ์šฐ, 10์›์€ 7์›์œผ๋กœ ๋‚˜๋ˆ ์งˆ ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์— ๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜๋Š”๊ฒŒ ์ ํ•ฉํ•˜๋‹ค.

๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋“ฑ์—๋„ ํ™œ์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ์ •๋ ฌ ๋“ฑ๊ณผ ํ•จ๊ป˜ ์‚ฌ์šฉ๋˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋งŽ๋‹ค.

References


#6

Graph

๊ทธ๋ž˜ํ”„๋Š” ์ •์ ๊ณผ ๊ฐ„์„ ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. ์ •์  ๊ฐ„์˜ ์—ฐ๊ฒฐ๊ด€๊ณ„๋Š” ๊ฐ„์„ ์œผ๋กœ ๋‚˜ํƒ€๋‚ธ๋‹ค.

#6-1

Graph Traversal: BFS, DFS

BFS(Breadth-First Search, ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰)

BFS๋Š” ๊ทธ๋ž˜ํ”„ ์ „์ฒด๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ๋ฒ• ์ค‘ ํ•˜๋‚˜๋กœ์จ, ํ˜„์žฌ ํ™•์ธํ•˜๋Š” ๋…ธ๋“œ์˜ ์ธ์ ‘ํ•œ ๋…ธ๋“œ๋“ค์„ ๋จผ์ € ํƒ์ƒ‰ํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ์‹œ์ž‘ ์ •์ ์œผ๋กœ๋ถ€ํ„ฐ ๊ฐ€๊นŒ์šด ์ •์ ์„ ๋จผ์ € ๋ฐฉ๋ฌธํ•˜๊ณ  ๋ฉ€๋ฆฌ ๋–จ์–ด์ ธ ์žˆ๋Š” ์ •์ ์„ ๋‚˜์ค‘์— ๋ฐฉ๋ฌธํ•˜๋Š” ์ˆœํšŒํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๋…ธ๋“œ๋ฅผ ํƒ์ƒ‰ํ•œ๋‹ค. ์ฃผ๋กœ ๊ตฌํ˜„์€ Queue๋ผ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์— ์ด์›ƒํ•˜๋Š” ์ •์ ์„ ๋‹ค ๋‹ด์•„๋†“๊ณ  ์ฐจ๋ก€๋Œ€๋กœ pop์„ ํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„ํ•œ๋‹ค. ์ฃผ๋กœ ๋‘ ๋…ธ๋“œ ์‚ฌ์ด์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ ํ˜น์€ ์ž„์˜์˜ ๊ฒฝ๋กœ๋ฅผ ์ฐพ๊ณ  ์‹ถ์„ ๋•Œ ์ด ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•œ๋‹ค.

  • ์žฅ์ 
    • ๋…ธ๋“œ์˜ ์ˆ˜๊ฐ€ ์ ๊ณ  ๊นŠ์ด๊ฐ€ ์–•์€ ๊ฒฝ์šฐ ๋น ๋ฅด๊ฒŒ ๋™์ž‘ํ•  ์ˆ˜ ์žˆ๋‹ค.
    • ๋‹จ์ˆœ ๊ฒ€์ƒ‰ ์†๋„๊ฐ€ ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰(DFS)๋ณด๋‹ค ๋น ๋ฅด๋‹ค.
    • ๋„ˆ๋น„๋ฅผ ์šฐ์„  ํƒ์ƒ‰ํ•˜๊ธฐ์— ๋‹ต์ด ๋˜๋Š” ๊ฒฝ๋กœ๊ฐ€ ์—ฌ๋Ÿฌ๊ฐœ์ธ ๊ฒฝ์šฐ์—๋„ ์ตœ๋‹จ๊ฒฝ๋กœ์ž„์„ ๋ณด์žฅํ•œ๋‹ค.
    • ์ตœ๋‹จ๊ฒฝ๋กœ๊ฐ€ ์กด์žฌํ•œ๋‹ค๋ฉด ์–ด๋Š ํ•œ ๊ฒฝ๋กœ๊ฐ€ ๋ฌดํ•œํžˆ ๊นŠ์–ด์ง„๋‹คํ•ด๋„ ์ตœ๋‹จ๊ฒฝ๋กœ๋ฅผ ๋ฐ˜๋“œ์‹œ ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค.
  • ๋‹จ์ 
    • ์žฌ๊ท€ํ˜ธ์ถœ์˜ DFS์™€๋Š” ๋‹ฌ๋ฆฌ ํ์— ๋‹ค์Œ์— ํƒ์ƒ‰ํ•  ์ •์ ๋“ค์„ ์ €์žฅํ•ด์•ผ ํ•˜๋ฏ€๋กœ ์ €์žฅ๊ณต๊ฐ„์ด ๋งŽ์ด ํ•„์š”ํ•˜๋‹ค.
    • ๋…ธ๋“œ์˜ ์ˆ˜๊ฐ€ ๋Š˜์–ด๋‚˜๋ฉด ํƒ์ƒ‰ํ•ด์•ผํ•˜๋Š” ๋…ธ๋“œ ๋˜ํ•œ ๋งŽ์•„์ง€๊ธฐ์— ๋น„ํ˜„์‹ค์ ์ด๋‹ค.

DFS(Depth-First Search, ๊นŠ์ด์šฐ์„ ํƒ์ƒ‰)

DFS๋Š” ๊ทธ๋ž˜ํ”„ ์ „์ฒด๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ๋ฒ•์ค‘ ํ•˜๋‚˜๋กœ์จ, ์‹œ์ž‘์  ๋ถ€ํ„ฐ ๋‹ค์Œ ๋ถ„๊ธฐ(branch)๋กœ ๋„˜์–ด๊ฐ€๊ธฐ ์ „์— ํ•ด๋‹น ๋ถ„๊ธฐ๋ฅผ ์™„๋ฒฝํ•˜๊ฒŒ ํƒ์ƒ‰ํ•˜๊ณ  ๋„˜์–ด๊ฐ€๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. ๋จผ์ € ๋ณด์ด๋Š” ๋…ธ๋“œ๋ถ€ํ„ฐ ๊ณ„์†ํ•ด์„œ ๊นŠ์ด๋ฅผ ๋Š˜๋ ค๊ฐ€๋ฉฐ ํƒ์ƒ‰ํ•˜๊ณ , ๋” ์ด์ƒ ํƒ์ƒ‰ํ•  ๋…ธ๋“œ๊ฐ€ ์—†๋‹ค๋ฉด ์ด์ „ ๋…ธ๋“œ๋กœ ๋Œ์•„๊ฐ€์„œ ๋‹ค๋ฅธ ๋ธŒ๋žœ์น˜๋ฅผ ๋‹ค์‹œ ๊นŠ์ด ํŒŒ๋ณด๋Š” ํ˜•์‹์„ ๋งํ•œ๋‹ค. Stack์ด๋‚˜ ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด์„œ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ, ์žฌ๊ท€ํ•จ์ˆ˜๊ฐ€ ๊ตฌํ˜„์ด ๊ฐ„ํŽธํ•˜๋‹ค.

  • ์žฅ์ 
    • ํ˜„์žฌ ๊ฒฝ๋กœ ์ƒ์˜ ๋…ธ๋“œ๋“ค๋งŒ ๊ธฐ์–ตํ•˜๋ฉด ๋˜๋ฏ€๋กœ, ์ €์žฅ ๊ณต๊ฐ„์˜ ์ˆ˜์š”๊ฐ€ ๋น„๊ต์  ์ ๋‹ค.
    • ๋ชฉํ‘œ ๋…ธ๋“œ๊ฐ€ ๊นŠ์€ ๋‹จ๊ณ„์— ์žˆ๋Š” ๊ฒฝ์šฐ์—๋„ ํ•ด๋ฅผ ๋นจ๋ฆฌ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.
    • ๊ตฌํ˜„์ด ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(BFS) ๋ณด๋‹ค ๊ฐ„๋‹จํ•˜๋‹ค.
  • ๋‹จ์ 
    • ๋‹จ์ˆœ ๊ฒ€์ƒ‰ ์†๋„๋Š” ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(BFS) ๋ณด๋‹ค ๋Š๋ฆฌ๋‹ค.
    • ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์€ ํ•ด๋ฅผ ๊ตฌํ•˜๋ฉด ํƒ์ƒ‰์ด ์ข…๋ฃŒ๋˜๋ฏ€๋กœ, ๊ตฌํ•œ ํ•ด๊ฐ€ ์ตœ๋‹จ ๊ฒฝ๋กœ๊ฐ€ ๋œ๋‹ค๋Š” ๋ณด์žฅ์ด ์—†๋‹ค. ๋ชฉํ‘œ์— ์ด๋ฅด๋Š” ๊ฒฝ๋กœ๊ฐ€ ๋‹ค์ˆ˜์ธ ๊ฒฝ์šฐ, DFS๋ฅผ ํ†ตํ•ด ๊ตฌํ•œ ํ•ด๊ฐ€ ์ตœ์ ์ด ์•„๋‹ ์ˆ˜ ์žˆ๋‹ค. DFS๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š”, ๋ชจ๋“  ๊ฒฝ๋กœ๋ฅผ ์ „๋ถ€ ํ™•์ธํ•ด๋ณด์•„์•ผ ํ•œ๋‹ค.

BFS์™€ DFS์˜ ํƒ์ƒ‰ ์ˆœ์„œ

์ฃผ์˜ํ•ด์•ผํ•  ๊ฒƒ

๋…ธ๋“œ๋ฅผ Queue ํ˜น์€ Stack์— ๋„ฃ์„ ๋•Œ, ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ๋ฐ˜๋“œ์‹œ ํ‘œ์‹œํ•ด์ฃผ์–ด์•ผ ํ•œ๋‹ค. ๊ทธ๋ ‡์ง€ ์•Š์œผ๋ฉด, ์ž๋ฃŒ๊ตฌ์กฐ์— ๋…ธ๋“œ๊ฐ€ ์ค‘๋ณต๋˜๊ฒŒ ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ๋ฐฉ๋ฌธ ํ‘œ์‹œ๋ฅผ ํ•˜์ง€ ์•Š์œผ๋ฉด, ์‹ฌํ•œ ๊ฒฝ์šฐ์—๋Š” ๋ฌดํ•œ๋ฃจํ”„์— ๋น ์งˆ ์ˆ˜๋„ ์žˆ๋‹ค.

References


#6-2

Shortest Path

ํ•œ ๋…ธ๋“œ์—์„œ ๋‹ค๋ฅธ ๋…ธ๋“œ๋กœ ๊ฐ€๋Š” ์—ฃ์ง€์— cost ๊ฐ€ ์žˆ๋Š” ๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ํ•œ ์ง€์  โ†’ ๋ชฉํ‘œ ์ง€์  ๋˜๋Š” ๋ชจ๋“  ์ง€์  โ†’ ๋ชจ๋“  ์ง€์ ๊นŒ์ง€ cost ๊ฐ€ ๊ฐ€์žฅ ์ ๊ฒŒ ๋“œ๋Š” ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ฐพ๋Š” ๋ฌธ์ œ์ด๋‹ค.

๋Œ€ํ‘œ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ Dijkstra, Floyd-Warshall, Bellman-Ford ๊ฐ€ ์žˆ๋‹ค.

#6-2-1

Dijkstra

ํ•œ ๋…ธ๋“œ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ๋…ธ๋“œ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ์ตœ๋‹จ ๊ฒฝ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•œ๋‹ค. ๋‹จ, cost (๊ฑฐ๋ฆฌ) ๋Š” ๋ฐ˜๋“œ์‹œ ์Œ์ˆ˜๊ฐ€ ์—†์–ด์•ผ ํ•œ๋‹ค. ์ด๋Ÿฌํ•œ ํŠน์„ฑ ๋•Œ๋ฌธ์— GPS ๊ธธ์ฐพ๊ธฐ ๋“ฑ์— ์‘์šฉ๋œ๋‹ค.

๊ธฐ๋ณธ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ถœ๋ฐœ ๋…ธ๋“œ์—์„œ ๋‹ค๋ฅธ ๋…ธ๋“œ๋กœ ๊ฐ€๋Š” ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ธฐ๋กํ•˜๋Š” ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ํ…Œ์ด๋ธ”๊ณผ ํ•ด๋‹น ๋…ธ๋“œ ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ์‚ดํ”ผ๋Š” visited ํ…Œ์ด๋ธ”์„ ์‚ฌ์šฉํ•œ๋‹ค.

๋™์ž‘ ๋ฐฉ์‹

์ตœ๋‹จ ๊ฑฐ๋ฆฌ ํ…Œ์ด๋ธ”์— ์ถœ๋ฐœ ๋…ธ๋“œ๋Š” 0, ๋‚˜๋จธ์ง€ ๋…ธ๋“œ๋Š” INF ๋กœ ์ดˆ๊ธฐํ™”ํ•œ๋‹ค.

  1. ๋จผ์ € ์ถœ๋ฐœ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธ(visited[start] = True)ํ•˜๊ณ  ์ถœ๋ฐœ ๋…ธ๋“œ์—์„œ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋‹ค๋ฅธ ๋…ธ๋“œ๋“ค๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ๋ฅผ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ํ…Œ์ด๋ธ”์— ๊ธฐ๋กํ•œ๋‹ค.
  2. ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ํ…Œ์ด๋ธ”์„ ๋ณด๊ณ  ๊ฐ€์žฅ ๊ฑฐ๋ฆฌ๊ฐ€ ์งง์€ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•œ๋‹ค(visited์— ๊ธฐ๋ก).
  3. ํ•ด๋‹น ๋…ธ๋“œ์™€ ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ ์ค‘ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ์— ๋Œ€ํ•ด ํ˜„์žฌ๊นŒ์ง€ ๊ฑฐ๋ฆฌ + ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ๊นŒ์ง€ ๊ฑฐ๋ฆฌ๊ฐ€ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ํ…Œ์ด๋ธ”์˜ ๊ฑฐ๋ฆฌ๋ณด๋‹ค ์งง๋‹ค๋ฉด ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ํ…Œ์ด๋ธ”์„ ๊ฐฑ์‹ ํ•œ๋‹ค.
  4. ๋ชจ๋“  ๋…ธ๋“œ์— ๋ฐฉ๋ฌธํ•  ๋•Œ๊นŒ์ง€ 2 ์™€ 3 ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค.

์œ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” $O(V^2)$ ($V$ : ๋…ธ๋“œ ๊ฐœ์ˆ˜) ์ด๋‹ค. ๋ชจ๋“  ๋…ธ๋“œ์— ๋Œ€ํ•ด ๋ฐฉ๋ฌธํ•˜๊ณ  ํ…Œ์ด๋ธ”์„ ๋ชจ๋‘ ์‚ดํŽด๋ณด๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ์ด๋ฅผ ๊ฐœ์„ ํ•˜๊ธฐ ์œ„ํ•ด ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ์„ ๋•Œ ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์‚ฌ์šฉํ•˜๊ณ  ํ์—์„œ ๊บผ๋‚ธ ๊ฑฐ๋ฆฌ๋ณด๋‹ค ์ตœ๋‹จ๊ฑฐ๋ฆฌ ํ…Œ์ด๋ธ”์˜ ๊ฐ’์ด ๋” ์ž‘๋‹ค๋ฉด ๋ฐฉ๋ฌธํ•œ ๊ฒƒ์œผ๋กœ ๊ฐ„์ฃผํ•œ๋‹ค. ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์‚ฌ์šฉํ•œ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” $O(ElogV)$ ($V$: ๋…ธ๋“œ ๊ฐœ์ˆ˜, $E$: ์—ฃ์ง€ ๊ฐœ์ˆ˜) ์ด๋‹ค.

    import heapq
    import sys
    input = sys.stdin.readline
    INF = int(1e9)

    # ๋…ธ๋“œ ๊ฐœ์ˆ˜, ๊ฐ„์„  ๊ฐœ์ˆ˜ ์ž…๋ ฅ๋ฐ›๊ธฐ
    n, m = map(int, input().split())
    # ์‹œ์ž‘ ๋…ธ๋“œ ๋ฒˆํ˜ธ ์ž…๋ ฅ๋ฐ›๊ธฐ
    start = int(input())
    # ๊ฐ ๋…ธ๋“œ์— ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๋…ธ๋“œ์— ๋Œ€ํ•œ ์ •๋ณด๋ฅผ ๋‹ด๋Š” ๋ฆฌ์ŠคํŠธ ๋งŒ๋“ค๊ธฐ
    graph = [[] for i in range(n+1)]
    # ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ํ…Œ์ด๋ธ”์„ ๋ชจ๋‘ ๋ฌดํ•œ์œผ๋กœ ์ดˆ๊ธฐํ™”
    distance = [INF] * (n+1)

    # ๋ชจ๋“  ๊ฐ„์„  ์ •๋ณด ์ž…๋ ฅ๋ฐ›๊ธฐ
    for _ in range(m):
    	a, b, c = map(int, input().split())
    	# a ๋ฒˆ ๋…ธ๋“œ์—์„œ b ๋ฒˆ ๋…ธ๋“œ๋กœ ๊ฐ€๋Š” ๋น„์šฉ์ด c ๋ผ๋Š” ์˜๋ฏธ
    	graph[a].append((b, c))

    def dijkstra(start):
    	q = []
    	# ์‹œ์ž‘ ๋…ธ๋“œ๋กœ ๊ฐ€๊ธฐ ์œ„ํ•œ ์ตœ๋‹จ ๊ฒฝ๋กœ๋Š” 0 ์œผ๋กœ ์„ค์ •ํ•˜์—ฌ, ํ์— ์‚ฝ์ž…
    	heapq.heappush(q, (0, start))
    	distance[start] = 0
    	while q: # ํ๊ฐ€ ๋น„์–ด์žˆ์ง€ ์•Š๋‹ค๋ฉด
    		# ๊ฐ€์žฅ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๊ฐ€ ์งง์€ ๋…ธ๋“œ์— ๋Œ€ํ•œ ์ •๋ณด ๊บผ๋‚ด๊ธฐ
    		dist, now = heapq.heappop(q)
    		# ํ˜„์žฌ ๋…ธ๋“œ๊ฐ€ ์ด๋ฏธ ์ฒ˜๋ฆฌ๋œ ์ ์ด ์žˆ๋Š” ๋…ธ๋“œ๋ฉด ๋ฌด์‹œ
    		if distance[now] < dist:
    			continue
    		# ํ˜„์žฌ ๋…ธ๋“œ์™€ ์—ฐ๊ฒฐ๋œ ๋‹ค๋ฅธ ์ธ์ ‘ํ•œ ๋…ธ๋“œ๋“ค์„ ํ™•์ธ
    		for to_other in graph[now]:
    			cost = dist + to_other[1]
    			if distance[to_other[0]] > cost:
    				distance[to_other[0]] = cost
    				heapq.heappush(q, (cost, to_other[0]))

    # ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜ํ–‰
    dijkstra(start)

    # ๋ชจ๋“  ๋…ธ๋“œ๋กœ ๊ฐ€๊ธฐ ์œ„ํ•œ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถœ๋ ฅ
    for i in range(1, n+1):
    	# ๋„๋‹ฌํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ, ๋ฌดํ•œ์œผ๋กœ ์ถœ๋ ฅ
    	if distance[i] == INF:
    		print("INFINITY")
 	else:
 		print(distance[i])

References


#6-2-2

Floyd-Warshall

๋ชจ๋“  ์ง€์ ์—์„œ ๋ชจ๋“  ์ง€์ ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

A โ†’ B ๋ฅผ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•  ๋•Œ, ํŠน์ • ๋…ธ๋“œ X ๋ฅผ ์ค‘๊ฐ„์— ๊ฑฐ์ณ ๊ฐ€๋Š” ๊ฐ’๊ณผ ๊ธฐ์กด์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ ํ…Œ์ด๋ธ” ๊ฐ’ ์ค‘ ์–ด๋Š ๊ฒƒ์ด ์งง์€์ง€ ๋น„๊ตํ•˜๋Š” ๊ฒƒ์ด ํ•ต์‹ฌ์ด๋‹ค. ์ด ๊ณผ์ •์—์„œ X ๋ฅผ ๋ชจ๋“  ๋…ธ๋“œ๋กœ ๋ฐ”๊ฟ”๊ฐ€๋ฉฐ ์ง„ํ–‰ํ•˜๋ฉด ๋œ๋‹ค.

๋ชจ๋“  ๋…ธ๋“œ์— ๋Œ€ํ•ด ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ ๊ฑฐ์ณ ๊ฐ€๋Š” ๊ฒฝ์šฐ๋ฅผ ๊ณ„์‚ฐํ•˜๋ฏ€๋กœ ํ”Œ๋กœ์ด๋“œ-์›Œ์…œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” $O(V^3)$($V$: ๋…ธ๋“œ ๊ฐœ์ˆ˜)์ด๋‹ค.

๋‹ค์ต์ŠคํŠธ๋ผ๊ฐ€ ๊ทธ๋ฆฌ๋””ํ•œ ๋ฐฉ์‹์ด์—ˆ๋‹ค๋ฉด, ํ”Œ๋กœ์ด๋“œ-์›Œ์…œ์€ ์ ํ™”์‹์„ ํ†ตํ•ด ํ…Œ์ด๋ธ”์„ ๊ฐฑ์‹ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— DP ๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๋ฐฉ์‹์ด๋‹ค.

$$ D_{ab} = min(D_{ab}, D_{ak} + D_{kb}) $$

INF = int(1e9) # ๋ฌดํ•œ์„ ์˜๋ฏธํ•˜๋Š” ๊ฐ’์œผ๋กœ 10 ์–ต์„ ์„ค์ •

# ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜ ๋ฐ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ž…๋ ฅ๋ฐ›๊ธฐ
n = int(input())
m = int(input())
# 2 ์ฐจ์› ๋ฆฌ์ŠคํŠธ (๊ทธ๋ž˜ํ”„ ํ‘œํ˜„) ๋ฅผ ๋งŒ๋“ค๊ณ , ๋ชจ๋“  ๊ฐ’์„ ๋ฌดํ•œ์œผ๋กœ ์ดˆ๊ธฐํ™”
graph = [[INF] * (n+1) for _ in range(n+1)]

# ์ž๊ธฐ ์ž์‹ ์—์„œ ์ž๊ธฐ ์ž์‹ ์œผ๋กœ ๊ฐ€๋Š” ๋น„์šฉ์€ 0 ์œผ๋กœ ์ดˆ๊ธฐํ™”
for i in range(1, n+1):
	graph[i][i] = 0

# ๊ฐ ๊ฐ„์„ ์— ๋Œ€ํ•œ ์ •๋ณด๋ฅผ ์ž…๋ ฅ๋ฐ›์•„, ๊ทธ ๊ฐ’์œผ๋กœ ์ดˆ๊ธฐํ™”
for _ in range(m):
	# A ์—์„œ B ๋กœ ๊ฐ€๋Š” ๋น„์šฉ์€ C ๋ผ๊ณ  ์„ค์ •
	a, b, c = map(int, input().split())
	graph[a][b] = c

# ์ ํ™”์‹์— ๋”ฐ๋ผ ํ”Œ๋กœ์ด๋“œ ์›Œ์…œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ˆ˜ํ–‰
for k in range(1, n+1):
	for a in range(1, n+1):
		for b in range(1, n+1):
			graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# ์ˆ˜ํ–‰๋œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅ
for a in range(1, n+1):
	for b in range(1, n+1):
		# ๋„๋‹ฌํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ, ๋ฌดํ•œ์œผ๋กœ ์ถœ๋ ฅ
		if graph[a][b] == INF:
			print("INFINITY")
		else:
			print(graph[a][b], end = ' ')
	print()

References


#6-2-3

Bellman-Ford

๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๊ฐ„์„ ์ด ์Œ์ˆ˜์ธ ๊ฒฝ์šฐ ์Œ์ˆ˜ ์‚ฌ์ดํด์— ๋น ์งˆ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๋‹ค. ๋ฒจ๋งŒ ํฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜๋ฉด ์Œ์ˆ˜ ์‚ฌ์ดํด์„ ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค.

๊ธฐ๋ณธ์ ์ธ ๊ฐœ๋…์€ ๋ชจ๋“  ์—ฃ์ง€๋ฅผ ๊ฑฐ์น˜๋ฉด์„œ ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ๋Š” ๊ฒƒ์ด๋‹ค. ์ด ์ž‘์—…์„ ๋ชจ๋“  ๋…ธ๋“œ์— ๋Œ€ํ•ด ์ง„ํ–‰ํ•œ๋‹ค. ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” $O(VE)$($V$: ๋…ธ๋“œ ๊ฐœ์ˆ˜, $E$: ์—ฃ์ง€ ๊ฐœ์ˆ˜) ์ด๋‹ค.

  1. ์ถœ๋ฐœ ๋…ธ๋“œ๋ฅผ ์„ค์ •ํ•œ๋‹ค.
  2. ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ํ…Œ์ด๋ธ”์„ ์ถœ๋ฐœ ๋…ธ๋“œ๋Š” 0 ๋‚˜๋จธ์ง€๋Š” INF ๋กœ ์ดˆ๊ธฐํ™”ํ•œ๋‹ค.
  3. ๋ชจ๋“  $E$๋ฅผ ํ™•์ธํ•˜๋ฉฐ ํ…Œ์ด๋ธ” ๊ฐ’๋ณด๋‹ค (ํ˜„์žฌ ๋…ธ๋“œ ์ตœ๋‹จ๊ฑฐ๋ฆฌ + ํ˜„์žฌ๋…ธ๋“œ์—์„œ ํ•ด๋‹น ๋…ธ๋“œ๋กœ ๊ฐ€๋Š” ๊ฑฐ๋ฆฌ)๊ฐ€ ์ž‘๋‹ค๋ฉด ํ…Œ์ด๋ธ”์„ ๊ฐฑ์‹ ํ•˜๋Š” ๊ฒƒ์„ $V-1$๋ฒˆ ๋ฐ˜๋ณตํ•œ๋‹ค.

์ดํ›„ ์Œ์ˆ˜ ์‚ฌ์ดํด์„ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” 3์˜ ๊ณผ์ •์„ ํ•œ ๋ฒˆ๋งŒ ๋” ์ˆ˜ํ–‰ํ•œ๋‹ค. ์ด ๋•Œ, ํ…Œ์ด๋ธ”์ด ๊ฐฑ์‹ ๋œ๋‹ค๋ฉด ์Œ์ˆ˜ ์‚ฌ์ดํด์ด ์žˆ๋Š” ๊ฒƒ์ด๋‹ค.

๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ตœ์ ์˜ ํ•ด๋ฅผ ์ฐพ๋Š”๋ฐ ๋น„ํ•ด, ๋ฒจ๋งŒ ํฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ชจ๋“  ๊ฐ„์„ ์„ ๋ชจ๋“  ๋…ธ๋“œ ๊ฐœ์ˆ˜๋งŒํผ ๋ฐ˜๋ณตํ•˜๋Š” ์ ์—์„œ ๋น„ํšจ์œจ์ ์ด๋‹ค. ํ•˜์ง€๋งŒ ์Œ์ˆ˜ ์‚ฌ์ดํด์„ ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ๋Š” ์ ์ด ํŠน์ง•์ด๋‹ค.

import sys
input = sys.input.readline
INF = int(1e9)

def bf(start):
  dist[start] = 0
  for i in range(n):
    for j in range(m):
      cur = edges[j][0]
      next_node = edges[j][1]
      cost = edges[j][2]
      if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
        dist[next_node] = dist[cur] + cost
        if i == n - 1:
          return True
  return False

n, m = map(int, input().split())
edges = []
dist = [INF] * (n+1)

for _ in range(m):
  a, b, c = map(int, input().split())
  edges.append(a, b, c)

start = 1
negative_cycle = bf(start)

if negative_cycle:
  print("negative cycle")
else:
  for i in range(2, n+1):
    if dist[i] == INF:
      print("INF")
    else:
      print(dist[i])

References


#6-3

Minimum Spanning Tree

Spanning Tree

Spanning Tree(์‹ ์žฅ ํŠธ๋ฆฌ)๋ž€ ๊ทธ๋ž˜ํ”„์—์„œ ์ผ๋ถ€ ๊ฐ„์„ ์„ ์„ ํƒํ•ด์„œ ๋งŒ๋“ , ๊ทธ๋ž˜ํ”„ ๋‚ด์˜ ๋ชจ๋“  ์ •์ ์„ ํฌํ•จํ•˜๋Š” ํŠธ๋ฆฌ๋ฅผ ๋งํ•œ๋‹ค.

Spanning Tree๋Š” ๊ทธ๋ž˜ํ”„์˜ ์ตœ์†Œ ์—ฐ๊ฒฐ ๋ถ€๋ถ„ ๊ทธ๋ž˜ํ”„ ์ด๋‹ค. ์ตœ์†Œ ์—ฐ๊ฒฐ์˜ ์˜๋ฏธ๋Š” ๊ฐ„์„ ์˜ ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ์ ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. n๊ฐœ์˜ ์ •์ ์„ ๊ฐ€์ง€๋Š” ๊ทธ๋ž˜ํ”„๊ฐ€ ๋ชจ๋‘ ์ด์–ด์ง€๊ธฐ ์œ„ํ•ด์„œ๋Š” ์ตœ์†Œ (n-1)๊ฐœ์˜ ๊ฐ„์„ ์ด ํ•„์š”ํ•˜๋‹ค. n๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง€๋Š” ๊ทธ๋ž˜ํ”„์—์„œ (n-1)๊ฐœ์˜ ๊ฐ„์„ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์œผ๋ฉด ํ•„์—ฐ์ ์œผ๋กœ ํŠธ๋ฆฌ ํ˜•ํƒœ๊ฐ€ ๋˜๊ณ , ์ด๋ฅผ spanning tree๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค. ๋˜ํ•œ, ํŠธ๋ฆฌ ํ˜•์‹์„ ๋งŒ์กฑํ•ด์•ผํ•˜๋ฏ€๋กœ ์‚ฌ์ดํด์„ ํฌํ•จํ•ด์„œ๋Š” ์•ˆ๋œ๋‹ค. DFS, BFS์„ ํ†ตํ•ด ํƒ์ƒ‰ ๋„์ค‘์— ์‚ฌ์šฉ๋œ ๊ฐ„์„ ๋งŒ ๋ชจ์•„์„œ ์ด์–ด์ฃผ๋ฉด, ๊ทธ๋ž˜ํ”„์—์„œ ์‹ ์žฅ ํŠธ๋ฆฌ๋ฅผ ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค. ํ•˜๋‚˜์˜ ๊ทธ๋ž˜ํ”„์—๋Š” ๋งŽ์€ ์‹ ์žฅ ํŠธ๋ฆฌ๊ฐ€ ์กด์žฌํ•  ์ˆ˜ ์žˆ๋‹ค.

Minimum Spanning Tree

MST(Minimum Spanning Tree, ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ)๋ž€ Spanning Tree ์ค‘์—์„œ ์‚ฌ์šฉ๋œ ๊ฐ„์„ ๋“ค์˜ ๊ฐ€์ค‘์น˜ ํ•ฉ์ด ์ตœ์†Œ์ธ ํŠธ๋ฆฌ๋ฅผ ๋งํ•œ๋‹ค.

MST๋Š” ๊ฐ„์„ ์— ๊ฐ€์ค‘์น˜๋ฅผ ๊ณ ๋ คํ•˜์—ฌ ์ตœ์†Œ ๋น„์šฉ์˜ Spanning Tree๋ฅผ ์„ ํƒํ•˜๋Š” ๊ฒƒ์„ ๋งํ•œ๋‹ค. ์ฆ‰, ๋„คํŠธ์›Œํฌ(๊ฐ€์ค‘์น˜๋ฅผ ๊ฐ„์„ ์— ํ• ๋‹นํ•œ ๊ทธ๋ž˜ํ”„)์— ์žˆ๋Š” ๋ชจ๋“  ์ •์ ๋“ค์„ ๊ฐ€์žฅ ์ ์€ ์ˆ˜์˜ ๊ฐ„์„ ๊ณผ ๋น„์šฉ์œผ๋กœ ์—ฐ๊ฒฐํ•˜๋Š” ๊ฒƒ์ด๋‹ค. MST๋Š” ๊ฐ„์„ ์˜ ๊ฐ€์ค‘์น˜์˜ ํ•ฉ์ด ์ตœ์†Œ์—ฌ์•ผ ํ•œ๋‹ค๋Š” ํŠน์ง•์ด ์žˆ๋‹ค. ์ด ์™ธ์—๋„ "n๊ฐœ์˜ ์ •์ ์„ ๊ฐ€์ง€๋Š” ๊ทธ๋ž˜ํ”„์— ๋Œ€ํ•ด ๋ฐ˜๋“œ์‹œ (n-1)๊ฐœ์˜ ๊ฐ„์„ ๋งŒ์„ ์‚ฌ์šฉํ•ด์•ผ ํ•œ๋‹ค"๊ฑฐ๋‚˜ "์‚ฌ์ดํด์ด ํฌํ•จ๋˜์–ด์„œ๋Š” ์•ˆ๋œ๋‹ค"๋Š” ๋“ฑ์˜ spanning tree์˜ ํŠน์ง•๋„ ํฌํ•จํ•œ๋‹ค.

MST๋ฅผ ๊ตฌํ˜„ํ•˜๊ธฐ ์œ„ํ•ด์„œ Kruskal MST ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ˜น์€ Prim ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์‚ฌ์šฉ๋œ๋‹ค. ๊ทธ๋ž˜ํ”„ ๋‚ด์— ์ ์€ ์ˆซ์ž์˜ ๊ฐ„์„ ๋งŒ์„ ๊ฐ€์ง€๋Š” ํฌ์†Œ ๊ทธ๋ž˜ํ”„(Sparse Graph)์˜ ๊ฒฝ์šฐ Kruskal ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ ํ•ฉํ•˜๊ณ , ๊ทธ๋ž˜ํ”„์— ๊ฐ„์„ ์ด ๋งŽ์ด ์กด์žฌํ•˜๋Š” ๋ฐ€์ง‘ ๊ทธ๋ž˜ํ”„(Dense Graph) ์˜ ๊ฒฝ์šฐ๋Š” Prim ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ ํ•ฉํ•˜๋‹ค.

References


#6-3-1

Prim

Prim ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€ ์‹œ์ž‘ ์ •์ ์—์„œ๋ถ€ํ„ฐ ์ถœ๋ฐœํ•˜์—ฌ ์‹ ์žฅํŠธ๋ฆฌ ์ง‘ํ•ฉ์„ ๋‹จ๊ณ„์ ์œผ๋กœ ํ™•์žฅํ•ด๋‚˜๊ฐ€๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. ์ •์  ์„ ํƒ์„ ๊ธฐ๋ฐ˜์œผ๋กœ ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ฉฐ, ์ด์ „ ๋‹จ๊ณ„์—์„œ ๋งŒ๋“ค์–ด์ง„ ์‹ ์žฅ ํŠธ๋ฆฌ๋ฅผ ํ™•์žฅํ•˜๋ฉด์„œ ๋‚˜์•„๊ฐ€๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. Prim ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๋™์ž‘๋ฐฉ๋ฒ•์€ ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

  • ์‹œ์ž‘ ๋‹จ๊ณ„์—์„œ๋Š” ์‹œ์ž‘ ์ •์ ๋งŒ์ด MST(์ตœ์†Œ ๋น„์šฉ ์‹ ์žฅ ํŠธ๋ฆฌ) ์ง‘ํ•ฉ์— ํฌํ•จ๋œ๋‹ค.
  • ์•ž ๋‹จ๊ณ„์—์„œ ๋งŒ๋“ค์–ด์ง„ MST ์ง‘ํ•ฉ์— ์ธ์ ‘ํ•œ ์ •์ ๋“ค ์ค‘์—์„œ ์ตœ์†Œ ๊ฐ„์„ ์œผ๋กœ ์—ฐ๊ฒฐ๋œ ์ •์ ์„ ์„ ํƒํ•˜์—ฌ ํŠธ๋ฆฌ๋ฅผ ํ™•์žฅํ•œ๋‹ค.
  • ์ฆ‰, ๊ฐ€์žฅ ๋‚ฎ์€ ๊ฐ€์ค‘์น˜๋ฅผ ๋จผ์ € ์„ ํƒํ•œ๋‹ค.
  • ์œ„์˜ ๊ณผ์ •์„ ํŠธ๋ฆฌ๊ฐ€ (N-1)๊ฐœ์˜ ๊ฐ„์„ ์„ ๊ฐ€์งˆ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•œ๋‹ค.

Prim ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š”, ์ฃผ ๋ฐ˜๋ณต๋ฌธ์ด ์ •์ ์˜ ์ˆ˜ n๋งŒํผ ๋ฐ˜๋ณตํ•˜๊ณ , ๋‚ด๋ถ€ ๋ฐ˜๋ณต๋ฌธ์ด n๋ฒˆ ๋ฐ˜๋ณต๋˜๋ฏ€๋กœ, $O(n^2)$์ด๋‹ค.

Prim ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ˆ˜ํ–‰ ๋‹จ๊ณ„

References


#6-3-2

Kruskal

Kruskal ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€ ๊ฐ„์„  ์„ ํƒ์„ ๊ธฐ๋ฐ˜์œผ๋กœ ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ, ์ด์ „ ๋‹จ๊ณ„์—์„œ ๋งŒ๋“ค์–ด์ง„ ์‹ ์žฅ ํŠธ๋ฆฌ์™€๋Š” ์ƒ๊ด€์—†์ด ๋ฌด์กฐ๊ฑด ์ตœ์†Œ ๊ฐ„์„ ๋งŒ์„ ์„ ํƒํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. ๋งค ๋‹จ๊ณ„๋งˆ๋‹ค ์‚ฌ์ดํด์„ ๋งŒ๋“ค์ง€ ์•Š๋Š” ์ตœ์†Œ ๊ฐ„์„ ์„ ์ฑ„ํƒํ•˜๋ฉด ๋œ๋‹ค.

Kruskal ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํƒ์š•์ ์ธ ๋ฐฉ๋ฒ•(greedy method)์„ ์ด์šฉํ•˜์—ฌ, ๋„คํŠธ์›Œํฌ(๊ฐ€์ค‘์น˜๋ฅผ ๊ฐ„์„ ์— ํ• ๋‹นํ•œ ๊ทธ๋ž˜ํ”„)์˜ ๋ชจ๋“  ์ •์ ์„ ์ตœ์†Œ ๋น„์šฉ์œผ๋กœ ์—ฐ๊ฒฐํ•˜๋Š” ์ตœ์  ํ•ด๋‹ต์„ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. MST(์ตœ์†Œ ๋น„์šฉ ์‹ ์žฅ ํŠธ๋ฆฌ)๊ฐ€ ์ตœ์†Œ ๋น„์šฉ์˜ ๊ฐ„์„ ์œผ๋กœ ๊ตฌ์„ฑ๋˜๋ฉฐ, ์‚ฌ์ดํด์„ ํฌํ•จํ•˜์ง€ ์•Š๋Š”๋‹ค๋Š” ์กฐ๊ฑด์— ๊ทผ๊ฑฐํ•˜์—ฌ, ์ตœ์ ํ•ด๋ฅผ ๋ณด์žฅํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ฐ ๋‹จ๊ณ„์—์„œ ์‚ฌ์ดํด์„ ์ด๋ฃจ์ง€ ์•Š๋Š” ์ตœ์†Œ ๋น„์šฉ ๊ฐ„์„ ์„ ์„ ํƒํ•˜๋ฉด ๋œ๋‹ค.

์ฃผ์˜ํ•  ์ ์€ ๋‹ค์Œ ๊ฐ„์„ ์„ ์ด๋ฏธ ์„ ํƒ๋œ ๊ฐ„์„ ๋“ค์˜ ์ง‘ํ•ฉ์— ์ถ”๊ฐ€ํ•  ๋•Œ ์‚ฌ์ดํด์„ ์ƒ์„ฑํ•˜๋Š”์ง€๋ฅผ ์ฒดํฌํ•ด์•ผ ํ•œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ์ƒˆ๋กœ์šด ๊ฐ„์„ ์ด ์ด๋ฏธ ๋‹ค๋ฅธ ๊ฒฝ๋กœ์— ์˜ํ•ด ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ •์ ๋“ค์„ ์—ฐ๊ฒฐํ•  ๋•Œ ์‚ฌ์ดํด์ด ํ˜•์„ฑ๋œ๋‹ค. ์ฆ‰, ์ถ”๊ฐ€ํ•  ์ƒˆ๋กœ์šด ๊ฐ„์„ ์˜ ์–‘๋ ์ •์ ์ด ๊ฐ™์€ ์ง‘ํ•ฉ์— ์†ํ•ด ์žˆ์œผ๋ฉด, ์‚ฌ์ดํด์ด ํ˜•์„ฑ๋œ๋‹ค. ๋”ฐ๋ผ์„œ, ์ถ”๊ฐ€ํ•˜๊ณ ์ž ํ•˜๋Š” ๊ฐ„์„ ์˜ ์–‘๋ ์ •์ ์ด ๊ฐ™์€ ์ง‘ํ•ฉ์— ์†ํ•ด ์žˆ๋Š”์ง€๋ฅผ ๋จผ์ € ๊ฒ€์‚ฌํ•ด์•ผ ํ•˜๊ณ , ์ด๋•Œ union-find ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜์—ฌ ๊ฒ€์‚ฌํ•  ์ˆ˜ ์žˆ๋‹ค.

Kruskal ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๋™์ž‘๋ฐฉ๋ฒ•์€ ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

  • ๊ทธ๋ž˜ํ”„์˜ ๊ฐ„์„ ๋“ค์„ ๊ฐ€์ค‘์น˜์˜ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค.
  • ์ •๋ ฌ๋œ ๊ฐ„์„  ๋ฆฌ์ŠคํŠธ์—์„œ ์ˆœ์„œ๋Œ€๋กœ ์‚ฌ์ดํด์„ ํ˜•์„ฑํ•˜์ง€ ์•Š๋Š” ๊ฐ„์„ ์„ ์„ ํƒํ•œ๋‹ค.
  • ์ฆ‰, ๊ฐ€์žฅ ๋‚ฎ์€ ๊ฐ€์ค‘์น˜๋ฅผ ๋จผ์ € ์„ ํƒํ•œ๋‹ค.
  • ์‚ฌ์ดํด์„ ํ˜•์„ฑํ•˜๋Š” ๊ฐ„์„ ์„ ์ œ์™ธํ•œ๋‹ค.
  • ํ•ด๋‹น ๊ฐ„์„ ์„ ํ˜„์žฌ์˜ MST(์ตœ์†Œ ๋น„์šฉ ์‹ ์žฅ ํŠธ๋ฆฌ)์˜ ์ง‘ํ•ฉ์— ์ถ”๊ฐ€ํ•œ๋‹ค.

Kruskal ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” $O(e \log_2 e)$์ด๋‹ค.

Kruskal ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜ํ–‰ ๋‹จ๊ณ„

References


#6-4

Union-find

์œ ๋‹ˆ์˜จ-ํŒŒ์ธ๋“œ(Union-find) ํ˜น์€ ์„œ๋กœ์†Œ ์ง‘ํ•ฉ(Disjoint Sets) ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ์„œ๋กœ์†Œ ๋ถ€๋ถ„ ์ง‘ํ•ฉ๋“ค๋กœ ๋‚˜๋ˆ ์ง„ ์›์†Œ๋“ค์— ๋Œ€ํ•œ ์ •๋ณด๋ฅผ ๋‹ค๋ฃจ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. ์œ ๋‹ˆ์˜จ-ํŒŒ์ธ๋“œ ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ํ•ฉ์ง‘ํ•ฉ(Union)๊ณผ ์ฐพ๊ธฐ(Find) ์—ฐ์‚ฐ์„ ์ œ๊ณตํ•œ๋‹ค.

  • ํ•ฉ์ง‘ํ•ฉ(Union): ๋‘ ๊ฐœ์˜ ์ง‘ํ•ฉ์„ ํ•˜๋‚˜์˜ ์ง‘ํ•ฉ์œผ๋กœ ํ•ฉ์นœ๋‹ค.
    • ์„œ๋กœ ์—ฐ๊ฒฐํ•  ๋‘ ๋…ธ๋“œ A, B๊ฐ€ ์žˆ๋‹ค๊ณ  ํ•  ๋•Œ, A์™€ B์˜ ๋ฃจํŠธ ๋…ธ๋“œ์ธ A'๊ณผ B'์„ ์ฐพ๋Š”๋‹ค.
    • A'์„ B'์˜ ๋ถ€๋ชจ ๋…ธ๋“œ๋กœ ํ˜น์€ B'์„ A'์„ ๋ถ€๋ชจ ๋…ธ๋“œ๋กœ ์„ค์ •ํ•œ๋‹ค.
  • ์ฐพ๊ธฐ(Find): ๋…ธ๋“œ๊ฐ€ ์†ํ•œ ์ง‘ํ•ฉ์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

๊ตฌํ˜„ ๋ฐฉ๋ฒ•์€ ๊ฐœ์„ ๋œ ์„œ๋กœ์†Œ ์ง‘ํ•ฉ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (๊ฒฝ๋กœ ์••์ถ•) - ์ด๊ฒƒ์ด ์ทจ์—…์„ ์œ„ํ•œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ๋‹ค ๊ตฌํ˜„ ์ฝ”๋“œ๋ฅผ ์ฐธ๊ณ !

์œ ๋‹ˆ์˜จ-ํŒŒ์ธ๋“œ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ํ™œ์šฉ

์œ ๋‹ˆ์˜จ-ํŒŒ์ธ๋“œ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ด์šฉํ•ด ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„ ๋‚ด์—์„œ์˜ ์‚ฌ์ดํด์„ ํŒ๋ณ„ํ•  ์ˆ˜ ์žˆ๋‹ค. ํ•ฉ์ง‘ํ•ฉ ์—ฐ์‚ฐ์€ ๊ทธ๋ž˜ํ”„์˜ ๊ฐ„์„ ์œผ๋กœ ๋Œ€์‘๋œ๋‹ค๊ณ  ํ•  ๋•Œ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ์‚ฌ์ดํด์„ ํŒ๋ณ„ํ•  ์ˆ˜ ์žˆ๋‹ค.

  • ๊ฐ„์„ ์œผ๋กœ ์—ฐ๊ฒฐ๋œ ๋‘ ๋…ธ๋“œ์˜ ๋ฃจํŠธ ๋…ธ๋“œ๋ฅผ ํ™•์ธํ•œ๋‹ค.
  • ๋งŒ์•ฝ ๋ฃจํŠธ ๋…ธ๋“œ๊ฐ€ ์„œ๋กœ ๋‹ค๋ฅด๋‹ค๋ฉด ํ•ฉ์ง‘ํ•ฉ ์—ฐ์‚ฐ์„ ์ˆ˜ํ–‰ํ•œ๋‹ค.
  • ๋งŒ์•ฝ ๋ฃจํŠธ ๋…ธ๋“œ๊ฐ€ ๊ฐ™๋‹ค๋ฉด ์‚ฌ์ดํด์ด ๋ฐœ์ƒํ–ˆ๋‹ค๊ณ  ํŒ๋‹จํ•œ๋‹ค.

๊ตฌํ˜„ ๋ฐฉ๋ฒ•์€ ์„œ๋กœ์†Œ ์ง‘ํ•ฉ์„ ํ™œ์šฉํ•œ ์‚ฌ์ดํด ํŒ๋ณ„ - ์ด๊ฒƒ์ด ์ทจ์—…์„ ์œ„ํ•œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ๋‹ค ๊ตฌํ˜„ ์ฝ”๋“œ๋ฅผ ์ฐธ๊ณ !

References


#6-5

Topological Sort

์œ„์ƒ ์ •๋ ฌ(Topological Sort)๋ž€ ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„์˜ ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ์„ ํ–‰ ์ˆœ์„œ๋ฅผ ์ง€ํ‚ค๋ฉฐ ์ •์ ์„ ์ˆœ์„œ๋Œ€๋กœ ๋‚˜์—ดํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ์œ„์ƒ ์ •๋ ฌ์˜ ๋Œ€ํ‘œ์ ์ธ ์˜ˆ๋กœ ๋Œ€ํ•™๊ต ์„ ์ˆ˜๊ณผ๋ชฉ์ด ์žˆ๋‹ค. ์œ„์ƒ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

  • ์ง„์ž…์ฐจ์ˆ˜๊ฐ€ 0์ธ ๋…ธ๋“œ๋ฅผ ํ์— ๋„ฃ๋Š”๋‹ค.
  • ํ๊ฐ€ ๋นŒ ๋•Œ๊ฐ€์ง€ ๋‹ค์Œ์„ ๋ฐ˜๋ณตํ•œ๋‹ค.
    • ํ์—์„œ ์š”์†Œ๋ฅผ ๊บผ๋‚ด ํ•ด๋‹น ๋…ธ๋“œ์—์„œ ์ถœ๋ฐœํ•˜๋Š” ๊ฐ„์„ ์„ ๊ทธ๋ž˜ํ”„์—์„œ ์ œ๊ฑฐํ•œ๋‹ค.
    • ์ƒˆ๋กญ๊ฒŒ ์ง„์ž…์ฐจ์ˆ˜๊ฐ€ 0์ด ๋œ ๋…ธ๋“œ๋ฅผ ํ์— ๋„ฃ๋Š”๋‹ค.

๋งŒ์•ฝ ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๊ธฐ ์ „์— ํ๊ฐ€ ๋นˆ๋‹ค๋ฉด ์‚ฌ์ดํด์ด ์กด์žฌํ•œ๋‹ค๊ณ  ํŒ๋‹จํ•  ์ˆ˜ ์žˆ๋‹ค. ์™œ๋ƒํ•˜๋ฉด ์‚ฌ์ดํด์ด ์กด์žฌํ•˜๋Š” ๊ฒฝ์šฐ ์‚ฌ์ดํด์„ ํ˜•์„ฑํ•˜๋Š” ๋…ธ๋“œ๋“ค์˜ ์ง„์ž…์ฐจ์ˆ˜๊ฐ€ ํ•ญ์ƒ 1 ์ด์ƒ์ด๋ฏ€๋กœ ํ์— ๋„ฃ์„ ์ˆ˜๊ฐ€ ์—†๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

๊ตฌํ˜„ ๋ฐฉ๋ฒ•์€ ์œ„์ƒ ์ •๋ ฌ - ์ด๊ฒƒ์ด ์ทจ์—…์„ ์œ„ํ•œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ๋‹ค ๊ตฌํ˜„ ์ฝ”๋“œ๋ฅผ ์ฐธ๊ณ !

๐Ÿ’ก ์ง„์ž… ์ฐจ์ˆ˜(degree)
๋…ธ๋“œ์˜ ๊ด€์ ์—์„œ ๋“ค์–ด์˜ค๋Š” ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ง„์ž… ์ฐจ์ˆ˜(degree)๋ผ๊ณ  ํ•œ๋‹ค.

References