본문 바로가기

Data Structure

 (9)
[자료구조] Deque Deque Deque(덱 .. ?)은 스택과 큐를 합친 자료구조이다. Stack : 한쪽에서만 삽입, 삭제가 가능하다. Queue : 한쪽에서는 삽입만, 한쪽에서는 삭제만 가능하다. Deque : 양쪽에서 삽입/삭제가 가능하다. Deque (Double Ended Queue) : 양쪽 끝에서 삽입과 삭제가 가능한 자료구조 언제 사용하는데? 그 특징에서 알 수 있는 것처럼 특정 배열에 데이터를 앞/뒤 모두 넣었다 뺐다 할 때 효율적으로 사용할 수 있다. 실제로 양쪽에 삽입/삭제가 필요한 경우는 그렇지 많지 않아서 보통 스케줄링 할 때 많이 사용한다고 한다. 우리같은 경우는 .. 알고리즘을 풀 때 많이 사용하게 될텐데 .. 만약 !! 알고리즘을 풀 때 반복문 중첩이 없는데 시간 초과가 뜬다면 ?! Deque..
[자료구조] 이진 탐색 트리 (구현) #노드 클래스 생성 class Node { var data: T var left: Node? var right: Node? init(data: T) { self.data = data } } 이진 탐색 트리의 경우 몇가지 조건이 있다. ✅ 데이터를 비교하면서 탐색을 하기 때문에 비교 가능한 데이터만 저장할 수 있도록 Comparable 프로토콜을 채택한 제너릭으로 선언했다. ✅ 데이터는 항상 존재해야 하므로 Non-Optional Type이다.✅ (데이터는 옵셔널이 아니지만) 트리의 왼쪽, 오른쪽 자식 노드는 있을 수도 있고 없을 수도 있기 때문에 Optional Type이다. #이진 탐색 트리 클래스 생성 위에서 생성한 노드 클래스를 바탕으로 이진 탐색 트리를 구현해보자. 먼저, 최상위 노드인 root ..
[자료구조] 트리, 이진트리, 이진탐색트리 (개념) Tree 트리는 데이터를 계층적으로 표현하기 위한 자료 구조이다. (tmi : 트리의 모양이 뒤집어 놓은 나무와 같다고 해서 붙여진 이름이라고 한다.) 노드와 간선을 이용해서 사이클을 이루지 않도록 구성한 데이터 구조이다. #트리의 특징 비선형 자료구조, 무방향 비순환 그래프, 계층형 자료구조 #노드 노드란? 내 데이터 + 다음 데이터의 주소값을 갖고 있는 형태이다. 연결 리스트에서 노드의 형태는 아래와 같다. 단방향일 경우에는 next만 갖고 있고, 양방향일 경우에는 prev, next 모두 갖고 있다. #트리의 형태 트리의 형태도 비슷하다. 트리 역시 내 데이터 + 다음 데이터의 주소값을 갖는 형태이지만 위의 연결 리스트와 비교했을 때 연결 고리의 모양이 조금 다르다. 위와 같이 노드들이 계층을 갖고..
[자료구조] 그래프 알고리즘 문제를 풀면서 한번씩은 접하게 되는 개념이 BFS(너비 우선 탐색) / DFS(깊이 우선탐색)이다. 이 방식들은 그래프를 순회하는 방식을 의미한다. 그래프 그래프란, 노드(정점)와 간선으로 이루어진 자료구조이다. 정확하게 설명하자면 정점간의 관계를 표현하는 조직도라고 볼 수 있다. *트리와 그래프 노드? 간선? 은 트리 구조에서도 나오는 개념이다. 트리는 그래프의 일종이라고 할 수 있다. ✔️ 트리와 다르게 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있으며 ✔️ 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다. 그래프는 네트워크 모델 즉 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다. 실생활의 다양한 예를 그래프로 표현할 수 있다. 대표적으로 지하철 노선도, 도..
[자료구조] Queue 이전에 올린 스택의 경우 Swift에서는 배열을 스택처럼 사용할 수 있었다. (append(), removeLast() 등의 메서드를 사용해서) 그러나 큐의 경우 Swift에서 따로 지원하지 않기 때문에 만약 알고리즘 문제를 풀면서 큐를 사용할 일이 있다면 따로 만들어서 사용해야 한다. 큐는 선입선출 FIFO 구조이다. enqueue : 맨 뒤에 원소 추가 dequeue : 맨 앞에 원소 삭제 peek : 첫 번째 위치한 데이터 읽기 clear : 큐 재설정해 빈 상태되게 하기 count : 큐에 있는 요소의 수 반환 isEmpty isFull 구현 구조체와 배열로 아래와 같이 구현할 수 있다. struct Queue { private var queue: [T] = [] public var count: ..
[자료구조] Stack Swift에서 Stack을 구현하고 싶다면 배열을 사용해서 구현할 수 있다. Stack이란? c b a 위와 같은 스택 구조가 있다면 a -> b -> c 순으로 스택에 들어갔을 것이고 나올 때는 c -> b -> a 순서로 나오게 된다. 즉, 스택은 FILO 구조이다. 구조의 마지막에 추가/삭제 되기 때문에 시간 복잡도는 O(1)를 갖게 되며 그러므로 오버헤드는 발생하지 않는다. Stack 구현 아래와 같이 구조체와 배열을 사용해서 스택을 구현할 수 있다. struct Stack { private var stack: [T] = [] public var count: Int { return stack.count } public var isEmpty: Bool { return stack.isEmpty } p..
[자료구조] 연결 리스트 (양방향) 단방향 연결 리스트의 경우 아래와 같이 원하는 데이터를 찾고 싶으면 head부터 순회해야 하므로 만약 찾고자 하는 데이터가 마지막에 있다면 모든 연결 리스트를 순회해야 하는 단점이 있다. (마지막 노드가 무엇인지 모르기 때문에) 이를 보완한 것이 양방향 리스트이다. 양방향 연결 리스트 가장 첫 노드를 가리키는 head와 가장 마지막 노드를 가리키는 tail을 두고 하나의 노드에 대해서 이전 노드와 다음 노드를 모두 연결해서 양방향으로 탐색이 가능한 것이 양방향 연결 리스트이다. 그러므로 위의 단방향의 경우 마지막 노드와 가까운 데이터를 찾는 경우 head부터 하나씩 순회해야 하는 단점이 있었지만, 양방향의 경우 찾고자하는 데이터가 연결 리스트의 마지막 노드와 가깝다면 tail을 이용해서 찾으면 되고 찾고..
[자료구조] 연결 리스트 (단방향) 배열 VS 연결 리스트 리스트에 대해 본격적으로 들어가기 전에 배열과의 차이점에 대해서 알아보자. 연결 리스트 역시 이전에 포스팅 했던 배열과 마찬가지로 데이터를 표현하는 자료구조 중 하나이다. *배열과 연결 리스트는 서로의 장단점을 보완하고 있다. 배열 배열은 인덱스를 이용해서 하나의 메모리 공간 안에 데이터들이 나란히 저장되어 있다. 그래서 인덱스를 통해 데이터에 접근할 수 있고 인덱스만 알고 있다면 값에 대한 접근이 매우 빠르다. 그러나, 처음이나 마지막 인덱스가 아닌 요소를 추가/삭제한다면 element(index+value)를 재배치하는 작업 때문에 오버 헤드가 발생할 수 있다는 단점이 있다. 연결 리스트 연결 리스트는 배열의 단점을 보완한 것이다. 따라서 배열과 같이 순차적으로 데이터를 보관하..

티스토리툴바