PS/Data Structure5 [자료구조] 트리(Tree) 트리 트리란? 회사의 조직도, 가계도와 같이 나무처럼 뻗어나가는 모양의 사이클이 없는 그래프다. 노드 간선 루트 노드: 트리의 맨 꼭대기 부모 노드/자식 노드 리프 노드: 자식이 없는 노드 차수와 깊이 그리고 높이 차수: 특정 노드의 자식 수 깊이: 특정노드로부터 루트노드와 떨어져있는 정도 높이: max깊이 + 1 이진트리 트리의 자식을 2개로 한정하면, 이진트리 배열로 나타내기 좋다. 부모는 i, 왼쪽 자식은 i2, 오른쪽 자식은 i2+1 만약 모든 자식이 꽉 차있지 않다면 배열도 같이 비워줘야한다. 이진트리는 한번 알면 여러모로 편하다.. 자식이 2개로 제한되어 있기 때문에 구현도 좋다… 그러니 확실하게 알아둘 것! 트리의 순회 트리를 탐색하는 순회 방법은 3 가지가 있다. 전위 순회(왼>뿌>오) 중.. 2023. 1. 24. [자료구조] Deque와 파이썬의 collections ✔ 덱(deque)이란? double ended: 양 끝이 닮은, 앞뒤가 없는..이라는 뜻이다. 따라서 데큐는 양 끝 모두가 출입구가 되므로, 양방향으로 push&pop이 가능하다. (stack은 한쪽으로만 입출력!) 데큐는 큐의 일종으로, FIFO(First In First Out: 먼저 넣은 데이터가 먼저 나오는) 구조이다. 선착순을 떠올리면 직관적으로 이해할 수 있다. 📝 덱(deque)의 성질 덱은 가장 앞부분을 가리키는 front와 가장 뒷부분을 가리키는 back이 구성되어있다. 따라서 push_front push_back, pop_front pop_back 을 모두 활용할 수 있다!! 데큐를 쓰는 이유는 https://wiki.python.org/moin/TimeComplexity 를 읽어보면.. 2022. 12. 24. [자료구조] 힙(heap)/ 최대힙(Max-Heap) / 최소힙(Min-Heap) / 자료구조 힙 / 힙정렬 ✔ 힙(heap) 힙이란? 1등을 찾기 위한 자료구조이다. 최소힙, 최대힙으로 최댓값과 최솟값을 빠르게 찾아낼 수 있다. 완전 이진 트리의 일종으로, 루트 노드에 있는 원소(1등 원소)를 뽑으면, 2등이 자동으로 1등이 된다. 📝 힙의 성질 완전 이진트리(모든 노드의 자식이 두개)의 일종으로, 리프 노드(제일 마지막 노드)를 제외한 자식 노드는 반드시 2개이다. 완전 이진트리는 중복을 허용하지 않지만, 자료구조 힙은 중복을 허용한다. 부모는 자식 보다 반드시 크거나(Max-Heap), 부모는 자식 보다 반드시 작다.(Min-Heap) 트리를 배열로 표현할 수 있다. 위의 설명에 따르면, 결론적으로 자료구조 힙은 루트 원소(제일 큰 값 or 제일 작은 값)를 제거하면서 원하는 값(제일 큰 값 or 제일 작.. 2022. 12. 24. [자료구조] 스택 / stack / 스택구현 / push / pop / empty / size / top https://www.acmicpc.net/problem/10828을 풀면서 복기했던 스택에 대해 정리한다. 1. 스택(stack)이란? 컴퓨터 과학에서 요소들의 집합으로 기능하는 abstract data type. (출처: 위키백과) 쉽게 말해서 배열처럼 요소들의 집합인 자료구조이다. 스택의 강력한 특징은 LIFO(Last In - First Out)이다. 조금 더 직관적인 이해를 위해 그림을 그려봤다. 위 그림과 같이 먼저 들어간 a보다 c가 먼저 나오는 구조다. 그리고 데이터는 한쪽에서만 입출력이 가능하다. 처음 스택을 접하면 받아들이기가 힘들 수도 있다. 일반적인 상식과는 어긋나기 때문이다🤣 (먼저 들어간 사람이 먼저 나오는 게 상식적이니까..?) 이렇게 생각하다 보니까 갑자기 스택의 예시로는 뭐.. 2022. 12. 22. [자료구조] 두 개의 Rectangle 위치 비교(feat. C++) 자료구조 수업 첫번째 과제는 1. Rectangle.cpp와 Rectangle.h, main.cpp의 관계를 파악하고 Rectangle 객체 생성 ~ 파괴 관계를 아는 것. 2. 두 개의 Rectangle 객체 위치 비교. 첫과제의 1번을 해결하기 위해서 1. 클래스와 객체 2. 생성자&파괴자 3. 연산자 오버로딩 의 개념에 대한 이해가 필요했다. (이에 대해서는 따로 C++ 카테고리에서 자세히 설명할 것이다.) 코드 해석을 하기 위해 가장 중요한 것은 "생성자와 소멸자가 언제 어떻게 생성되는지 이해하고, 그를 바탕으로 프로그램 결과물을 파악" 하는 것이라고 느꼈다. 다음은 교수님께서 작성하신 main.cpp 내용이다. int main() { Rectangle r1(1, 1, 3, 4); std::cout 2022. 5. 20. 이전 1 다음
