Data Structure
-
Heap(힙)Data Structure 2022. 9. 6. 15:56
이진 탐색 트리에 이어 트리와 유사한 구조를 가진 Heap에 대해서 알아보자. Heap(힙) 이란? 들어간 순서에 상관없이 우선 순위를 근거로 dequeue 연산을 진행하는 우선순위 큐의 형태 Max Heap과 Min Heap 두가지 컨셉이 존재한다. 부모와 자식의 key 값은 같은 경우 허용함 완전 이진 트리의 형태 ■ Max Heap - key 값이 큰 노드가 가장 우선 순위가 높음 - 각 노드의 key 값이 자식의 key 값보다 큰 트리 - 완전 이진 트리 ■ Min Heap - key 값이 작은 노드가 가장 우선 순위가 높음 - 각 노드의 key 값이 자식의 key 값보다 작은 트리 - 완전 이진 트리 1) Heap 삽입 연산(Max Heap에서) 20 15 19 8 13 10 23을 삽입(배열의..
-
Binary Search Tree(이진 탐색 트리)Data Structure 2022. 9. 4. 14:07
이진 탐색 트리를 설명하기에 앞서 트리 구조에 대해 먼저 알아보자. 트리 구조란? 하나의 루트(root) 노드를 가진다. 나머지 노드들은 부모와 자식 관계의 노드들로 간선으로 이어진 계층형 자료 구조이다. 이진 트리란? 이진 트리는 트리의 모든 차수가 2인 트리를 말한다. 차수는 노드의 서브트리 개수를 말하는데 트리 내부의 서브트리가 항상 2개인 트리를 이진 트리라고 부른다. 이진 탐색 트리란? 탐색(검색)을 효율적으로 하기 위한 트리 구조 이진 트리이며 모든 원소는 서로 다른 유일한 key를 가진다. 왼쪽 서브트리의 key값 < 루트의 key값 < 오른쪽 서브트리의 key값의 법칙을 항상 따른다. 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리이다. 1) 탐색 연산 탐색할 key값 x를 루트 노드의 ..
-
Graph(BFS 너비우선탐색)Data Structure 2022. 8. 31. 15:43
지난 시간 DFS(깊이우선탐색)에 이어 BFS(너비우선탐색)에 대해서 알아보자. BFS(너비우선탐색) 시작 정점에서 가까운 정점이 먼 정점보다 먼저 방문되도록 하는 방식 시작 정점 v를 방문 v에 인접한 모든 정점들을 방문 새롭게 방문한 정점들에 인접하면서 과거에 방문하지 않은 정점들을 모두 방문 Queue를 이용 다음 탐색을 위해서는 Queue에서 dequeue를 하고 dequeue를 한 노드에서 시작한다. 이제 G7 그래프를 가지고 BFS 알고리즘에 대해서 알아보자. 위와 같은 G7 그래프가 있다. 이전 DFS 알고리즘과 같은 그래프를 가지고 BFS 알고리즘은 어떤 경로를 따라 최단경로를 찾는지 비교하면서 살펴보자. Queue 1) 시작정점 A에서 BFS 알고리즘을 시작한다. 2) 정점 A에서 방문하..
-
Graph(DFS 깊이 우선 탐색)Data Structure 2022. 8. 29. 10:43
코딩테스트를 위해 백준이나 프로그래머스를 보다보면 DFS, BFS 용어에 대해서 한 번쯤은 듣게 될 것이다. DFS 원리와 BFS 원리를 적용하면 최단 경로를 쉽게 찾을 수 있다고 하는데, 오늘은 그 원리에 대해 알아보자. DFS(깊이 우선 탐색) 하나의 정점을 방문한다. 이웃한 정점으로 갈 수 있다면 무조건 이웃 정점 하나로 방문한다.(과거에 방문하지 않은 새로운 정점) 시작점으로부터 점점 깊어지는 노드로 전진하게 된다. 방문 가능한 이웃 정점이 없다면 backtracking을 통해 경로 상 가장 최근 방문했던 정점으로 돌아가서 또다른 새로운 노드 방문을 시도 한다.(stack 이용) 반드시 오름차순에 따라 이동한다.(경로상 갈림길을 만났을 때) 새로운 이웃한 노드가 존재하면 stack에 위치한 지점을..
-
Dijkstra Algorithm(다익스트라 알고리즘)Data Structure 2022. 8. 26. 16:13
최단 경로 알고리즘 중 가장 많이 사용된다고 할 수 있는 다익스트라 알고리즘에 대해서 알아보자 특징 : 무방향 그래프, 방향 그래프에 모두 적용 가능하다. 가정 : 모든 간선은 음이 아닌 비용을 가진다. ■ 다익스트라 알고리즘의 Concept 시작 정점 ~ 모든 다른 정점까지의 최단 경로를 구한다. 시작 정점 v에서 정점 u까지의 최단경로 dist[u]를 구해 정점 u가 집합 S에 추가되면 정점 u에 의해 단축되는 경로가 있는지를 반복적으로 확인한다. 현재 알고 있는 dist[w]와 새로 추가된 정점 u를 거쳐가는 dist[u] + cost[u][w]를 비교해 더 단축된 작은 값을 새로운 dist[w]로 가중치를 수정한다. dist A B C D E 0 10 5 ∞ ∞ pred A B C D E A A ..
-
6. List#1 - LinearListData Structure 2022. 3. 20. 11:56
List는 크게 LinearList와 LinkedList로 분류할 수 있다. 이 중 오늘은 LinearList에 대해서 다루어 보고자 한다. LinearList는 자료구조의 가장 단순한 나열 방식으로 순서를 가진 항목들의 모임이다. 다시 말해 일반적으로 쓰는 Array 배열과 같다고 생각하면 된다. -> 장점 : 구현이 간단하다. -> 단점 : 삽입, 삭제 시 오버헤드 항목의 개수 제한으로 비효율적이다. LinearList를 구현할 기본 함수를 먼저 셋팅해 주었다. ※ 원소 삽입 중간에 원소가 삽입되면, 그 이후 원소들은 한 자리씩 자리를 뒤로 이동해서 물리적 순서를 논리적 순서와 일치시켜야 한다. ① 원소를 삽입할 빈자리를 만든다. ② 준비한 빈 자리에 원소를 삽입한다. 기존 배열 10 20 30 40..
-
5. Recursion(재귀)Data Structure 2022. 3. 19. 21:35
학기가 시작되면서 블로그 포스팅을 하기가 너무 빡세다... 해서 수업시간에 배운 자료구조 및 알고리즘들을 조금씩 틈을 내서 포스팅 해 보고자 한다. 오늘은 재귀(recursion) 알고리즘에 대한 포스팅이다. 재귀는 함수 안에 함수를 다시 호출하여 반복하는 알고리즘이다. 구현 하기가 어렵지만 구현을 성공하면 생각보다 길이도 짧으면서 다른 사람들이 보기에도 쉬운 멋진 알고리즘이다. 대표적인 재귀 알고리즘 3가지를 소개해 보고자 한다. #1. 피보나치 수열 우리가 흔히 알고있는 피보나치 수열은 0 1 1 2 3 5 8 13 21 34 55 69 124 이런식으로 n-2와 n-1의 자리를 더한 값을 n값으로 하는 알고리즘이다. 위의 재귀함수로 간단하게 구현할 수 있다. #2. 하노이 탑 하노이 탑은 구글에서 ..
-
4. Queue(큐)Data Structure 2022. 1. 28. 11:13
큐란? - 스택과 유사하게 데이터를 일시적으로 쌓아 두기 위한 자료구조, 선입선출(FIFO)형식이다. **enQueue(인큐)와 deQueue(디큐) - enQueue : 큐에 데이터를 넣는 작업을 말한다.(rear에서 넣음) - 시간복잡도 O(1) - deQueue : 큐에서 데이터를 꺼내는 작업을 말한다.(front에서 꺼냄) - 시간복잡도 O(n), 중간의 데이터가 수정될 경우 모든 요소를 한 칸씩 앞으로 옮기는 작업을 하게 되기 때문에 시간 복잡도가 상대적으로 높다. **링 버퍼 - deQueue의 시간 복잡도를 줄이기 위해서 배열 요소를 앞쪽으로 옮기지 않고 배열의 처음이 끝과 연결되었다고 보는 자료 구조. 시간 복잡도는 O(1)이다. 이렇게 배열의 처음과 끝을 연결해서 데이터가 수정되어도 해당..