[TIL]20220522

WIL: 배열, 연결리스트, 스택, 큐, 해시테이블,그래프, BFS, DFS

배열(Array)

배열은 파이썬에서 list와 tuple 이라는 두가지 타입을 제공한다. 그리고 파이썬에서는 원소의 타입이 동일하지 않아도 된다는 특징이있다. 

Tuple 은 원소수정을 할 수없지만 

List는 원소 수정(추가,삭제) 이 가능하다.

 

연결리스트(Linked List)

노드를 이용해 집적 구현해야 한다. 

클래스: 함수들을 모아놓은것을 클래스라고 한다. 

class Node:
    def __init__(self,var,next):
        self.var = var
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self,vartoadd):
        if self.head is None:
            self.head = Node(vartoadd,None)
            return

        startnode = self.head
        while startnode.next:
            startnode = startnode.next

        startnode.next = Node(vartoadd,None)

    def printll(self):
        node = self.head
        while node:
            print(node.var)
            node = node.next
    def deletekey(self,keyval):

        temp = self.head
        if temp is not None:
            if temp.var == keyval:
                self.head = temp.next

                return

        while temp:
            if temp.var == keyval:
                break
            prev = temp
            temp = temp.next

        if temp is None:
            return

        prev.next = temp.next

 

스택(Stack)

한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조이다.(LIFO)

파이썬에서는 list 의 append(x)와 pop()을 사용한다. 

대표적으로는 컴퓨터의 되돌리기 기능이 스택을 사용한다.

클래스를 사용해 구현하면 다음과 같다. 

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


class Stack:
    def __init__(self):
        self.top = None

    def push(self, value):
        self.top = Node(value, self.top)

    def pop(self):
        if self.top is None:
            return None

        node = self.top
        self.top = self.top.next

        return node.item

    def is_empty(self):
        return self.top is None

큐

Queue: 먼저 들어온것이 먼저나가는 형태의 선형 자료구조. FIFO

ADT( Abstract Data Type) : 추상자료형. 연결리스트, 스택, 큐 등의 ADT는 data를 담을 저장소를 만드는것과, data를 다루는 함수들을 정의하는것들을 모두 포함하는 계념.

python 에서는 collections 의 deque 를 활용해 큐를 만든다. ( deque: 양쪽 끝에서 빠르게 추가와 삭제를 할수있는 리스트류 컨테이너)

deque 에서 append(x), appendleft(x), pop(), popleft() 는 모두 비용이 O(1) 이다.

클래스를 사용해 구현하면 다음과 같다. 

class Queue:
    def __init__(self):
        self.front = None

    def push(self, value):
        if not self.front:
            self.front = Node(value, None)
            return

        node = self.front
        while node.next:
            node = node.next
        node.next = Node(value, None)

    def pop(self):
        if not self.front:
            return None

        node = self.front
        self.front = self.front.next
        return node.item

    def is_empty(self):
        return self.front is None

해시테이블

해시 테이블(해시맵) : 키를 값에 매핑할수 있는 구조인 연관배열 추상 자료형 (ADT)을 구현하는 자료구조. 대부분 연산(삽입, 삭제, 탐색) 이 O(1)에 가능하다

 

해시 함수: 임의 크기의 데이터를 고정 크기값으로 매핑하는데 사용할수 있는 함수 

ex)  ABC -> A1
     1324BC ->C8
     AF32B -> D5

 

해시 테이블이 인덱싱을 하기위해 해시함수를 사용하는것을 해싱(Hashing) 이라고 하고, 해싱은 정보를 가능한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법중 하나다 ( 최적의 검색, 심볼테이블자료구조 구현 등에 쓰인다.)

 

좋은해시함수란?

• 해시함수값충돌최소화
• 쉽고 빠른 연산
• 해시테이블 전체에 해시값이 균일하게 분포
• 사용할 키의 모든 정보를 이용하여 해싱
• 해시테이블 사용효율이 높음

로드팩터(Load Factor): 해시테이블에 저장된 데이터 개수 n 을 버킷의 개수 k 로 나눈 값

 

load factor = n/k

 

로드팩터의 비율에 따라 해시함수를 재작성해야할지 또는 해시테이블의 크기를 조정할지를 결정한다. 

일반적으로 로드팩터가 증가할수록 해시테이블 성능은 감소한다.

자바10에서 해시맵 디폴트 로드팩터를 0.75로 조정함 ("시간과 공간의 절충안")

파이썬: 0.66, 루비: 0.5

 

모듈로 연산을 이용한 해시함수

가장쉽고 많이 쓰임

h(x) = x mod m 

x 는 입력값, 배열값

m은 해시테이블의 크기로 일반적으로 2의 멱수(거듭제수)에 가깝지 않은 소수를 사용하는것이 좋다

 

충돌관리 ( 개별체이닝, 오픈 어드레싱)

개별체이닝: 충돌발생시 연결 리스트로 연결

잘 구현하면 대부분의 탐색은 O(1) 이지만 모든 해시충돌 발생시(최악의경우) O(n)이다.

오픈어드레싱: 충돌발생시 탐사(probing)을 통해 빈공간을 찾아내는 방식. 

모든 원소가 반드시 자신과 일치하는 주소에 저장된다는 보장은 없다.

선형탐사(Linear Probing)의 문제점:

해시테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 (clustering) 경향이 있다.

버킷 사이즈보다 큰 경우에는 삽입할수 없다. ( 또 다른 버킷 생성후 새롭게 리해싱 해야함)

 

해시테이블과 파이썬

"딕셔너리"를 오픈 어드레싱 방식의 해시테이블로 구현했다. 

오픈어드레싱방식을 채택한 이유는 로드팩터가 낮은(0.8 이하) 상황에서 더 좋은 성능을보이기 때문

파이썬: "체이닝시 메모리 할당하는 오버헤드가 높아 오픈 어드레싱 채택"

 

그래프

선형구조 vs 비선형구조

선형구조: 자료를 저장하고 꺼내는것에 초점을 맞춤. ex) 리스트, 스택, 큐

비선형구조: 표현에 초점을 맞춤. ex) 그래프( 특히 연결관계에 초점)

 

그래프란? 

연결되어있는 정점(Node)과 정점(Node)의 관계를 표현할 수 있는 자료구조

유방향 그래프: 간선은 단방향 관계를 의미하고, 각 간선은 한방향으로만 진행 ( 팔로우)

무방향 그래프: 방향이 없는 간선을 갖는다. (일촌)

 

 

 

그래프의 표현 방법

1) 인접행렬 (Adjacent Matrix): 2차원 배열로 그래프의 연결관계를 표현 (시간복잡도는 낮고 공간복잡도는 높다)

2) 인접리스트 (Adjacency List): 링크드 리스트로 그래프의 연결관계를 표현 (공간복잡도는 낮고 시간복잡도는 높다)

  

          2 - 3
           ⎜       
      0 - 1

1.  인접 행렬,
   0  1  2  3
0 X  O  X  X
1 O  X  O  X
2 X  O  X  O
3 X  X  O  X

이걸 배열로 표현하면 다음과 같습니다!
graph = [
    [False, True, False, False],
    [True, False, True, False],
    [False, True, False, True],
    [False, False, True, False]
]

2. 인접리스트

0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

이를 딕셔너리로 표현하면 다음과 같습니다!
graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}

.

그래프 탐색 방법 (dfs, bfs)

DFS (Depth Fisr Search) : 갈수있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조. 스택이나 재귀로 구현할수 있다. 

 

BFS ( Breadth-first-search) : 넓이 우선탐색 (큐를 이용해 구현한다)

 

from collections import deque

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}


def bfs_queue(start):
    q = deque([start])
    visited = [start]
    while q:
        node = q.popleft()
        for adj in graph[node]:
            if adj not in visited:
                visited.append(adj)
                q.append(adj)

    return visited

def dfs_stack(start):
    stack = [start]
    visited = []
    while stack:
        node = stack.pop()
        visited.append(node)
        for adj in graph[node]:
            if adj not in visited:
                stack.append(adj)
    return visited

def dfs_recursive(start,visited = []):
    visited.append(start)
    for adj in graph[start]:
        if adj not in visited:
            dfs_recursive(adj,visited)
    return visited


print(bfs_queue(1))
print(dfs_stack(1))
print(dfs_recursive(1))

 

백트래킹

필요없는 경우를 가지치기 함으로써 시간 복잡도를 줄이는 방법

완전탐색을 좀 더 효율적으로 만들어준 기법. 또 하나의 함수를 만들어 사용하거나 if 문을 통해 구현한다.

 

 

---

알고리즘 문제

두가지 Sliding Window 문제를 풀어보았다. 포인터를 두개 선언해 주기보다 Start 와 for 문을 이용해서 구현하자!

Longest Substring Without Repeating Characters, Best Time to Buy and Sell Stock