선택 정렬 (Selection Sort) 첫 번째 데이터를 두 번째 데이터 ~ 마지막 데이터까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 데이터를 세 번째 데이터 ~ 마지막 데이터까지 차례대로 비교하여 가장 작은 값을 두 번째 위치에 놓는 과정을 반복해 정렬하는 과정을 말한다. 특징 장점 - 자료 이동 횟수가 미리 결정된다. 단점 - 안정성을 만족하지 않는다. - 같은 값을 같은 데이터가 있는 경우 상대적인 위치가 변경될 수도 있다. 시간 복잡도 비교 - 두 개의 for문이 실행됨 = O(n^2) - 외부 루프 : n-1번 - 내부 루프 : n-1, n-2, n-3,..., 2, 1번 교환 - 외부 루프의 실행 횟수만큼 작업 = O(1) ∴ O(n^2) 정렬 알고리즘 시간 복잡도..
이진 탐색 트리 (Binary Search Tree, BST) 이진 탐색 트리는 효율적인 탐색을 위해 만들어진 트리로, 다음과 같은 속성이 존재한다. 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다. (중복 X) 2. 부모의 키가 왼쪽 자식 노드의 키보다 크다. 3. 부모의 키가 오른쪽 자식 노드의 키보다 작다. 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다. 특징 기존 이진트리보다 탐색이 빠르다는 장점을 가지고 있다. 이진 탐색 트리의 탐색 연산은 트리의 높이가 h라면 O(h)의 시간 복잡도를 갖게 된다. 탐색 (Search) 이진 탐색 트리의 탐색 과정은 다음과 같다. 1. 루트 노드와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료한다. 2. 찾고자 하는 값이 루트 노드보다 작..
Spanning Tree Spanning Tree = 스패닝 트리 = 신장 트리 그래프 내의 모든 정점을 포함하는 트리로 그래프의 최소 연결 부분 그래프이다. 특징 DFS/BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. 모든 정점들이 연결되어 있어야 하고, 사이클이 포함되서는 안된다. 그래프에 있는 n개의 정점(v)을 정확히 n-1개의 간선(e)으로 연결한다. Minumum Spanning Tree (MST) Spanning Tree 중에서 간선들의 가중치 합이 최소인 트리를 MST라고 부른다. 각 간선의 가중치가 동일하지 않을 때, 단순히 가장 적은 간선을 사용한다고 해서 최소 비용을 얻는 것은 아니다. 특징 간선의 가중치의 합이 최소여야 ..
그래프를 탐색하는 방법에는 크게 2가지로 나눌 수 있는데, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다. 💡 그래프란 ? 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종. 그래프를 탐색한다는 것 = 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것 깊이 우선 탐색 (DFS, Depth-First Search) : 최대한 깊이 내려간 후, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동 깊이 우선 탐색의 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식. 예를 들어, 미로 찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더이상 갈 수 없게 되면 ..
💡 다익스트라(Dijkstra) 알고리즘이란? 그래프에서 '최소 비용', '최소 거리'를 구해야 하는 경우에 사용하는 알고리즘으로, 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최소 비용인 경로를 찾을 때 유용하게 사용된다. 다익스트라 알고리즘은 그래프의 어느 간선의 가중치라도 음수가 있으면 안된다는 특징이 있다. (가중치에 음수가 있을 시 벨만-포드 알고리즘 이용) 다익스트라 알고리즘을 구현하기 위해서는 다음 과정을 반복하면 된다. 1. 방문하지 않은 정점 중 가장 가중치가 작은 정점을 방문한다. 2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록된 값보다 작으면 그 거리를 갱신해준다. 예시를 통해 좀 더 자세하게 설명해보겠다. 다음과 같은 그래프가 있다고 하자. 시작 정점은 0번 정..
💡 비선형 자료 구조 (Non Linear Data Structure) 비선형 자료 구조란 하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 것을 의미한다. 자료들 간의 앞뒤 관계가 1:n, 또는 n:n의 관계를 말한다. 트리와 그래프가 대표적인 비선형 자료 구조이고, 계층적 구조(Hierarchical Relationship)를 나타내기에 적절하다. 🔎 트리(Tree)의 개념 트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사하다. 트리는 또한 트리 내에 다른 하위 트리가 존재하고, 그 하위 트리 안에는 또다른 하위 트리가 있는 재귀적 자료구조이기도 하다. 대표적인 트리 구조 예시는 ..
🔎 스택 (Stack) 📕 개념 선형 자료구조의 일종으로, 스택은 영어의 의미인 쌓아 올린다는 것을 의미합니다. 따라서 책처럼 위로 하나씩 차곡차곡 쌓아 올린 자료구조를 말합니다. 📒 특징 위의 그림처럼 같은 구조와 크기인 자료들을 정해진 방향으로만 쌓을 수 있고, top으로 정해진 곳을 통해서만 접근이 가능합니다. top은 가장 위에 있는 자료로, 가장 최근에 추가된 자료를 가리키고 있습니다. 또한 삭제할 때도, top을 통해서만 가능합니다. 스택에서 삽입하는 연산을 'push', 삭제하는 연산을 'pop'이라고 합니다. 따라서 스택은 나중에 들어간 원소가 먼저 나오고 (Last In First Out - LIFO), 먼저 들어간 원소는 가장 나오게 됩니다 (First In Last Out - FILO..
0. 선형 자료구조 (Linear Data Structure) 선형 자료구조란 하나의 자료 뒤에 하나의 자료가 존재하는 것을 의미합니다. 자료들 간의 앞뒤 관계가 1:1 선형 관계를 이루며, 배열과 리스트가 대표적인 예이고, 더 나아가 스택, 큐, 데크도 선형 자료구조에 해당됩니다. 해당 선형 자료구조는 연속된 자료구조와 연결된 자료구조 2가지로 나눌 수 있습니다. (Contiguous & Linked) ▪ 연속된 자료구조 (Contiguous) 연속된 자료 구조는 모든 원소를 단일 메모리 덩어리에 넣어 저장하는 것을 말합니다. 대표적인 연속된 자료 구조에는 배열(Array)이 있습니다. ▪ 연결된 자료구조 (Linked) 연결된 자료 구조는 노드(node)라고 하는 여러 개의 메모리 덩어리에 데이터를 ..
