목록CS/자료구조 (6)
강신규

그래프의 개념 그래프(Graph)는 연결이 되어있는 원소(Node)간의 관계를 표현한 자료구조입니다. 앞선 트리와의 가장 큰 차이점은 사이클이 존재가능하다는 점이고 그래프를 연결할 객체를 나타내는 Node(Vertex)와 그 Node를 연결하는 간선(Edge)의 집합으로 구성됩니다. 그래프는 방향이 존재하는 방향 그래프 , 방향이 없는 무방향 그래프 , 간선에 비용이나 가중치가 들어간 가중치 그래프 등으로 구성되어있습니다. 그래프 구현 1.인접행렬 구현 map[i][j] = 1 -> i 에서 j로 가는 간선이 존재한다는 뜻입니다. map[i][j] = 0 -> i 에서 j로 가는 간선이 없다는 뜻입니다. ex) map[1][2] = 1 map[2][1] = 1 map[1][3] = 1 map[3][1]..

트리 자료구조의 개념 트리 자료구조란 위의 사진처럼 노드(Node)들이 나무 가지처럼 연결된 계층적 자료구조입니다. 트리는 노드들과 노드들을 연결하는 간선(edge)들로 구성되어 있습니다. 루트 노드는 0개 이상의 자식 노드를 가지고 있으며 그 자식 노드 또한 0개 이상의 자식노드를 갖고있으며 이것이 반복된 것이 트리 자료구조 입니다. 트리는 사이클이 존재할 수 없으며 사이클이 존재하는 그래프와 다르다는 것이 큰 특징입니다. 트리 구현 class TreeNode { var value: T var children: [TreeNode] = [] init(value: T) { self.value = value } func addChild(_ child: TreeNode) { children.append(chi..
Dictionary(딕셔너리)란 Key , Value 가 함께 저장되는 자료구조입니다. Key 값은 중복되면 안되고 value는 상관없습니다. 딕셔너리 생성방법 var dic : [String : Int] = [:] // 타입을 작성해야합니다 var dic1 : [String : Int] = ["testKeyOne" : 150 , "testKeyTwo" : 100] var dic2 = [String : Int]() var dic3 = Dictionary() 딕셔너리 값 접근 var dic : [String:Int] = ["age" : 10 , "height" : 100] var height = dic["height"] // Optional(100) var age = dic["age"] // Optiona..

배열(Array) index를 이용하여 한 메모리 공간 안에 데이터들이 "나란히" 저장되어 있음 배열의 장점은 index만 알면 값에 대한 접근이 매우 빠른 것이 배열의장점 하지만 마지막 index 가 아닌 배열요소를 삭제하거나 삽입할 경우에는 배열 재배치하는 작업 때문에 오버헤드가 발생하는 단점이 존재한다 연결 리스트(LinkedList) 배열의 단점을 보완하기 위해 데이터들을 배열과 같이 보관 하는 것이 아닌 각각 떨어진 공간에 존재하는 데이터를 연결해 놓은것 배열처럼 중간에 element 삽입이나 삭제 시 재배치에 발생하는 오버헤드가 발생하지 않는다 하지만 데이터에 접근하려면 첫 번째 데이터부터 원하는 데이터까지 순차적으로 찾아가야 해서 접근 속도가 느리다 탐색(search) - O(N) 특정한 노..

큐의 개념 큐는 기존 스택과는 다르게 먼저 들어간 자료가 먼저 나오는 구조입니다(First in First Out). 한쪽이 뚫려 있는 구조로 한쪽으로는 데이터의 삽입(enQueue) 다른 한쪽은 데이터 추출(deQueue)이 진행됩니다. 큐는 front(머리) rear(꼬리) 가 존재하는데 데이터 삽입시 rear 다음에 위치(rear+1) 데이터 추출시에 먼저 들어온 데이터가 나가야 하기때문에 머리 위치에서 나갑니다. 큐의 구현(Array) struct Queue { private var queue: [T] = [] public var count: Int { return queue.count } public var isEmpty: Bool { return queue.isEmpty } public mut..

스택(Stack)이란 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LAST IN FIRST OUT 형식의 자료구조 입니다. LAST IN FIRST OUT 이란 가장 최근에 들어온 데이터가 가장 먼저 나간다는 의미입니다. 이는 먼저 들어온 데이터가 먼저 나가는 '큐' 와 가장 큰 차이점을 가집니다. 구현 스택은 마지막으로 들어온것이 먼저 나가는 구조입니다. 가장 최근에 스택에 추가한 항목이 가장 먼저 제거가 됩니다. 본인이 사용하는 언어로 Array 를 통해 제일 마지막으로 들어온 데이터를 출력해주는 형태로 구현이 가능합니다 이때 생성, 삽입, 삭제 시간 복잡도를 계산하면서 구현하면은 더욱더 좋습니다. 시간복잡도 데이터 삽입시 시간복잡도 : O(1) 데이터 삭제시 시간복잡도 : O(1) 스택의 구현 stru..