data structure
[Data Structure] BFS (너비 우선 탐색)
[Data Structure] BFS (너비 우선 탐색)
2021.06.25Bredth-First-Search (너비 우선 탐색)란? BFS의 원리는 간단하게 말하면 퍼지는 물결파 이다. 잔잔한 호수에 돌을 던져 생기는 물결파를 떠올려 보자. 동그란 원형의 파원을 일으키며 퍼져나간다. 이렇게 동일한 거리의 지점들은 동시에 탐색을 하는 방법이다. 핵심은 1번의 탐색 루틴에서 하나의 level에 있는 모든 정점을 탐색한다는 것이다. 저번 DFS처럼 BFS방식을 그래프를 통해 설명해보겠다. 앞서 DFS에서 사용한 그래프와 동일한 형태의 그래프다. DFS와 마찬가지로 1번 정점부터 탐색을 시작해보자. 1번 정점을 탐색 완료했다면 현재 정점의 인접하는 정점들을 확인한다. BFS는 다음에 탐색할 위치를 인접한 모든 정점으로 선택한다. 따라서 다음 탐색은 2, 3번 정점으로 이동한다. 원리..
[Data Structure] DFS (깊이 우선 탐색)
[Data Structure] DFS (깊이 우선 탐색)
2021.06.24그래프 탐색 (Graph Search) 앞서서 그래프를 배웠다. 트리에 트리를 탐색하는 트리 순회가 있었다면, 그래프는 그래프 탐색이 존재한다. 그래프 탐색 방법에는 DFS와 BFS가 존재한다. 이번 글에서는 DFS에 대해서 이야기할 예정이다. 그래프 탐색을 배우는 이유는 그래프의 이동 경로나 생김새를 파악하기 위해서 사용한다. 탐색을 통해서 그래프에 사이클이 몇개고, 전체적인 묶음이 몇개인지 알 수 있기때문이다. DFS VS BFS DFS는 깊이 우선 탐색(Depth-First-Search)의 약자이고 BFS는 너비 우선 탐색(Bredth- First-Search)의 약자이다. 이름에 탐색 방식이 들어가 있다. DFS는 깊게 들어가는 것을 우선으로 하는 탐색방식이고 BFS는 넓은 분포, 즉 한 leve..
[Data Structure] Graph (그래프)
[Data Structure] Graph (그래프)
2021.06.24Graph (그래프) 그래프란 정점과 간선으로 구성된 자료구조이다. 일반적으로 G = (V,E)로 나타내는데, V는 vertices로 정점을 말하고, E는 edges인 간선을 의미한다. |V|는 정점의 개수를 의미하고 |E|는 간선의 개수를 의미한다. 그래프는 간선의 종류에 따라 2가지로 구분할 수 있다. 그리고 그 종류에서도 그래프의 특징으로 종류를 더 세분화할 수 있다. 그래프의 종류 그래프는 간선의 종류로 크게 2가지로 나눠지게 된다. 무향 그래프 (undirected graph) 유향 그래프 (directed graph) 명칭에서 보이듯이 그래프의 간선에 방향성이 있고 없고의 차이를 보여준다. 무향 그래프 (undirected graph) 그래프의 이름 그대로 간선에 방향성이 존재하지 않는다. 그..
[Data Structure] Binary Search Tree (이진 탐색 트리)
[Data Structure] Binary Search Tree (이진 탐색 트리)
2021.06.24Binary Search Tree (이진 탐색 트리) 이진 탐색 트리는 앞서서 배운 트리의 확장적인 형태라고 보면 편하다. 일반적인 이진 트리는 탐색의 기준이 없어서 특정 데이터를 찾으려면 모든 노드를 탐색해야한다. 하지만 이진 탐색 트리에서는 평균적으로 훨씬 빠른 시간에 탐색이 가능해진다. Binary Search (이진 탐색) 우선 이진 탐색과 이진 탐색 트리를 구분해야 한다. 전자는 알고리즘의 일종이고 후자는 자료구조의 일종이다. 이진 탐색 트리의 원리를 알기 이전에 이진탐색의 원리를 알아야 한다. 이진 탐색은 간단하게 말하면 탐색 범위를 절반으로 줄여나가는 탐색이다. 바로 이전 포스트에서 말한 search table과 같다. 굳이 자세한 설명을 더 하진 않겠다. 이런 이진 탐색을 트리 형태로 구조..
[Data Structure] Hash (해시)
[Data Structure] Hash (해시)
2021.06.24Dictionary (딕셔너리) 딕셔너리는 사실 C++보다는 파이썬에서 더 익숙할 것이라 생각된다. 실제로 딕셔너리라고 아예 명확하게 말을 하기도 하니까... 자료구조에서 딕셔너리는 key와 value를 함께 저장하는 entry 저장 자료구조이다. 대신 key의 중복을 허용한다. 시간 복잡도 딕셔너리의 시간복잡도는 딕셔너리를 리스트 구현을 기준으로 얘기를 해보겠다. 딕셔너리의 ADT는 우선적으로 put, find, erase정도각 대표적이다. put 함수는 리스트에서 바로 맨 뒤나 맨 앞에 저장하는 방식을 활용한다. 당연히 이 함수는 \(O(1)\)의 시간복잡도를 갖는다. 보통 doubly-linked list나 배열로 구현을 한다. find와 erase는 doubly linked list를 기준으로 우..
[Data Structure] Priority Queue (우선순위 큐)
[Data Structure] Priority Queue (우선순위 큐)
2021.06.24Priority Queue (우선순위 큐) 이전에 큐에 대해서 배운 적이 있다. 이렇게 일반적인 큐를 FIFO Queue라고 한다. FIFO원리를 갖고 있는 큐이기 때문이다. 이번 시간에는 다른 성질을 갖는 우선순위 큐에 대해서 이야기해보겠다. 우선순위 큐는 이름에 특징이 잘 나와있는데, 큐의 pop 연산수행을 진행할 때, 프로그래머가 정해놓은 우선순위에 맞춰서 제거 연산을 진행한다. 일반적으로는 우선순위 기준은 2가지인데, 크기가 큰 값을 우선순위로 두는 Max-Priority-Queue 크키가 작은 값을 우선순위로 두는 Min-Priority-Queue 가 있다. 우선순위 큐와 큐는 잘 알아둘 필요가 있는 이유가 있다. 이전 글에서 트리의 탐색 방식은 향후 그래프 탐색방법인 DFS와 일맥상통한다고 했..
[Data Structure] Binary Tree (이진트리) & Tree 구현
[Data Structure] Binary Tree (이진트리) & Tree 구현
2021.06.24Binary Tree (이진트리) 이진트리 개념 이진트리는 우리가 이전에 배운 트리의 특수한 형태이다. 일반 트리가 자식 수에 제한이 없다면, 이진트리는 1부모에 최대 2개의 자식 노드가 존재한다. 보통 왼쪽 노드, 오른쪽 노드라고 부르며 왼쪽 노드가 오른쪽 노드보다 우선하는 성질을 가진다. 일반 트리에서 설명하지 않았지만 트리는 자식간에 순서가 있는 ordered pair이다. 이진트리의 쓰임새는 아래와 같은 것들이 있다. 수식의 표현 트리 수식의 계산 트리 결정트리 우선 결정트리부터 설명해보면 internal node는 결정요소를 갖고있고 external node는 해당 결정요소에대한 결정 값들을 갖고있다. 후에 서술할 중위순회를 이용하면 수식을 표현할 수 있다. 완전 이진트리의 성질 완전 이진트리는..
[Data Structure] Vector and List (벡터와 리스트)
[Data Structure] Vector and List (벡터와 리스트)
2021.03.03Vector (벡터) 벡터 개념 벡터는 크기가 동적으로 변하는 배열이라고 생각하면 된다. Array list라고 부르기도 하며 다양한 데이터들이 배열의 형태로 저장된 연속체라고 생각하면 된다. 삽입, 삭제, 접근 연산이 모두 index에의해 이뤄지게 된다. Vector ADT 벡터의 추상자료형은 다음과 같다. at(integer i) : index i에대해서 데이터 값을 반환해준다. set(integer i, object o) : index i의 데이터를 o로 바꿔준다. insert(integer i, object o) : index i에 o를 삽입한다. earase(integer i) : index i에 있는 데이터를 제거해준다. size() : 벡터의 크기를 반환해준다. empty() : 벡터가 비었..
[Data Structure] Queue(큐)
[Data Structure] Queue(큐)
2021.03.03Queue (큐) 큐 개념 큐의 삽입과 삭제의 원리는 First-In First-Out(FIFO, 선입선출)로 작동한다. 가장 먼저 들어온 데이터가 가장 먼저 나가게된다. 큐의 실제 활용 예시는 다음과 같다. 대기열 공유자원의 접근권한, 순서 멀티 프로그래밍 과정 Queue ADT 큐의 추상자료형은 다음과 같다. enqueue(object) : 데이터를 큐의 제일 마지막에 삽입한다. dequeue() : 큐의 가장 앞에 있는 데이터를 제거한다. object front() : 큐의 가장 앞에 있는 데이터를 반환해준다. integer size() : 큐에 저장된 원소들의 개수를 반환해준다. boolean empty() : 큐가 비어있는 지를 확인해준다. Queue implementation (큐 구현) 큐의..
[Data Structure] Stack(스택)
[Data Structure] Stack(스택)
2021.03.03Abstract Data Types (추상 자료형) 추상 자료형 (ADTs)는 한마디로 말하면 알고리즘의 요약본이다. ADT는 correctness와 performance를 독립적으로 생각하게 해줄 수 있다. Correctness는 일반적으로 interface라고도 하는데, input이 들어왔을 때, output의 일치 정확도가 얼마나 높은 가를 말한다. Performance는 implementation이라고 하며 time complexity와 같은 것을 말한다. ADT를 짤 때는 해당 알고리즘의 기능만을 고려하며 성능과 자세한 구현을 고려하지 않는다. Stack (스택) 스택 개념 스택의 삽입과 삭제 원리는 Last-In First-Out(LIFO, 후입선출)로 작동한다. 말 그대로 가장 나중에 들어온..
[Data Structure] Analysis of Algorithms (알고리즘 분석)
[Data Structure] Analysis of Algorithms (알고리즘 분석)
2021.03.03Algorithm Analysis (알고리즘 분석) Asymtotic Analysis (점근적 분석) 알고리즘을 비교, 분석할 때는 일반적으로 점근적 분석방법을 따른다. 점근적 분석방법은 아래의 과정들로 진행된다. 의사코드 (pseudo code) 연산자 개수 카운트 (primitive operation counting) input size n에 대한 함수로 표현 Big-O notation으로 표기 위 순서에 있는 내용을 기준으로 이번 글을 다루겠다. Running time (실행시간) 알고리즘의 개념적 정의는 아래와 같다. 0개 이상의 입력값이 주어질 때, 1개 이상의 출력이 나오는 절차나 방법 이런 정의에서 알 수 있듯이 우리는 특정 입력 값의 크기에따른 출력의 결과를 계산해야한다. 출력결과가 나오기..
[Data Structure] Linked List (연결 리스트)
[Data Structure] Linked List (연결 리스트)
2021.03.03Linked list (연결 리스트) 링크드 리스트와 배열 Linked list (연결 리스트)와 가장 많이 비교되는 자료구조에는 Array (배열)가 있다. 두 자료구조 모두 linear order data structure로, 선형 저장구조를 갖고 있다. 선형 저장구조를 갖고 있다는 의미는 데이터 간의 전후관계가 존재한다는 의미와도 같다. 두 자료구조의 차이점에는 데이터 접근성과 size의 변동성이 있다. Array (배열) 배열은 임의의 인덱스에 빠르게 접근이 가능하다. 접근하고자 하는 index를 알기만 하면 O(1)시간에 접근이 가능하다. 배열을 선언할 때 memory를 선언하고 할당하기 때문에 제한된 메모리 크기를 갖는다. 그로인해 한 번 선언한 배열의 크기는 변경 할 수 없다는 단점이 있다...