🖥️ CS/자료구조

그래프(Graph)그래프는 노드와 간선의 집합으로 이루어진 자료구조이다.객체 간의 관계를 선으로 연결하여 표현하는 형태로, 각 정점 간에는 부모-자식 관계가 없다.너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 알고리즘에서 그래프를 순회하는 방식에서 사용한다. 그래프에서 사용하는 용어노드/정점(Vertex): 데이터가 저장되는 기본 객체간선(Edge): 정점을 연결하는 선인접 정점: 간선에 의해 직접 연결된 노드로, 한 정점에서 간선을 한 번에 갈 수 있다면 해당 정점들은 인접하다고 할 수 있다.단순 경로: 경로 중에서 반복되는 정점이 없는 경우 그래프 종류무방향 그래프모든 간선이 양방향인 그래프로, 방향이 없기 때문에 양쪽의 방향 모두 이동이 가능하다.방향 그래프간선들의 방향이 존재하는 그래프로, ..

힙(Heap) 완전 이진 트리를 기반으로 한 자료구조로, 최대값과 최소값을 빠르게 찾기 위해 만들어졌다. 반정렬 상태(느슨한 정렬 상태)를 유지한다. 즉, 모든 노드가 정렬되어 있는 건 아니라는 의미이다. 부모 노드와 자식 노드 간의 대소 관계를 이용하여 구성한다. 이진 탐색 트리와 달리 왼쪽, 오른쪽 자식 노드 간의 크기는 상관이 없다. 힙은 중복 값이 허용된다. 힙은 대량의 최대값이나 최소값을 빠르게 찾아야할 때 매우 유용하게 사용된다. 예를 들어, 우선순위 큐를 구현하거나, 다익스트라 알고리즘 등의 그래프 알고리즘에서 최단 경로를 찾을 때 사용된다. 완전 이진 트리(Complete Binary Tree) 왼쪽에서부터 채워져 있는 이진 트리 마지막 레벨을 제외하고는 모든 레벨이 채워져 있는 형태 마지..

이진 탐색 트리(Binary Search Tree) 이진 탐색과 연결 리스트를 결함한 자료구조의 일종으로, 탐색 작업을 효율적으로 할 수 있다. 이진 탐색 트리의 특징 이진 트리 구조로 이루어져 있다. 노드의 왼쪽 서브 트리에는 노드 값보다 작은 값이 포함되어 있고, 오른쪽 서브 트리에는 노드 값보다 큰 값이 포함되어 있다. 서브 트리 또한 이진 탐색 구조로 이루어져 있다. 모든 원소의 키는 유일한 키를 가진다. (중복 값이 없다.) 이진 탐색 트리를 사용하는 이유 트리를 사용하는 이유는 일반적으로 데이터를 빠르게 탐색하기 위해 사용한다. 선형 자료구조에서는 하나의 데이터 뒤에 오직 하나의 데이터만 존재한다. 때문에 특정 값을 탐색할 때 맨 끝까지 순차적으로 탐색하는 최악의 경우에 시간 복잡도가 O(n)..

트리 (Tree) 노드(Node)와 간선(Edge)로 이루어진 비선형 자료구조 트리의 용어 구분 설명 간선(Edge) 두 노드를 연결하는 선(링크) 노드(Node) 트리를 구성하는 기본 원소 루트 노드(Root) 트리의 최 상위 노드 리프 노드(Leaf) 자식 노드가 없는 노드 형제 노드(Sibling) 같은 부모를 갖는 노드 노드의 크기(Size) 자신을 포함한 모든 자식 노드의 개수 노드의 깊이(depth) 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 노드의 레벨(Level) 트리의 특정 깊이를 가지는 노드의 집합 노드의 차수(Degree) 각 노드의 자식 노드 개수 트리의 차수(Degree of Tree) 트리의 최대 차수 트리의 높이(Height) 루트 노드에서 가장 깊숙이 있는 노..

큐(Queue) 가장 먼저 들어온 것이 가장 먼저 나오는 FIFO의 특징을 가지는 자료구조 Queue는 뒤(rear)에서 데이터를 추가하고(enqueue), 앞(front)에서 데이터를 꺼낸다(dequeue). Front: Queue의 가장 첫 원소 Rear: Queue의 가장 끝 원소 removeFirst() Swift에서 배열의 첫 번째 원소를 제거하고 반환해주는 인스턴스 메소드가 존재한다. 하지만 나머지 배열의 원소의 자리를 이동시켜 빈 공간을 없애주기 때문에 시간복잡도가 O(n)이 된다. 연결 리스트로 Queue 구현하기 Node.swift class Node { let data: T var next: Node? init(data: T, next: Node? = nil) { self.data = ..

연결 리스트(Linked List) 연속적인 메모리 위치에 저장되지 않는 선형 자료구조 데이터 필드 + 다음의 노드에 대한 참조 를 포함하는 노드로 구성 연결 리스트를 사용하는 이유? 배열은 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당받아야 했다. 그렇기 때문에 새로운 요소 삽입의 비용이 많이 든다. (공간 만들기 + 기존 요소의 이동) 장점 동적인 크기를 가진다. 삽입/삭제가 용이하고 속도가 빠르다. 단점 Random Access가 불가하기 때문에 첫 번째 노드부터 순차적으로 액세스해야한다. 검색 속도가 느리다. 저장 공간의 효율이 높지 않다. 추가(add) 노드가 아무것도 없을 때 head = nil, tail = nil head 값을 확인 후 새로운 노드를 연결하고 tail도 동일하게 ..

스택(Stack) 가장 나중에 들어온 것이 가장 먼저 나오는 LIFO의 특징을 가지는 자료구조 삽입(Push) append() 시간복잡도: O(1) 삭제(Pop) removeLast() 또는 popLast() removeLast(): 배열이 비어있을 때 에러를 발생시킴 popLast(): 배열이 비어있을 때 nil을 반환시킴 시간복잡도: O(1) 스택의 마지막 요소 조회(Top) last() 시간복잡도: O(1) 구현 import Foundation struct Stack { var elements: [T] = [] var count : Int { return elements.count } var isEmpty : Bool { return elements.isEmpty } mutating func pop..