2022/자료구조 + 알고리즘

2022.01.14 - [2022/자료구조 + 알고리즘] - [자료구조] 이진 트리 참고하면 좋다!!! [자료구조] 이진 트리 이진 트리 : 모든 노드가 최대로 두 개의 자식 노드를 갖는 순서화된 트리 각 노드가 최대 2개의 자식을 갖는다. 각 노드가 자식을 왼쪽 자식 또는 오른쪽 자식으로 분류한다. 왼쪽 자식이 오른쪽 guiyum.tistory.com 이진 탐색트리 이진 트리 T의 각 내부 노드 v가 엔트리 (k, x)를 저장하는 이진 트리이다. v의 왼쪽 서브트리에 있는 노드들에 저장된 키들은 k보다 작거나 같다. v의 오른쪽 서브트리에 있는 노드들에 저장된 키들은 k보다 크거나 같다. T의 노드들에 저장된 키들은 일련의 내부 노드들에서 비교를 함으로써 탐색을 수행하는 방법을 제공하고 있다. 현재 노..

정렬된 맵 맵의 엔트리들을 어떤 전체 순서(total order)에 따라 정렬하고, 이렇게 정렬된 순서에 따라 키와 값을 검색하는 정렬된 맵을 사용할 필요가 있다. firstEntry(k): 가장 작은 키값을 가진 엔트리에 대한 반복자를 반환. 맵이 비었다면 end를 반환 lastEntry(k): 가장 큰 키값을 가진 엔트리에 대한 반복자를 반환. 맵이 비었다면 end 반환 ceilingEntry(k): k보다 크거나 같은 키값 중 가장 작은 키값을 가진 엔트리에 대한 반복자를 반환. 그런 엔트리가 없다면 end 반환 floorEntry(k): k보다 작거나 같은 키값 중 가장 큰 키값을 가진 엔트리에 대한 반복자 반환. 그러한 엔트리 없다면 end 반환 lowerEntry(k): k보다 작은 키값 중 ..

맵 맵은 원소를 저장하고 키를 이용하여 빠르게 찾을 수 있도록 한다. 엔트리라 불리는 키-값 쌍(k, v)을 저장한다. 맵 ADT에서 각 키는 유일하여 키와 값의 연관은 매핑을 정의한다. 가장 높은 수준의 일반화를 위해, 맵에 저장된 키와 값은 어떠한 객체타입도 가능하다. 키는 일종의 위치 역할을 하는 객체이다. 맵은 객체에 연관된 키가 그 자료구조에서 객체의 위치를 결정하기 때문에 연관된 저장소(associative stores) 또는 연관된 컨테이너(associative container)라고 불리기도 한다. 엔트리와 구성 패턴 엔트리는 구성 패턴(Composition Pattern)이라 불리는 객체지향 설계 패턴의 한 예로 다른 객체들로 구성된 단일 객체를 정의한다. 쌍은 가장 간단한 구성이다. 두..

힙-정렬 2022.01.18 - [2022/자료구조 + 알고리즘] - [자료구조] 힙 [자료구조] 힙 https://guiyum.tistory.com/130 [자료구조] 우선순위 큐 우선순위 큐 : 임의의 순서로 입력된 우선순위된 원소들을 저장하고 우선순위에 따라 출력하는 추상 데이터 타입 저장된 원소들 중 가장 우선순 guiyum.tistory.com 앞에서 설명한 바와 같이, 힙으로 우선순위 큐를 구현할 경우 모든 우선순위 큐 ADT의 함수들을 로그 시간 또는 그보다 효율적으로 구현할 수 있는 장점이 있다. 이번에는 우선순위 큐 P를 이용하여 리스트 L을 정렬하는 PriorityQueueSort 정렬 기법을 다시 보자!! 첫 번째 단계에서, i번째의 (1 ≤ i ≤ n) insert 연산은 각각 O(..

https://guiyum.tistory.com/130 [자료구조] 우선순위 큐 우선순위 큐 : 임의의 순서로 입력된 우선순위된 원소들을 저장하고 우선순위에 따라 출력하는 추상 데이터 타입 저장된 원소들 중 가장 우선순위가 높은 원소가 삭제됨 키 응용프로그램에서는 guiyum.tistory.com ▲우선순위 큐는 전 포스팅 힙(Heap) : 키들을 내부 노드들에 저장하는 이진 트리 T. 다음과 같은 특성을 가진다. 힙-순서 특성(Heap-Order Property): 힙 T에서 루트를 제외한 모든 노드 v에 대하여 v에 저장된 키는 v의 부모에 저장된 키보다 크거나 같다. => 최소값을 갖는 키는 항상 T의 루트에 저장된다. 완전(complete) 이진 트리 특성: 힙은 완전(complete)해야 한다...

우선순위 큐 : 임의의 순서로 입력된 우선순위된 원소들을 저장하고 우선순위에 따라 출력하는 추상 데이터 타입 저장된 원소들 중 가장 우선순위가 높은 원소가 삭제됨 키 응용프로그램에서는 종종 "키"라고 불리는 매개변수 또는 특성에 따라 객체들을 비교하고 순위를 매기는 것이 필요하다. 여기서 키는 집합에 포함된 각 객체에 주어진 값이다. 공식적으로, 우리는 키를 원소들에게 속성으로 주어진 객체라고 정의하며 그 원소를 식별하거나 순위를 정하거나 측정하는 데 사용된다. 비교자(Comparator) 우선순위 큐의 구현에 있어 중요한 점은 키를 비교하기 위한 관계를 정의하는 방법이다. 일반적인 접근방법은 우선순위 큐를 템플릿화된 클래스로 가정하는 것이다. 우리는 우선순위 큐의 원소로 사용될 수 있는 각 클래스가 타..

이진 트리 : 모든 노드가 최대로 두 개의 자식 노드를 갖는 순서화된 트리 각 노드가 최대 2개의 자식을 갖는다. 각 노드가 자식을 왼쪽 자식 또는 오른쪽 자식으로 분류한다. 왼쪽 자식이 오른쪽 자식보다 먼저 오도록 순서화되었다. 각 노드가 0개 또는 2개의 자식을 가지면 이진 트리가 프로퍼(proper)하다고 한다. 경우에 따라 이러한 트리를 풀(full) 이진 트리라고 한다. => 프로퍼 이진 트리에서는 모든 내부 노드는 정확히 두 개의 자식을 가진다!! 산술식 트리(arithmetic expression tree) 외부 노드: 변수 or 상수 내부 노드: +, -, x, / +, -, x, / 의 연산자는 실질적으로 두 개의 피연산자를 가짐 => 산술식은 프로퍼(proper) 이진 트리! 물론 -x..

깊이와 높이 p를 트리 T의 노드라고 하자!! p의 깊이(depth)는 p의 조상의 수이다. 예를 들어 이 트리의 2의 깊이는 2다!!! (조상 7, 2) 노드 p의 깊이를 다음과 같이 재귀적으로 정의할 수 있다. 만약 p가 루트이면, p의 깊이는 0이다. 그렇지 않으면, p의 깊이는 p의 부모의 깊이에 1을 더한 것과 같다. Algorithm depth(T, p): if p.isRoot() then return 0 else return 1 + depth(T, p.parent()) 수도 코드로 나타내면 이렇게!!! C++ 코드로 작성해보자!! int depth(const Tree& T, const Position& p) { if (p.isRoot()) return 0; else return 1 + dep..

자료구조(data structure): 자료를 구성하고 접근하는 체계적인 방법 알고리즘: 유한한 시간내에 어떤 일을 수행하는 단계적인 절차 보통 최악의 경우에 관한 실행시간을 특정 지음 최악의 경우에서 잘 수행되는 알고리즘에 대한 성공의 기준을 만드는 것은 모든 입력에서 잘 수행된다는 것을 필수적으로 요구한다!! Big-Oh 표기법 위 식을 만족하는 실수 상수 c>0와 정수 상수 n0≥1이 존재한다면 f(n)을 O(g(n))이라고 한다!! 그니까 어떤 지점 n0에서부터는 아무리 나빠도 cg(n)보다 좋다는 상한을 의미한다!!! (=최악의 경우) Big-Oh 표기법은 함수 증가에 영향을 미치는 주요 구성요소에만 초점을 맞추고 낮은 차수와 상수 인자는 무시할 수 있도록 허용한다. 이렇게 제일 큰 차수만 남겨..

링크드 리스트 : 어떤 노드를 저장할 때 그 다음 순서의 자료가 있는 위치를 포함시키는 상식으로 자료를 저장 단일 링크드 리스트(singly linked list) : 각각의 노드가 값과 다음 노드를 가리키는 포인터 next를 저장한다. next 참조를 통해 한 노드에서 다른 노드로 이동하는 것을 링크 연결하기(link hopping) 또는 포인터 연결하기(pointer hopping)라고 한다. 링크드 리스트의 제일 처음과 마지막 노드를 각각 그 리스트의 head와 tail이라 부른다. null값을 참조하는 next 값을 가진 node가 tail이다. 배열과 마찬가지로 단일 링크드 리스트도 특정 순서로 원소들을 저장하며, 이 순서는 next 링크의 연결로써 결정된다. 배열과 다른 점은 단일 링크드 리스..