자료구조 (4) 썸네일형 리스트형 [자료구조] Heap에 대해 알아보고 구현해보기 (Swift) Heap이란? Heap은 트리를 사용하고, 트리 중 에서도 완전이진트리를 기본으로 한 자료구조입니다. 주로 최솟값과 최댓값을 빠르게 찾기 위해서 사용하는데, 루트노드를 최댓값으로 사용하면 최대힙이되고, 최소값으로 사용하면 최소힙이 됩니다. 시간 복잡도 삽입 : $O(log_n)$ 삭제 : $O(log_n)$ 구현 array를 사용하여 구현하고, 값을 비교하기 위해 Comparable 프로토콜을 채택한 자료형에 대해서만 요소로 사용할 수 있도록 구현하였습니다. 삽입 완전 이진 트리의 마지막 요소에 삽입 (append 사용) 삽입된 요소를 부모노드와 비교 최대힙이라면, 부모노드보다 더 크다면 swap 최소힙이라면, 부모노드보다 더 작다면 swap 루트노드가 될 때 까지 반복 삭제 힙의 루트 노드와 마지막 노.. [자료구조] Deque에 대해 알아보고 구현해보기 (Swift) Deque란? Deque 자료구조는 Queue의 특성과 Stack의 특성을 모두 갖는 자료구조 입니다. 왼쪽, 오른쪽 방향으로 삽입 삭제가 가능합니다. 왼쪽으로 삽입 오른쪽에서 삭제, 오른쪽으로 삽입 왼쪽에서 삭제 한다면 Queue 자료구조에 특성일 것이고 왼쪽으로 삽입 왼쪽에서 삭제, 오른쪽으로 삽입 오른쪽에서 삭제 한다면 Stack 자료구조의 특성일 것입니다. 시간 복잡도 삽입 : $O(1)$ 삭제 : $O(1)$ 검색 : $O(n)$ 구현 Deque을 어떻게 구현할 수 있을까요? 연결리스트를 사용하지 않고, Array 2개를 사용해서 구현해보았습니다. Queue를 구현할 때, index를 사용해서 구현한 것 처럼 요소를 가리킬 2개의 index를 두었습니다. 왼쪽이나 오른쪽으로 삽입하는 연산은 어떻.. [자료구조] Queue에 대해 알아보고 구현해보기 (Swift) Queue란? Queue 자료구조는 선입선출(First In First Out)FIFO의 특성을 갖는 자료구조 입니다. 즉, 먼저 들어온 것이 가장 먼저 나가는 구조입니다. 맛집에 먼저 줄을 섰던 사람이 먼저 들어가는 것과 동일합니다. 예를 들어 1, 2, 3이란 원소가 Queue에 들어온다면? Queue에 요소들이 이러한 식으로 들어와져 있을 것입니다. pop을 하게 된다면? 1이 가장 먼저 들어왔기 때문에 1이 먼저 나가겠죠? 시간 복잡도 삽입 : $O(1)$ 삭제 : $O(1)$ 검색 : $O(n)$ 구현 Queue를 어떻게 구현할 수 있을까요? Stack을 구현했던 것과 동일하게 Array을 사용해서 구현하려고 해요. 삽입 연산은 Swift의 Array의 append 메서드를 사용할 수 있겠죠? .. [자료구조] Stack에 대해 알아보고 구현해보기 (Swift) Stack이란? Stack 자료구조는 후입선출(Last In First Out)LIFO 의 특성을 갖는 자료구조 입니다. 즉, 나중에 들어온 것이 가장 먼저 나가는 구조입니다. 예를 들어 1, 2, 3이란 원소가 Stack에 들어왔다면 스택에 요소들이 이러한 식으로 들어와져 있을 것입니다. pop을 하게 된다면? element 3이 삭제될 것입니다. 시간 복잡도 삽입 : $O(1)$ 삭제 : $O(1)$ 검색 : $O(n)$ 스택의 활용 실행 취소 (undo) 웹 브라우저에서의 뒤로가기 재귀함수 구현 스택을 어떻게 구현할 수 있을까요? 연결리스트를 사용하여 구현할 수도 있지만 Array를 사용해서 구현해보겠습니다. 삽입 연산은 Swift의 Array의 append 메서드를 사용할 수 있습니다. 단순히 A.. 이전 1 다음
