devAlgorithm

알고리즘 기본-백업자료

알고리즘 기본

기존 깃북에 올려놓은 마크다운 복붙이라 내용이 비어있거나
안맞을 수도 있습니다.

다시 공부하기전에 알고 있는거 그냥 한번씩 정리하자.. 학부생때 생각나게 ㅋㅋ

Core Java 책에 이렇게 표현하기도 한다.

프로그램 = 자료구조 + 알고리즘

너무 단순하다고 볼 수 있지만 틀린 것은 아닌게 정말 심플하게만 바라보면
컴퓨터는 어떤 입력에 따라 출력을 내주는 정말 계산기 같은 기계로 볼 수 있다.

이렇게 들어온 자료를 계산및 가공하기 위해 저장이 필요하며
이때 어떻게 저장할지를 생각하는게 자료 구조이며 이렇게 저장된 자료를
어떻게 처리할 것인가의 고민이 알고리즘이라고 할 수 있다.

1.빅오

1.O(1)

  • 스택의 push, pop
  • 해쉬 테이블-하나의 키에만 접근 하기에 100만개 아이템이 있더라 하더라도 한번의 접근이기에.

2.O(log n)

  • 바이너리 탐색 트리의 접근, 서치, 삽입, 삭제가 예
  • 8개의 아이템이 있을때 바이너리 트리의 depth는 3
  • 혹은 log 8 = log 2^3 = 3으로 나타낼 수도 있다.

3.O(n)

  • 배열 안의 모든 아이템을 출력 한다던지.–> 100만개의 아이템이 있다면 100만번 접근이 필요.
  • 트리 순회(traverse tree), 연결 리스트 순회(traverse linked list)

4.O(n log n)

  • Quick Sort, Merge Sort(병합정렬), Heap Sort

5.,O(n^2)

  • Insertion Sort(삽입정렬), Bubble Sort(거품정렬), Selection Sort(선택정렬)
  • 2중 for문의 일반적

Sort(정렬)

1.거품정렬(Bubble Sort)

정렬을 위한 교환 작업이 거품같이 버블 거린다고 해서 거품 정렬

  • 시간 복잡도: O(n^2) ..좋지 않다.
  • 공간 복잡도:O(1)교환을 위한 공간이 하나 필요하다.
  • 비교를 해서 크기 조건에 맞으면 스와핑, 아니면 패스
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import unittest

def bubblesort(alist):
    for i in range(len(alist)-1):
        for j in range(len(alist)-1):
            if alist[j] > alist[j+1]:
                alist[j], alist[j+1] = alist[j+1], alist[j]
    return alist


class unit_test(unittest.TestCase):
    def test(self):
        self.assertEqual([1, 2, 3, 4, 5, 6], bubblesort([4, 6, 1, 3, 5, 2]))
        self.assertEqual([1, 2, 3, 4, 5, 6], bubblesort([6, 4, 3, 1, 2, 5]))
        self.assertEqual([1, 2, 3, 4, 5, 6], bubblesort([6, 5, 4, 3, 2, 1]))

2.선택정렬(Selection Sort)

정렬을 위한 교환 작업이 거품같이 버블 거린다고 해서 거품 정렬

  • 시간복잡도: O(n^2), 최악,최상 전부 n^2로 좋지 않으나, 구현이 쉬워서 많은 사람들이 구현.
  • 공간복잡도: O(n) total, O(1) auxiliary
  • 처음 포인터가 첫아이템을 가르키고 min값 변수에 집어넣는다.
  • 이후 아이템 끝까지 순회하면서 min값 변수와 비교한다. 끝까지 순회하면 가장 작은 min값이 남게된다.
  • min값을 가졌던 그 아이템과 첫 아이템을 swap하고 포인터는 그다음을 가르킨다. 이후 반복
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import unittest

def selectionSort(input):
    for i in range(len(input) - 1):
        # assume the min is the first element
        idx_min = i
        j = i + 1

        # test against elements after i to find the smallest
        while j < len(input):
            if(input[j] < input[idx_min]):
                # found new minimum; remember its index
                idx_min = j
            j = j + 1

        if idx_min is not i:
            # swap
            input[idx_min], input[i] = input[i], input[idx_min]

    return input

class unit_test(unittest.TestCase):
    def test(self):
        self.assertEqual([1, 2, 3, 4, 5, 6], selectionSort([4, 6, 1, 3, 5, 2]))
        self.assertEqual([1, 2, 3, 4, 5, 6], selectionSort([6, 4, 3, 1, 2, 5]))
        self.assertEqual([1, 2, 3, 4, 5, 6], selectionSort([6, 5, 4, 3, 2, 1]))

3.삽입정렬(InsertionSort)

아주 간단하게 구현이 가능하다. 효율성은 다른 알고리즘에 비해 떨어진다.

  • 시간복잡도: O( )
  • 공간복잡도: O( )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import unittest

def insertion_sort(input):

    for idx, valueToInsert in enumerate(input):
        # select the hole position where number is to be inserted
        holePosition = idx

        # check if previous no. is larger than value to be inserted
        while holePosition > 0 and input[holePosition-1] > valueToInsert:
            input[holePosition - 1], input[holePosition] = input[holePosition], input[holePosition-1]
            holePosition = holePosition - 1

    return input

class unit_test(unittest.TestCase):
    def test(self):
        self.assertEqual([1, 2, 3, 4, 5, 6], insertion_sort([4, 6, 1, 3, 5, 2]))
        self.assertEqual([1, 2, 3, 4, 5, 6], insertion_sort([6, 4, 3, 1, 2, 5]))
        self.assertEqual([1, 2, 3, 4, 5, 6], insertion_sort([6, 5, 4, 3, 2, 1]))

4.병합정렬(Merge Sort)

아주 간단. 2개의 스텝(바이너리로 쪼갤 때 log n, 각자 비교하는 과정이 n)

  • 시간복잡도: O(n log n)
  • 공간복잡도: O( n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [6,2,4,1,3,7,5,8]
mergeSort(alist)
print(alist)

5.퀵 정렬(Quick Sort)

  • 시간복잡도: O(n log n) , 이미 리스트가 정렬되었을때는 O(n^2)라는 worst 케이스가 생기는 단점.
  • 공간복잡도: O(n), 따로 메모리 필요 없기에 아주좋은 공간 복잡도
  • 엄청 짧은 코드. 재귀 알고리즘의 대명사.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import unittest

def quick_sort(list, start, end):
    # repeat until sublist has one item
    # because the algorithm is using in-place space, we can not use len(list) instead we use start, end for sublist
    if start < end:
        # get pivot using partition method
        pivot = partition(list, start, end)
        # recurse quick sort left side from pivot
        quick_sort(list, start, pivot-1)
        # recurse quick sort right side from pivot
        quick_sort(list,pivot+1, end)
    return list

def partition(list, start, end):
    # use end item as initial pivot
    pivot = end
    # use start as initial wall index
    wall = start
    left = start
    # repeat until left item hit the end of list
    while left < pivot:
        # if left item is smaller than pivot, swap left item with wall and move wall to right
        # this will ensure items smaller than pivot stay left side from the wall and
        # the items greater than pivot stay right side from the wall
        if list[left] < list[pivot]:
            list[wall], list[left] = list[left], list[wall]
            wall = wall + 1
        left = left + 1
    # when left hit the end of list, swap pivot with wall
    list[wall], list[pivot] = list[pivot], list[wall]
    # now left side of wall are the items smaller than wall
    # now right side of pivot are the items greater than wall
    # wall is the new pivot
    pivot = wall
    return pivot

class unit_test(unittest.TestCase):
    def test(self):
        list = [8, 13, 2, 6, 1, 4]
        self.assertEqual([1, 2, 4, 6, 8, 13], quick_sort(list,0,len(list)-1))
        list = [8, 1, 2, 5, 10, 14, 7, 21]
        self.assertEqual([1, 2, 5, 7, 8, 10, 14, 21], quick_sort(list, 0, len(list) - 1))

자료구조

자료구조 다 아는건데.. 곡 인터뷰나 이런거 하면 긴장하면 머리가 멍해서 격 안나니 ㅋㅋ
빠른 레퍼런스를 위해 기억 상기용으로 대충 정리 해놓자.

Queue

  • FIFO
  • enqueue, dequeue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import unittest

"""
Queue
"""


class Queue:

    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        self.items.pop()

    def print_queue(self):
        print(self.items)

    def is_empty(self):
        return self.items == []

    def size(self):
        return len(self.items)

class QueueTest(unittest.TestCase):
    def test(self):
        queue = Queue()
        self.assertTrue(queue.is_empty())
        queue.enqueue(1)
        self.assertEqual(queue.size(),1)
        queue.enqueue(2)
        self.assertEqual(queue.size(),2)
        queue.print_queue()
        queue.dequeue()
        self.assertEqual(queue.size(),1)
        queue.print_queue()
        self.assertFalse(queue.is_empty())

Stack

  • FILO
  • Push, Pop
  • 오버플로우: 스택 풀일떄 또 push, 예전 해커스랩 오버플로우 익스플로잇 생각해볼것 strcpy()이용한거.
  • 언더플로우: 스택 아이템 0 일떄 POP~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import unittest

"""
Stack
"""


class Stack:
    def __init__(self):
        self.items = []
        self.max = 5

    def push(self, item):
        if len(self.items) < 5:
            self.items.append(item)
        else:
            print("abort push in order to prevent stack overflow")

    def pop(self):
        if len(self.items) > 0:
            self.items.pop()
        else:
            print("stack is empty, abort pop to prevent stack underflow")

    def print_stack(self):
        print(self.items)

    def peek(self):
        return self.items[len(self.items)-1]

    def is_empty(self):
        return self.items == []

    def size(self):
        return len(self.items)


class StackTest(unittest.TestCase):
    def test(self):
        st = Stack()
        self.assertTrue(st.is_empty())
        self.assertEqual(st.size(), 0)
        st.push(1)
        st.push(2)
        st.print_stack()
        st.pop()
        st.print_stack()
        st.push(3)
        self.assertEquals(st.peek(),3)
        self.assertFalse(st.is_empty())
        self.assertEqual(st.size(), 2)
        st.pop()
        st.pop()
        st.pop()
        st.push(3)
        st.push(3)
        st.push(3)
        st.push(3)
        st.push(3)
        st.push(3)

Linked List

  • Git도 이구조였음을 기억.(지옥에서 온 GIt강좌 설명 상기해보자)
  • 1학년 자료구조 중간고사 기억나나? ㅋㅋ(중간삭제, 마지막 삭제 흐름 한번씩 다시 되새겨보자)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
"""
Linked List
"""
import unittest

class Node:
    def __init__(self, item):
        self.val = item
        self.next = None

class LinkedList:
    def __init__(self, item):
        self.head = Node(item)

    def add(self, item):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(item)

    def remove(self, item):
        if self.head.val == item:
            self.head = self.head.next
        else:
            cur = self.head
            while cur.next is not None:
                if cur.val == item:
                    self.removeItem(item)
                    return
                cur = cur.next
            print("item does not exist in linked list")

    def removeItem(self, item):
        cur = self.head
        while cur.next is not None:
            if cur.next.val == item:
                nextnode = cur.next.next
                cur.next = nextnode
                break

    def reverse(self):
        prev = None
        cur = self.head
        while cur is not None:
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        self.head = prev

    def printlist(self):
        cur = self.head
        while cur is not None:
            print(cur.val)
            cur = cur.next


class LinkedListTest(unittest.TestCase):
    def test(self):
        ll = LinkedList(3)
        self.assertEqual(ll.head.val, 3)
        ll.add(4)
        self.assertEqual(ll.head.next.val, 4)
        ll.add(5)
        self.assertEqual(ll.head.next.next.val, 5)
        ll.remove(3)
        self.assertEqual(ll.head.val, 4)
        ll.remove(4)
        self.assertEqual(ll.head.val, 5)
        ll.add(6)
        self.assertEqual(ll.head.next.val, 6)
        ll.add(7)
        self.assertEqual(ll.head.next.next.val, 7)
        ll.printlist()
        ll.remove(6)
        self.assertEqual(ll.head.next.val, 7)

        ll2 = LinkedList(9)
        ll2.add(8)
        ll2.add(7)
        ll2.reverse()
        self.assertEqual(ll2.head.val, 7)
        self.assertEqual(ll2.head.next.val, 8)

Heap

  • 시간복잡도: 구성시(Run-time): 최악의 경우 O(n log n), 그러나 max와 min은 한방에 얻어낼 수 있는 엄청난 장점: O(1)
  • 공강복잡도: Heap sort is an in-place 알고리즘(따로 메모리 필요없)
  • Min-Heap, Max-Heap이 있다.(ROOT값에 따라서 )
  • 부모가 자식보다 크면 힙이다.?(과연?)맥스힙에선 그러하다.
  • Heapify, siftdown
    • Heapify: 일반적인 트리를 힙 트리로 바꾸는 과정. 열어보면 시프트다운의 연속.
    • siftdown: 자식이 더 크면 현 노드와 스왑.
  • 상품들 엄청많을때 제일 싼거? 제일 비싼거? –> 최대값을 한방에 구할 수 있는 힙 트리가 제격
  • 밑 예제 소스는 array를 사용해서 heap tree 구현..
  • 소스 테스트 필요, 최소힙인듯.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#=======================================================================
#  Title: Heapsort
#
#  Statement:
#  Given a disordered list of integers (or any other items),
#  rearrange the integers in natural order.
#
#  Sample Input: [8,5,3,1,9,6,0,7,4,2,5]
#  Sample Output: [0,1,2,3,4,5,5,6,7,8,9]
#
#  Time Complexity of Solution:
#  Best O(nlog(n)); Average O(nlog(n)); Worst O(nlog(n)).
#
#  Approach:
#  Heap sort happens in two phases. In the first phase, the array
#  is transformed into a heap. A heap is a binary tree where
#  1) each node is greater than each of its children
#  2) the tree is perfectly balanced
#  3) all leaves are in the leftmost position available.
#  In phase two the heap is continuously reduced to a sorted array:
#  1) while the heap is not empty
#  - remove the top of the head into an array
#  - fix the heap.
#  Heap sort was invented by John Williams not by B. R. Heap.
#
#  MoveDown:
#  The movedown method checks and verifies that the structure is a heap.
#
#  Technical Details:
#  A heap is based on an array just as a hashmap is based on an
#  array. For a heap, the children of an element n are at index
#  2n+1 for the left child and 2n+2 for the right child.
#
#  The movedown function checks that an element is greater than its
#  children. If not the values of element and child are swapped. The
#  function continues to check and swap until the element is at a
#  position where it is greater than its children.
#=======================================================================

def heapsort(a):

    def swap(a,i,j):
        tmp = a[i]
        a[i] = a[j]
        a[j] = tmp

    def siftdown(a, i, size):
        l = 2*i+1
        r = 2*i+2
        largest = i
        if l <= size-1 and a[l] > a[i]:
            largest = l
        if r <= size-1 and a[r] > a[largest]:
            largest = r
        if largest != i:
            swap(a, i, largest)
            siftdown(a, largest, size)

    def heapify(a, size):
        p = (size//2)-1
        while p>=0:
            siftdown(a, p, size)
            p -= 1

    size = len(a)
    heapify(a, size)
    end = size-1
    while(end > 0):
        swap(a, 0, end)
        siftdown(a, 0, end)
        end -= 1

arr = [1,3,2,4,9,7]
heapsort(arr)
print(arr)

Related POST

공유하기