[항해] 알고리즘 1주차 회고 (자료구조-알고리즘)

이번주는 폭풍의 시간이 었다. 자료구조를 배우고 알고리즘을 배우고 빠르게 진행된다.

빠르게 배우고 적용시켜서 문제를 풀려고 해도 잘 풀리지 않는게 코딩테스트 문제인거 같다.

1일차에는 알고리즘 개요와 배열을 간단히 배운다.

(간단하지만 간단한게 아니다.)

알고리즘 개요

점근 표기법

알고리즘의 성능을 수학적으로 표기하는 방법이다. 알고리즘의 "효율성"을 평가하는 방법

점근 표기법의 종류

점근 표기법의 종류에는
빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있다.

빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지,
빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기하는것이다.

예를 들어
빅오 표기법으로 표시하면 O(N),
빅 오메가 표기법으로 표시하면 Ω(1) 의 시간복잡도를 가진 알고리즘이다!
라고 표현할 수 있다.

알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석한다.
이유는 대부분의 입력값이 최선의 경우일 가능성은 굉장히 적을 뿐더러, 최악의 경우를 대비해야 하기 때문이다.

시간복잡도?

입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말한다.
입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것과 같다.

공간 복잡도?

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다.
입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것이다.

2일차에는 연결리스트에 대해서 배운다.
여전히 잘 적응이 안된다. 배운내용은 이해가 되지만 문제로 적용시키는게 너무 어려운 일이다.
쉬운 문제부터 풀었고, 40분동안 풀지못하면 답을 보고 이해하는 방식으로 진행했다.

연결리스트

배열과 연결리스트

• 어레이: 파이썬의 리스트. 접근 쉬움, 삽입 어려움. (파이썬의 리스트)
• 연결리스트: 직접 구현. 접근 어려움, 삽입 쉬움.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


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

    def append(self, val):
        if not self.head:
            self.head = ListNode(val, None)
            return

        node = self.head
        while node.next:
            node = node.next

        node.next = ListNode(val, None)

연결리스트를 직접 구현 할 수 있는게 중요한 사항이었다. 빈 파일에서 부터 작성 할 수 있게 연습해봤다.

3일차에는 스택에 대해서 배운다.

스택

한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조로 쌓아져 있는 책이나 빨래통을 떠올리면 된다.

가장 밑에 있는 데이터는 뺄 수 없다.
가장 위에서만 데이터를 빼거나 넣을 수 있다.
가장 처음 넣은 데이터는 가장 늦게 나오게 되는 것이다.

이런 자료 구조를 Last In First Out 이라고 해서 LIFO 라고 부른다.

컴퓨터의 되돌리기 기능이 스택으로 되어있다고 생각하면 된다.

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

스택은 그나마 이해하기가 쉬웠고 어느정도 적용이 잘 되었던 자료구조 이다.
1일차만 하더래도 답안을 보고 이해만 했는데 3일차 쯤 되니까 1~2문제씩 풀리는 문제가 생기기도 한다.
하지만 여전히 어렵고 복잡한건 마찬가지 이다.

큐

한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조

큐는 줄 서기를 생각하면 된다.
한 줄로 섰다가, 한 줄로 나오는 방식의 자료구조이다.

데이터를 한쪽 끝으로 넣고, 반대쪽으로 빠져 나오는 것이다.

이런 자료 구조를 First In First Out 이라고 해서 FIFO 라고 부릅니다. ( 선입선출 )

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

4일차에 큐를 배웠는데 큐도 어느정도 이해는 되는 자료구조이다. 몇 문제 안풀었는데 시간이 진짜 빠르다. 강의듣고 문제풀면 점심먹고 다시 앉아서 문제풀고 팀별로 이야기하고 밥먹으면 전체 과제톡하면 하루가 끝나 있다.
지금 내가 잘 하고 있는 건지 실력은 늘고 있는건지 잘 모르겠다. 그래도 다들 버티는게 이기는거라고 이야기 한다. 학습 분위기가 진짜 좋은거 같아서 나도 더 많이 공부하려고 한다.

5일차에는 해시테이블을 배우는데 미리 정리해둔 부분이 있어서 내 링크를 첨부해 두었다.

해시 테이블

https://geonoo.tistory.com/96

[자료구조] 해시테이블

DFS - 깊이 우선 탐색

그래프?
자료구조는 크게 비선형구조, 선형구조로 구분된다.
선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다.
이번 자료구조인 그래프는 바로 연결 관계에 초점이 맞춰져 있다.

노드(Node): 연결 관계를 가진 각 데이터를 의미합니다.
간선(Edge): 노드 간의 관계를 표시한 선.
인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

참고로 그래프는 유방향 그래프와 무방향 그래프 두가지가 있다고 합니다.
유방향 그래프(Directed Graph): 방향이 있는 간선을 갖습니다.
간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있습니다.
무방향 그래프(Undirected Graph)는 방향이 없는 간선을 갖습니다.

그래프의 표현방법
인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현
인접 리스트(Adjacnecy List): 링크드 리스트로 그래프의 연결 관계를 표현

          2 - 3
          ⎜       
      0 - 1

1. 이를 인접 행렬, 2차원 배열로 나타내면 다음과 같습니다!
  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]
}

위 두 방식의 차이는 시간 VS 공간 이다.

인접 행렬으로 표현하면 즉각적으로 0과 1이 연결되었는지 여부를 바로 알 수 있다.
그러나, 모든 조합의 연결 여부를 저장해야 되기 때문에 O(노드^2) 만큼의 공간을 사용해야 한다.

인접 리스트로 표현하면 즉각적으로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 한다.
따라서 연결되었는지 여부를 알기 위해서 최대 O(간선) 만큼의 시간을 사용해야 한다.
대신 모든 조합의 연결 여부를 저장할 필요가 없으니 O(노드 + 간선) 만큼의 공간을 사용하면 된다.

 

DFS는 Depth First Search 라고 한다.
갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조입니다.
 - 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다. 
 - 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.
 - 위 과정을 반복한다.

DFS 부터는 감을 잡기가 어렵다.
손으로 그려보고 머릿속으로 생각하고 문제에 적용시켜보고 반복하면 조금씩 보일거라고 생각한다. ( 재귀적 공부법인가... )
역시 구글링해서 답안을 보고 이해하는 방식으로 진행했고,
재귀방식이나 스택방식이 있는데 재귀 방식이 코드가 깔끔하게 나와서 재귀방식을 연습하고 있다.

그래프 탐색은 나중에 한번더 포스팅을 해야겠다. 

BFS - 너비 우선 탐색

인접 노드를 먼저 방문하는 탐색 방법

BFS 는 현재 인접한 노드 먼저 방문해야 한다.
인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다.
가장 처음에 넣은 노드들..? → 큐를 이용하면 BFS 를 구현할 수 있다.
 1. 루트 노드를 큐에 넣습니다.
 2. 현재 큐의 노드를 빼서 visited 에 추가한다.
 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
 4. 2부터 반복한다.
 5. 큐가 비면 탐색을 종료한다.

백트레킹

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아 가는 방식이다.

그래서, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다.

이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다.

일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있습니다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다.

 

회고

금, 토, 일, 월, 화, 수, 목, 금, 토 - 8일 동안의 알고리즘 주차에 대한 이야기

해야 할 일 목록

8일 이라는 시간동안 내가 공부 했던 것들을 쭉 돌아 봤다.
어느날은 과제하기도 벅찬 날이 있었고 어느날은 많은 양을 소화 해냈다.
해왔던 일들을 다시 돌아 보니까 뿌듯했다. 앞으로도 계속 할 일을 적어놓고 하루를 시작 해야겠다.

이틀 전에는 좀 복잡한 생각이 들었다.
함께 달려가고 있는 동료들을 보면 나는 뒤떨어지는게 아닌가 싶을 정도로 잘 하시는 분들이 많다.
그거에 자극이 되기도 하고 가끔은 힘들게도 하기도 한다.

잘 안 풀린다고 너무 힘들어 하지 말자, 누군가는 나보다 더 많은 시간을 들여 노력했을 거다.
그 노력한 시간은 생각하지 못하고 부러워만 했던건 아닐까 반성해본다.

지금은 이 시간들이 후회되지 않게 내가 최선을 다하면 되는 것이다. 힘내 보자!