CS/자료구조 (6) 썸네일형 리스트형 자료구조 - Heap (2) 정렬 C언어로 쉽게 풀어쓴 자료구조를 읽으며 정리Heap sort힙 자료구조를 이용한 정렬 방법에는 두 가지가 존재한다.정렬 대상인 데이터들을 힙에 넣었다가 꺼내는 방법기존의 배열을 heapify를 거쳐 꺼내는 방법[정렬 대상인 데이터들을 힙에 넣었다가 꺼내는 방법]정렬해야 할 n개의 요소들로 힙을 초기화한다.그다음으로 한 번에 하나씩 요소를 힙에서 꺼내 배열의 뒤부터 저장하면 된다.시간 복잡도 : 요소의 개수가 n개이므로 전체적으로 O(nlog2n)의 시간이 걸린다.공간 복잡도 : 추가적인 O(n) 만큼의 공간이 필요하다// Heap 구현은 https://liam777.tistory.com/37 참고 extension Array where Element: Comparable { mutating func so.. 자료구조 - Heap (1) 기본 C언어로 쉽게 풀어쓴 자료구조를 읽으며 정리Priorty Queue우선순위를 가진 항목들을 저장하는 큐FIFO 순서가 아니라 우선순위가 높은 데이터가 먼저 나가게 됨응용분야시뮬레이션 시스템 (여기서의 우선순위는 대개 사건의 시각)운영 체제에서의 작업 스케줄링네트워크 트래픽 제어시간복잡도우선순위 큐는 배열로 구현할 수도 있고 연결 리스트로 구현할 수도 있지만시간 복잡도 면에서 가장 좋은 방법은 힙(Heap)으로 구현하는 것이다.표현 방법삽입삭제배열 (정렬)O(1)O(n)배열 (비정렬)O(n)O(1)연결 리스트 (정렬)O(1)O(n)연결 리스트 (비정렬)O(n)O(1)트리(heap) (부분정렬)O(logn)O(logn) Heap힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만.. 자료구조 - 트리 C언어로 쉽게 풀어쓴 자료구조를 읽으며 정리트리트리는 데이터의 계층적 관계를 표현하는 비선형적 자료구조이다.노드와 간선으로 이루어져 있으며 사이클을 허용하지 않는 그래프의 한 종류이다. 트리 - 구성요소노드 : 트리를 구성하는 각 요소간선 : 트리를 구성하기 위해 노드와 노드를 연결하는 선루트 노드 : 트리 구조에서 최상위 노드단말 노드, 리프 노드 (Terminal Node, Leaf Node) : 하위에 다른 노드가 연결되어 있지 않은 노드내부 노드, 비단말 노드(Internal Node) : 단말 노드를 제외한 모든 노드 이진 트리루트노드를 중심으로 최대 두 개의 서브 트리로 나눠진다.나눠진 두 서브 트리 모두 이진 트리이다.서브 트리는 공집합일 수도 있다. (공집합도 이진 트리이다.) 트리의 각 .. 자료구조 - 스택, 큐, 덱 C언어로 쉽게 풀어쓴 자료구조를 읽으며 정리스택정의후입선출(LIFO)구조로 모든 원소들의 삽입, 삭제가 리스트의 한쪽 끝에서만 수행되는 선형구조.구현struct Stack { private var _stack: [Element] = [] var count: Int { self._stack.count } var isEmpty: Bool { self._stack.isEmpty } mutating func push(_ element: Element) { self._stack.append(element) } mutating func pop() -> Element? { return self.isEmpty ? nil : self... 자료 구조 - 배열, 연결 리스트 C언어로 쉽게 풀어쓴 자료구조를 읽으며 정리배열인덱스와 요소 쌍의 집합메모리의 연속된 위치에 구현된다.크기 5인 배열 A가 있을 때 메모리 주소는 아래와 같다.ElementMemory AddressA[0]base * 1 * sizeof(type of Element)A[1]base * 2 * sizeof(type of Element)A[2]base * 3 * sizeof(type of Element)A[3]base * 4 * sizeof(type of Element)A[4]base * 5 * sizeof(type of Element) 함수의 매개 변수로서의 배열C언어에서 함수의 매개 변수로 배열을 전달하는 것은, 배열의 포인터가 전달되는 것과 같다.Swift 역시 배열 자체가 아닌 배열의 참조가 전달된다.. 자료 구조 - 순환 (Recursion) C언어로 쉽게 풀어쓴 자료구조를 읽으며 정리 순환(Recursion)이란 어떤 알고리즘 또는 함수가 자기 자신을 호출하여 문제를 해결하는 기법 순환의 강점 순환은 반복에 비해 알고리즘을 훨씬 명확하고 간결하게 나타낼 수 있다. 순환의 약점 함수 호출을 하게 되므로 반복에 비해 수행시간 / 기억 공간의 사용면에서 떨어질 수 있다. 순환의 원리 주어진 문제를 더 작은 동일한 문제로 분해하여 해결하는 divide and conquer 기법 1) 정수의 팩토리얼// 순환 호출로 구현func factorial(n: Int) -> Int { if n // 반복문으로 구현func factorial(n: Int) -> Int { var result = 1 var n = n while n != 1 { .. 이전 1 다음
