[4/20] 자료구조와 알고리즘

누런강냉이 2021. 4. 20. 22:42

2021. 4. 20. 22:42

자료구조와 알고리즘

자료구조란? 데이터가 있고, 그 데이터에 대해 행할 수 있는 연산들로 이루어진 구조

알고리즘이란? 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택

선형 배열

배열이란? 원소들을 순서대로 늘어놓은 것

원소 삽입

L = [ 1, 3, 5, 7, 9 ]
index 0 1 2 3 4

L.insert(3,6) 적용 시

3번 인덱스의 앞을 우선 찾아내게 되고,

맨 뒤의 수를 오른쪽으로 한 칸 옮기게 된다. (이 과정에서 배열의 크기가 하나 늘어나 크기가 6인 배열이 된다.)
그 후 7을 또 오른쪽으로 한 칸 옮기고
마지막으로 6을 삽입함

결과

L = [ 1, 3, 5, 6, 7, 9 ]
index 0 1 2 3 4 5

원소 삭제

L = [ 1, 3, 5, 6, 7, 9 ]
index 0 1 2 3 4 5

del(L[2]) 적용 시

2번 인덱스에 있던 5를 삭제하고,

오른편에 있던 6과 7과 9를 한 칸씩 옮긴다.

그 후 맨마지막 5번 인덱스에 있던 9를 옮긴다. (이 과정에서 배열의 크기가 하나 줄어 크기가 5인 배열이 된다.)

결과

L = [ 1, 3, 6, 7, 9 ]
index 0 1 2 3 4

del()과 pop()은 비슷한 동작을 시행하지만,

del()은 시행한 후 빠져나간 원소의 값이 반환되지 않고,

pop()은 시행한 후 빠져나간 원소의 값이 반환된다는 차이를 보인다.

원소 삽입과 삭제는 리스트의 길이가 길면 비례해서 연산이 오래걸린다. (선형 시간)

=> O(n)만큼의 시간이 걸린다.

정렬

수 정렬

L = [ 5, 1, 3, 7, 2 ]

sorted(L) 적용 시

L = [ 5, 1, 3, 7, 2 ]

sorted(L)은 리스트 자체에 변화를 주지 않는다.

L.sort() 적용 시

L = [ 1, 2, 3, 5, 7 ]

L.sort()는 L 리스트 자체에 변화를 준다. (바로 적용이 된다.)

L = sorted(L, reverse=True) OR L.sort(reverse=True) 적용 시

L = [ 7, 5, 3, 2, 1]

문자열 정렬

L = [ 'abcd', 'xyz', 'spam']

위 리스트를 그냥 정렬하게 되면 사전순으로 정렬하게 된다.

그렇다면 문자열 길이별로 정렬하려면 어떻게 하여야 할까?

키를 활용한다.

sorted(L, key = lambda x : len(x)) 적용 시

L = [ 'xyz, 'abcd', 'spam' ]

탐색

탐색 알고리즘 (1) - 선형 탐색

리스트에 비례하는 시간 소요

=> O(n)

탐색 알고리즘 (2) - 이진 탐색

한 번 비교할 때마다 리스트를 반씩 줄인다. (divide & conquer)

=> O(log n)

이진 탐색 코드 구현

lower = 0
upper = len(L) - 1
while lower <= upper:
    middle = (lower + upper)//2 #중간 인덱스 찾기
    if L[middle] == target:
    	return middle
    elif L[middle] < target: #중간값이 target값보다 작을 경우
    	lower = middle+1 #중간 인덱스보다 1만큼 큰 값으로 lower값 조정
    else: #중간값이 target값보다 클 경우
    	upper = middle-1 #중간 인덱스보다 1만큼 작은 값으로 upper값 조정

재귀 알고리즘

재귀함수(Recursive function)란? 하나의 함수에서 자신을 다시 호출해 작업을 수행하는 것

재귀함수 설계 시, 종결 조건에 유의하여야 한다.

재귀 알고리즘의 효율

def sum(n):
    if n<=1:
    	return n
    else:
    	return n+sum(n-1)

=> O(n)

def sum(n):
    s = 0
    while n>=0:
    	s+=n
        n-=1
    return s

=> O(n)

def sum(n):
    return n*(n+1)//2

=> O(1)

※ 효율성 측면에 유의하여 알고리즘을 잘 설계해야 한다!

피보나치 순열

재귀함수를 활용한 경우

def solution(x):
    if x==0:
        return 0
    elif x==1:
        return 1
    else:
        return solution(x-1) + solution(x-2)

반복적 함수를 활용한 경우

def solution(x):
    a, b = 0, 1
    
    if x==0:
        return 0
    
    for i in range(x-1):
        a,b = b, a+b
            
    return b

※ 꼭 재귀라고 효율성이 좋은 것만은 아니다. 문제에 따라 적절한 자료구조를 선택해야 한다는 좋은 본보기가 되어준다.

재귀적 이진 탐색

def binsearch(L, x, lower, upper):
    if l>u:
        return -1
    mid = (lower + upper) // 2
    if x==L[mid]:
        return mid
    elif x<L[mid]:
        return solution(L,x,l,mid-1)
    else:
        return solution(L,x,mid+1,u)

알고리즘의 복잡도

☆ 시간 복잡도란? 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계

평균 시간 복잡도 : 임의의 입력 패턴(랜덤한 패턴)을 가정했을 때 소요되는 시간의 평균
최악 시간 복잡도 : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간 (이를 기준으로 알고리즘의 복잡도를 계산한다.)

공간 복잡도란? 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

☆ Big-O Notation이란? 점근 표기법의 하나. 알고리즘의 복잡도를 표현할 때 흔히 쓰인다.

선형 시간 알고리즘 - O(n)
로그 시간 알고리즘 - O(log n)
- ex) 이진 탐색 알고리즘
이차 시간 알고리즘 - O(n²)
- ex) 삽입 정렬

삽입 정렬보다 낮은 복잡도를 가지는 정렬 알고리즘

병합 정렬
- 정렬할 데이터를 반씩 나누어 각각 정렬시킨다. - O(log n)
- 정렬된 데이터를 두 묶음씩 한데 합친다. - O(n)
- 결과 => O(nlog n)
- 그림출처 : https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

연결 리스트 (Linked List)

추상적 자료구조

Data
- 정수, 문자열, 레코드, ...
A set of operations
- 삽입, 삭제, 순회, ...
- 정렬, 탐색, ...

연결 리스트 구현

class Node:

    def __init__(self, item):
        self.data = item
        self.next = None


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None


    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None

        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

        return curr


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos == 1:
            newNode.next = self.head
            self.head = newNode

        else:
            if pos == self.nodeCount + 1:
                prev = self.tail
            else:
                prev = self.getAt(pos - 1)
            newNode.next = prev.next
            prev.next = newNode

        if pos == self.nodeCount + 1:
            self.tail = newNode

        self.nodeCount += 1
        return True


    def popAt(self, pos):
        delete_node = self.getAt(pos)

        if pos < 1 or pos > self.nodeCount:  
            raise IndexError 

        if pos == 1:    
            if self.nodeCount == 1:    
                self.head=None
                self.tail=None
                
            else:                          
                self.head = self.head.next
            
        else:                          
            prev = self.getAt(pos - 1)
            prev.next = delete_node.next
            if pos == self.nodeCount:   
                prev.next = None
                self.tail = prev
                
        self.nodeCount -= 1
        return delete_node.data

    def traverse(self):
        result = []
        curr = self.head
        while curr is not None:
            result.append(curr.data)
            curr = curr.next
        return result

조금 변형된 연결 리스트 (Dummy head 추가)

그림 출처 : http://cslabserver2.cs.mtsu.edu/labs/2170/lab10/dummy.html

class Node:

    def __init__(self, item):
        self.data = item
        self.next = None


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail


    def traverse(self):
        result = []
        curr = self.head
        while curr.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        i = 0
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

        return curr


    def insertAfter(self, prev, newNode):
        newNode.next = prev.next
        if prev.next is None:
            self.tail = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos != 1 and pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        curr = prev.next
        
        if prev.next == None:
            return None
        
        if curr.next == None:
            self.tail = prev
        
        prev.next = curr.next
        self.nodeCount-=1 
        
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount :
            raise IndexError
            
        prev = self.getAt(pos-1)
        
        return self.popAfter(prev)
    
    def concat(self, L):
        self.tail.next = L.head.next
        if L.tail:
            self.tail = L.tail
        self.nodeCount+=L.nodeCount

한 쪽으로만 진행이 가능하다는 단점이 있다. 이를 보완한 것이...

양방향 연결 리스트(Doubly Linked Lists)

양방향 연결 리스트란? 앞으로도 뒤로도 즉, 양쪽으로 진행이 가능한 리스트

그림 출처 : https://www.studytonight.com/data-structures/doubly-linked-list

head와 tail에 dummy node를 달아준다.

class Node:

    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None


class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None


    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr


    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)
        
    def insertBefore(self, next, newNode):
        prev = next.prev
        newNode.next = prev.next
        newNode.prev = prev
        prev.next = newNode
        next.prev = newNode
        self.nodeCount+=1
        return True


    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount-=1
        
        return curr.data


    def popBefore(self, next): #수정필요
        curr = next.prev
        prev = curr.prev
        prev.next = next
        next.prev = prev
        self.nodeCount-=1
        
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
            
        prev = self.getAt(pos-1)
        next = self.getAt(pos)
        
        return self.popAfter(prev)
        #return self.popBefore(next)
        
    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail
        self.nodeCount += L.nodeCount

스택

스택이란? 자료를 보관할 수 있는 구조

한 쪽 끝에서 밀어 넣어야 하고

=> push

같은 쪽에서 뽑아 꺼내야 한다.

=> pop

※ LIFO구조 (Last in First out)

그림 출처 : https://swexpertacademy.com/

스택 연산

size() - 현재 스택에 들어 있는 데이터 원소 수
isEmpty() - 현재 스택이 비어 있는지 판단
push(x) - 데이터 원소 x를 스택에 추가
pop() - 스택의 맨 위 저장된 데이터 원소 제거 및 반환
peek() - 스택의 맨 위 저장된 데이터 원소 반환 (제거하지 않음)

배열을 이용해 구현

class ArrayStack:
    def __init__(self):
        self.data = []
    def size(self):
        return len(self.data)
    def isEmpty(self):
        return self.size() == 0
    def push(self, item):
        self.data.append(item)
    def pop(self):
        return self.data.pop()
    def peek(self):
        return self.data[-1]

연결 리스트를 이용해 구현

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

class LinkedListStack
    def __init__(self):
        self.data = DoublyLinkedList()
    
    def size(self):
        return self.data.getLength()
        
    def isEmpty(self):
        return self.size()==0
        
    def push(self, item):
        node = Node(item)
        self.data.insertAt(self.size() + 1, node)
        
    def pop(self):
        return self.data.popAt(self.size())
        
    def peek(self):
        return self.data.getAt(self.size()).data

'AI > KDT 인공지능' 카테고리의 다른 글

[04/26] 인공지능 수학 - 선형 시스템 (0)	2021.04.26
[4/26] 주피터 노트북 (0)	2021.04.26
[4/22] 코딩테스트 연습 (2) (0)	2021.04.22
[4/21] 코딩테스트 연습 (0)	2021.04.21
[4/21] 자료구조와 알고리즘(2) (0)	2021.04.21

누런강냉이