Data Structure(자료구조)
Array vs LinkedList
Array 가장 기본적인 자료구조인 array 자료구조는 논리적인 저장순서와 물리적인 저장순서가 일치한다. 따라서 인덱스로 해당 원소에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 O(1)에 해당원소로 접근할 수 있다. 즉 random access가 가능하다는 장점이 있는 것이다.
하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료 한뒤(O(1)), 또 한가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉, 빈공간이 생기게 되는 것이다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift 해줘야 하는 비용이 발생하고 이 경우 시간 복잡도는 O(n)가 된다. 그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity의 worst case는 O(n)이 된다.
삽입의 경우도 마찬가지이다. 만약 첫번째 자리에 새로운 원소를 추가하고자 한다면 모든 원소들의 인덱스를 1 씩 shift 해줘야 하므로 이 경우도 O(n)의 시간을 요구하게 된다.
LinkedList 이 부분에 대한 문제점을 해결하기 위한 자료구조가 연결리스트이다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 따라서 이 부분만 다른가뵤으로 바꿔주면 삭제와 삽입을 O(1)만에 해결할 수 있는 것이다.
하지만 LinkedList 역시 한가지 문제가 있다. 원하는 위치에 삽입을 하고자 하면 원하는 위치를 search과정에 있어서 첫번째 원소부터 다 확인해봐야 한다는 것이다. Array와 달리 논리적 저장순서와 물리적 저장순서가 일치하지 않기 때문이다. 이것은 일단 삽입하고 정렬하는 것과 마찬가지이다. 어떠한 원소를 삭제 또는 추가하고자 했을때 그 원소를 찾기위해서 O(n)의 시간이 추가적으로 발생하게 된다.
결국 linked list자료구조는 O(n)time complexity 를 갖고 삽입, 삭제에 대해서도 O(n)의 time complexity를 갖는다,
스택
한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO형식의 자료구조 스택의 연산은 가장 최근에 스택에 추가한 항목이 가장 먼저 제거된다.
스택의 활용 사례
재귀 알고리즘
웹브라우저 방문기록
실행 취소
역순 문자열 만들기
수식의 괄호 검사(연산자우선순위)
후위 표기법 계산(postfix)
큐
먼저 집어 넣은 데이터가 먼저나오는 FIFO구조로 저장하는 방식.
큐의 사용사례 : 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용.
BFS구현
처리해야할 노드의 리스트를 저장하는 용도로 큐를 사용
노드를 하나 처리할때 마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
노드를 접근한 순서대로 처리 할 수 있다.
노드를 접근한 순서대로 처리할 수 있다.
각종 대기열, 그리고 프로세스 관리에도 많이 쓰임.
트리
노드로 이루어진 자료구조.
하나이상의 루트 노드를 갖는다.
루트노드는 0개이상의 자식노드를 갖고 있다.
그 자식노드 또한 0개이상의 자식노드를 갖고 있고, 이는 반복적으로 정의된다.
트리의 구성요소
node(노드) : 트리를 구성하고 있는 각각의 요소를 의미한다.
edge(간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
Root Node(루트노드) : 트리구조에서 최상위에 있는 노드를 의미한다.
Terminal Node(=leaf Node, 단말노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
Internal Node(내부노드, 비단말 노드) : 단말노드를 제외한 모든 노드로 루트노드를 포함한다.
Binary Tree(이진트리)
루트노드를 중심으로 두개의 서브트리로 나누어 진다. 또한 나뉘어진 ㅜ 서브트리도 모두 이진 트리어야 한다. degree 가 2인 트리.
트리에서는 각 층별로 숫자를 매겨서 이를 트리의 레벨이라고 한다 레벨의 값은 0부터 시작하고 따라서 루트노드의 레벨은 0이다. 그리고 트리의 최고 레벨을 가리켜 해당 트리의 height(높이)라고 한다.
Full Binary Tree(포화 이진트리) vs Complete Binary Tree(완전 이진트리)
모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진트리라고 한다. 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진트리라고 한다. 배열로 구성된 포화 이진트리와 완전이진 트리는 노드의 개수가 n개일때, i번째 노드에 대해서 parent(i)= i/2, left_child(i) = 2i, right_child(i) = 2i+1 의 index 값을 갖는다.
BST(Binary search tree) 효율적인 탐색을 위해서는 어떻게 찾을까만 고민해서는 안된다. 그보다는 효율적인 탐색을 위한 저장방법이 무엇일까를 고민해야되는데 이진탐색 ㅡ리는 이진트리의 일종이다. 단 이진탐색 트리에는 데이터를 저장하는 규칙이있다. 이게 특정 데이터의 위치를 찾는데 사용할 수 있다. 1. 이진탐색 트리의 노드에 저장되는 키는 유일하다. 2. 루트 노드의 키가 왼쪽서브트리를 구성하는 어떠한 노드의 키보다 크다. 3. 루트노드의 키가 오른쪽 서브트리를 구성하는 어떠한 노드의 키보다 작다. 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
이진탐색 트리의 탐색연산은 O(logn)의 시간복잡도를 갖는다. 최악의 상황은 skewed tree(편향트리) 이때는 저장순서에 따라 한쪽으로만 노드가 추가되는 상황인데 이때가 worst case의 탐색이며 O(n)의 시간 복잡도를 갖게된다. 이 issue를 해결하기 위한 기법이 rebalancing 기법이다.
Red Black Tree
레드블랙 트리가 필요한 이유 : 이진 탐색 트리중에 값이 편향되게 들어 오는 경우가 있다. 그렬경우, 이진 탐색 트리의 검색효율을 나쁘게 하므로, 균형을 바로잡기위해 레드블랙 트리라는 알고리즘을 사용하도록 한다.
레드블랙 트리의 정의 Red-Black Tree 는 다음의 성질을 만족하는 BST이다.
각 노드는 Red or Black 이라는 색깔을 갖는다.
Root node의 색깔은 무조건 Black이다.
각 leaf node는 black이다.
어떤 노드의 색깔이 red라면 두 개의 children 의 색깔은 모두 black이다. black 노드이 자식들은 어느 색깔이든 상관없다.
각노드에 대해서 노드로부터 descendant leaves 까지의 단순 경로는 모두 같은수의 black node를 포함하고있다. 이를 해당노드의
black-height라고 한다.
레드블랙 트리의 특징
기본적으로 레드블랙 트리는 이진 탐색 트리를 베이스로 하기 때문에 이진 탐색 트리의 특성을 모두 갖는다.
루트 노드부터 리프노드까지의 모든 경로중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다. 이러한 상태를 balanced 상태라고 한다.
노드의 child 가 없을 경우 child를 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL들을 leaf node로 간주한다.
삽입 우선 BST의 특성을 유지하면서 노드를 삽입을 한다. 그리고 삽입된 노드의 색깔을 Red로 지정한다. red로 지정하는 이유는 blakc-height 변경을 최소화 하기 위함이다. 삽입결과 RBT의 특성을 위배시 노드의 색깔을 조정하고, black-height 가 위배되었다면 rotation을 통해 height를 조정한다. 이러한 과정을 통해 RBT의 동일한 height에 존재하는 internal node 들의 Black-height가 같아지게 되고 최소 경로와 최대 경로의 크기 비율이 2 미만으로 유지된다.
삭제 삭제도 삽입과 마찬가지로 BST의 특성을 유지하면서 해당 노드를 삭제한다. 삭제될 노드의 child의 개수에 따라 rotation 방법이 달라지게 된다. 그리고 만약 지워진 노드의 색깔이 balck 이라면 black-height가 1 감소한 경로에 black node가 1개 추가 되도록 rotation하고 노드의 색깔을 조정한다. 지워진 노드의 색깔이 red 라면 violation이 발생하지 않으므로 RBT가 그대로 유지된다.
힙
우선순위 큐(Priority Queue)를 위하여 만들어진 자료구조.
우선순위 큐 : 우선순위의 개념을 큐에 도입한 자료구조.
데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.
우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다 이중 힙(heap)으로 구현하는 것이 가장 효율적이다.
힙이란?
완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조.
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조.
힙은 일종의 반정렬 상태를 유지한다.
큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도.
간단히 말하면 부모 노드의 키 값이 자식 노드의 키값 보다 항상( 큰(작은) 아진 트리를 말한다.
힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
힙 종류
최대 힙(max heap)
부모노드의 키값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
key(부모노드)>= key(자식노드)
최소 힙(min heap)
부모노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리.
key(부모노드) >= key(자식 노드)
힙의 구현
힙을 저장하는 표준적인 자료구조는 배열이다.
구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 o는 사용되지 않는다.
특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
예를들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
힙에서의 부모 노드와 자식 노드의 관계
left child의 인덱스 = (부모의 인덱스) * 2
right child의 인덱스 = (부모의 인덱스) * 2 +1
부모의 인덱스 = (자식의 인덱스) / 2
그래프
정점과 간선의 집합,그래프 트리또한 그래프이고, 그중 사이클이 허용되지 않는 그래프를 말한다.
그래프 관련 용어
Undirected Graph : 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프.
Directed Graph : 간선에 방향성이 포함되어 있는 그래프.
Degree Undirected Graph에서 각 정점에 연결된 edge의 개수를 Degree라 한다. Directed Graph 에서는 간선에 방향성이 존재하기 때문에 Degree가 두개로 나뉜다. 각 정점으로부터 나가는 간선의 개수를 Outdegree라 하고, 들어오는 간선의 개수를 indegree라 한다.
그래프를 구현하는 두방법
인접행렬 (adjacent matrix): 정방 행렬을 사용하는 방법 해당하는 위치의 value 값을 통해서 vertex 간의 연결 관계를 O(1)으로 파악할 수 있다. Edge 개수와는 무관하개 V^2의 Space Complexity 를 갖는다 Dense graph를 표현할 때 적절한 방법이다.
인접 리스트 : 연결리스트를 사용하는 방법 vertex의 adjacent list를 확인해봐야 하므로 vertex 간 연결되어 있는지 확인하는데 오래 걸린다. Space Complexity 는 O(E+V)이다. Space graph를 표현하는 데 적당한 방법이다.
그래프 탐색
DFS stack 자료구조를 이용. 그래프 상에 존재하는 임의의 한 정점으로 부터 연결 되어 있는 한 정점으로만 나아간다는 방법을 우선으로 탐색. 일단 연결된 정점으로 탐색하는 것이다. 연결할 수 있는 정점이 있을 때까지 계속 연결하다가 더이상 연결되지 않은 정점이 없으면 바로 그 전단계의 정점으로 돌아가서 연결 할 수 있는 정점이 있는지 살펴봐야 할 것이다. 갔던 길을 되돌아 오는 상황이 존재하는 미로찾기처럼 구성하면 되는 것이다. Time Complexity : O(V+E) vertex개수 + edge 개수 BFS 그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. Tree에서의 Level Order Travelsal 형식으로 진행되는 것이다. BFS에서는 자료구조로 Queue를 사용한다. 연락을취할 정점의 순서를 기록하기 위한 것이다. 우선 탐색을 시작하는 정점을 queue에 넣는다. 그리고 dequeue를 하면서 dequeue한느 정점과 간선으로 연결되어 있는 정점들을 enqueue한다. 즉 vertex들을 방문한 순서대로 queue에 저장하는 방법을 사용하는 것이다. Time Complexity : O(V+E) vertex개수 + edge개수 BFS로 구한 경로는 최단 경로이다.
Minimum Spanning Tree
그래프 G의 spanning tree 중 edge weight의 합이 최소인 spanning tree를 말한다. 여기서 말하는 spanning tree란 그래프 G의 모든 vertex 가 cycle없이 연결된 형태를 말한다.
Kruskal Algotithm 초기화 작업으로 edge 없이 vertex 들로만 그래프를 구성한다. 그리고 weight가 제일 작은 edge부터 검토한다. 그러기 위해선 Edge set을 오름차순 으로 sorting 해야한다. 그리고 가장 작은 weight에 해당하는 edge를 추가하는데 추가할때 그래프에 cycle이 생기지 않는 경우에만 추가한다. spanning tree 가 완성되면 모든 vertex들이 연결된 상태로 종료가 되고 완성될 수 없는 그래프에 대해서는 모든 edge에 대해 판단이 이루어 지면 종료된다.
Cycle 판별법 방문체크후 그지점이 방문한 지점인데 시작지점일 경우 cycle.
Prim Algorithm
초기화 과정에서 한개의 vertex로 이루어진 초기그래프 A를 구성한다. 그리고나서 그래프 A내부에있는 vertex로 부터 외부에 있는 vertex사이의 edge를 연결하는데 그 중 가장 작은 weight의 edge를 통해 연결되는 vertex를 추가한다. 어떤 vertex건 간에 상관없이 edge의 weight를 기준으로 연결하는 것이다. 이렇게 연결된 vertex는 그래프 A에 포함된다. 위 과정을 반복하고 모든 vertex들이 연결되면 종료한다.
Sorting
Last updated
Was this helpful?