잡담
어제 썼어야 되는데 정리를 못해서 오늘 일주일 회고록을 쓴다. 나는 개인적으로 일요일을 복습하는 날로 두는게 어려운 것 같다. 하루에 뭘 할지를 정해놔도 외부요소로 플랜을 못 이행할 때가 있다. 특히 5월 후반이라 그런지 프리가 된 친구들과 시간 많은 일요일에 만나 시간을 오래 보내게 된다.
저녁엔 가족이랑 좋아하는 음식점에서 외식했는데 빨리 먹고 가서 공부하자!라고 생각했던게 무색하게 그 순간에 빠져 호수 돌고 바다도 보고 추억 쌓다보니 하루 시간이 다 갔다. 내 일요일은 어디?
요번 주부터 나빼고 가족들이 가족여행을 떠나기 때문에 더 신나게 놀았던 것 같다. 다른 분들을 열심히 공부했을 것 같아서 오늘은 그냥 열공할 거다.
2주차 알고리즘
알고리즘은 어렵다. 그래서 차근차근 공부할 필요성을 느끼고 항해 커리큘럼을 따라가되, 기본 지식들 위주로 공부하기로 했다. 여기 개념들은 여러 블로그 돌아다니며 퍼온 지식들이라 아직 내 말로 풀어 설명해놓지 않았다. 나중에 한 꺼번에 정리를 해보자!
개념
추상 자료형이란? 자료구조란?
추상 자료형은 기능의 구현 부분 대신 데이터의 형태와 그 데이터의 연산들을 나타낸다. 자료구조(Data structure)는 추상 자료형이 정의한 연산들을 구현한 구현체를 가리킨다.
배열이란?
배열은 논리적인 순서와 물리적인 순서가 같다. 따라서 인덱스(index)를 통해 데이터에 접근할 수 있다. 다만 크기가 고정되어 있으므로 크기를 미리 알아야 하고 데이터의 삽입과 삭제 시 비용이 든다. 빈 엘리먼트를 허용하고, 중복 엘리먼트가 허용된다.
연결리스트란?
본래 리스트(List)는 추상 자료형이므로 구현 방법이 정의되어 있지 않다. 리스트를 구현하려면, 배열(Array) 또는 연결 리스트(LinkedList)를 이용하면 된다. 보통 리스트를 구현할 때 연결 리스트를 많이 사용하기 때문에, 리스트와 연결 리스트를 동의어로 많이 사용하고 있다.
- 연결 리스트는 Singly Linked List, Doubly Linked List, Double-ended Linked List 등 여러 유형들이 존재한다.
스택이란?
선형 자료구조의 일종으로 Last In First Out (LIFO)를 기반으로 한다. 데이터의 삽입이나 삭제는 "top"이라는 꼭대기에서만 수행된다. 새로운 원소를 삽입하면 스택 맨 위에 추가되고, 원소를 삭제하면 원소가 스택 맨 위에서 삭제된다.
스택이 유용한 경우는 재귀 알고리즘을 사용할 때다. 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어주고, 재귀 함수를 빠져나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼줘야 한다. 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
스택은 다음과 같은 연산이 존재한다.
- push(item) : 스택의 맨 윗부분에 원소를 추가한다.
- pop() : 스택의 맨 윗부분의 원소를 삭제한다.
- peek() : 스택의 맨 윗부분의 원소를 반환한다.
- isEmpty() : 스택이 비어있으면 true를 반환한다.
큐란?
선형 자료구조의 일종으로 First In First Out (FIFO)를 기반으로 한다. 한쪽 끝에서는 삽입 작업이 이루어지고, 반대쪽 끝에서는 삭제 작업이 이루어지므로 삽입된 순서대로 삭제된다. 참고로 데크(Deque)는 큐의 확장이며 자료구조의 양 끝에 원소를 추가하고 삭제할 수 있다.
큐는 너비 우선 탐색(BFS)을 하거나 캐시를 구현하는 경우에 종종 사용된다. 예를 들어 BFS의 경우, 처리해야 할 노드의 리스트를 저장하는 용도로 큐를 사용하여 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다. 이렇게 함으로써 노드를 접근한 순서대로 처리할 수 있게 된다.
큐는 다음과 같은 연산이 존재한다.
- add(item) : 리스트의 끝부분에 원소를 추가한다.
- remove() : 리스트의 맨 첫 부분의 원소를 삭제한다.
- peek() : 큐의 맨 윗부분의 원소를 반환한다.
- isEmpty() : 큐가 비어있으면 true를 반환한다.
해시테이블이란?
그래프
정점과 간선의 집합을 말한다. 단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조로, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다. 예를 들어 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방통행길), 선수 과목 등이 있다. 트리 또한 그래프 중 하나이며, 트리는 사이클이 허용되지 않는 그래프를 말한다.
무방향 그래프, 방향 그래프
말 그대로 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프를 무방향 그래프(Undirected Graph)라 하고, 간선에 방향성이 포함되어 있는 그래프를 방향 그래프(Directed Graph)라고 한다.
무방향 그래프(Undirected Graph)에서 각 정점(Vertex)에 연결된 Edge의 개수를 Degree라 한다. 방향 그래프(Directed Graph)에서는 간선에 방향성이 존재하기 때문에 Degree가 두 개로 나뉘게 된다. 각 정점으로부터 나가는 간선의 개수를 Outdegree라 하고, 들어오는 간선의 개수를 Indegree라 한다.
그래프 구현
- Adjacent matrix (인접 행렬)
정방 행렬을 사용하는 방법이다. 해당하는 위치의 value 값을 통해서 vertex간의 연결 관계를 O(1)으로 파악할 수 있다. Edge개수와는 무관하게 V^2의 Space Complexity를 갖는다. Dense graph를 표현할 때 적절할 방법이다.- Adjacent list (인접 리스트)
연결 리스트를 사용하는 방법이다. vertex의 adjacent list를 확인해봐야 하므로 vertex간 연결되어있는지 확인하는데 오래 걸린다. Space Complexity는 O(E + V)이다. Sparse graph를 표현하는데 적당한 방법이다.
DFS & BFS
둘 다 비선형 (nonlinear) 자료구조이다.
밑에 더 설명있다.
그래프 탐색하기
1. 깊이 우선 탐색 (Depth First Search, DFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다라는 방법을 우선으로 탐색한다. 일단 연결된 정점으로 탐색하는 것이다. 연결할 수 있는 정점이 있을 때까지 계속 연결하다가 더 이상 연결되지 않은 정점이 없으면 바로 그 전 단계의 정점으로 돌아가서 연결할 수 있는 정점이 있는지 살펴봐야 할 것이다. 갔던 길을 되돌아오는 상황이 존재하는 미로 찾기처럼 구성하면 되는 것이다.
- Stack 자료구조로 구현한다.
- 시간복잡도 : O(V+E) … vertex 개수 + edge 개수
- 너비 우선 탐색 (Breadth First Search, BFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. Tree에서의 Level Order Traversal 형식으로 진행되는 것이다.
- BFS에서는 자료구조로 Queue를 사용한다. 연락을 취할 정점의 순서를 기록하기 위한 것이다. 우선, 탐색을 시작하는 정점을 Queue에 넣는다.(enqueue) 그리고 dequeue를 하면서 dequeue 하는 정점과 간선으로 연결되어 있는 정점들을 enqueue 한다. 즉 vertex들을 방문한 순서대로 queue에 저장하는 방법을 사용하는 것이다.
- 시간복잡도 : O(V+E) … vertex 개수 + edge 개수 *! BFS로 구한 경로는 최단 경로이다.
References
