Joon's Blog Joon's Blog

이진탐색트리(BST)를 기반으로 구성된 자료구조입니다. BST의 설명은 여기에 있습니다. 따라서 BST의 설명은 본 게시물에서는 하지 않습니다. 개념설명 : 우선 이진탐색트리를 잠깐 봅시다. 이진탐색트리는 Search, Insert, Delete 가 가능한 이진트리였습니다. 이때, 평균 시간복잡도는 O(log n) 이였죠. 하ㄴ지만 이진트리가 극단적으로 편향됬을때시간복잡도는 O(N) 이 됩니다. 이건 이진트리의 깊이(h) 많큼 탐색을 한다는 의미입니다. 이러한 문제들을 해결하기 위해 나온 것이 바로 레드-블랙트리(Red-BlackTree) 입니다. 다른 말로 Balanced Binary Search Tree 라고도 합니다. 이유는 이진탐색트리의 깊이를 항상 log N 으로 유지시켜주기 때문입니다. 따라서..

이진탐색트리(BST)는 링크드리스트를 기반으로 한 탐색 알고리즘입니다.그래서 링크드리스트를 모르시면 꼭! 자료구조를 통해 공부를 하시고 읽으시길 바랍니다. 본 게시물이선 BST에 대해서만 설명합니다. 이해 순서 포인터를 정확히 이해한다. 링크드리스트를 이해한다. 완전 이진트리를 이해한다. 이진 탐색트리를 이해한다. 이진탐색트리(BST) 란 ? : 방탄소년단(BST) ? 죄송합니다. 이진탐색트리는 이진탐색(Binary Search)와 연결리스트(Linked List)를 결합한 자료구조의 일종입니다. 이진탐색은 탐색에 필요한 시간복잡도가 O(logN)으로 빠르지만 자료 입력과 삭제가 불가능합니다. 연결리스트의 경우는 입력과 삭제의 시간복잡도가 O(1)로 빠르지만 탐색하는 시간복잡도는 O(n)으로 매우 비효율..

C++ 문법 Struct 개념부분은 내용을 조금씩 추가 할 예정입니다. 개념 구조체는 관련있는 변수들을 모아서 하나의 새로운 변수 타입을 만들어주는 기능이다. 쉽게말해 사용자 정의 변수타입이라고 할 수있다. 배열과 구조체의 공통점 1. 데이터 집합이다. 2. 연속된 메모리 블럭에 할당된다. - 따라서 structname 변수명 = {}; 와 같이 선언하면 구조체 안에 변수를 모두 0으로 초기화가 가능하다. 문법 sturct 구조체명 {}; 구조체명 변수명 구조체명.변수명 코드 : 클래스의 멤버변수 출력해보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 # include #define NAME_S..

C++ 문법 참조자형 개념부분은 내용을 조금씩 추가 할 예정입니다. 개념 참조자형은 마치 닉네임을 사용하는 것과 유사하다. 원래 한공간에 변수명은 하나만 입력을 하지만, 두가지의 변수명으로 사용 할 수있는 것이다. 주의해야할 점은 참조자와 참조하고자 하는 변수의 자료형을 일치시켜야 하는 것이다. 문법 자료형& 변수명 = 참조하고자 하는 변수명 코드 예시1) : 같은 자료형인 두개의 인수를 받는 경우 1 2 3 4 5 6 7 8 9 10 11 int main() { int Var1 = 5; int& Var2 = Var1; cout

C++ 문법 Nullptr 개념부분은 내용을 조금씩 추가 할 예정입니다. 개념: 요점만 말하자면 Nullptr 은 포인터를 초기화하는 키워드입니다.보통 일반변수를 선언할때 int Num=10; 이런식으로 원하는 값을 넣어 둡니다.하지만 값이 바로 정해지지 않는 경우 int Num= Null 이런식으로 초기화를 해두죠? 이건 바로 쓰레기값을 피하기 위해서 입니다. 컴퓨터는 Null 이 아닌 모든 값을 True 로 판단하기 때문입니다. 1int* Pnum = nullptr;cs 그래서 이런식으로 선언을 해주면 포인터 변수가 아무것도 가리키고 있지 않은 것을 의미합니다.

C++ 문법 Template 개념부분은 내용을 조금씩 추가 할 예정입니다. 문법 template or template 1 2 3 1 : 선언해주는 이름 2 : class, typename 두 가지의 경우가 있는데, 아무거나 사용해도 좋다. 하지만 class 의 경우 이미 정해진 이름이 있기 때문에 보통 typename 을 사용한다. 3 : 여기에는 편하게 사용할 문자를 사용하는데, 역시 보통 T 를 사용합니다. 코드 예시1) : 같은 자료형인 두개의 인수를 받는 경우 1 2 3 4 5 6 template T add(T a, T b) { return a + b; } cs 다시 return 하는 경우 당연히 함수도 T 로 선언해줘야 겠죠ㅎㅎ 코드 예시2) : 다른 자료형인 두개의 인수를 받는 경우 1 2 3..

알고리즘 힙정렬(Heap sort) 힙 정렬은 트리 구조를 이용하기 때문에 이해하는데 가장 오랜시간이 걸렸어요. 저는 자료구조를 배우지 않은 상태에서 알고리즘을 시작했거든요. 그래서 이번엔 저 처럼 자료구조를 배우지 않고 알고리즘을 먼저 시작한 사람들을 대상으로 설명할 예정입니다. 이해 순서 1. 트리의 구조를 이해한다. 2. 이진 트리를 이해한다. 3. 완전 이진 트리를 이해한다. 4. 최대힙과 최소힙을 이해한다. 5. 힙정렬을 이해한다. 주의 : 1 ~ 4 과정은 자료구조 게시판에 자세히 올릴 예정이므로 간단하게 설명하겠습니다. 트리 구조란 ? : 나무의 뿌리(root) , 줄기(trunk), 잎(leaf) 처럼 특정한 관계를 갖고 있는 자료들을 의미합니다. 그림을 보면 마치 뒤집어 놓은 나무처럼 보..

알고리즘 퀵정렬(Quick sort) 간단 요약 1. 임의의 값을 피벗(Pivot) 으로 정한다. 2. 피벗을 기준으로 하나씩 비교하여 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 정리한다. 3. 피벗을 기준으로 왼쪽 과 오른쪽의 배열을 비균등 분할을 한다. 4. 각각의 배열에서 순환 호출을 통해 더 이상 분할되지 않을 때 까지 반복 상세 설명 병합 정렬은 분할, 정복, 결합 세단계의 과정을 거쳐서 완성된다. 분할 : 피벗을 기준으로 비균등 분할 정복 : 각 배열의 크기가 더 이상 분할 할 수 없을 때 까지 순환 호출을 통해 분할을 반복한다. 결합 : 한회의 분할,정복이 끝날 때 마다 최소 하나이상의 피벗값이 생긴다. -> 각 회마다 결정되는 피벗값의 위치는 정렬이 완성되었을때의 위치와 같기 때문에 각..