반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 18: 트리 동적 계획법 (Tree DP) 트리 동적 계획법 (Tree DP)트리 동적 계획법(Tree DP)은 트리 구조를 가진 문제를 해결하기 위한 효율적인 방법입니다. 이는 주로 트리의 정점이나 간선을 따라 상태를 정의하고, 하위 트리에서의 정보를 이용하여 전체 문제를 해결하는 기법입니다.문제 예시: 트리의 최대 독립 집합 (Maximum Independent Set of a Tree)주어진 트리에서 서로 인접하지 않은 정점의 최대 집합을 찾는 문제입니다. 이는 트리 DP를 사용하여 효율적으로 해결할 수 있습니다.문제 정의주어진 트리의 정점 수 (n)트리의 간선 정보최대 독립 집합의 크기 계산트리 DP 구현다음은 C++로 트리의 최대 독립 집합 문제를 해결하는 예제입니다.#include #include #include const int MA.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 6: 트리의 기본 개념 트리 (Tree)트리는 계층적 자료구조로, 노드(Node)와 간선(Edge)으로 구성됩니다. 트리는 하나의 루트(Root) 노드를 가지며, 각 노드는 자식 노드를 가질 수 있습니다. 트리는 사이클이 없는 비순환 그래프입니다.트리의 용어:루트 노드 (Root Node): 트리의 최상위 노드입니다.부모 노드 (Parent Node): 특정 노드의 바로 위에 있는 노드입니다.자식 노드 (Child Node): 특정 노드의 바로 아래에 있는 노드입니다.리프 노드 (Leaf Node): 자식 노드가 없는 노드입니다.서브트리 (Subtree): 노드와 그 자손 노드들로 이루어진 트리의 부분 집합입니다.높이 (Height): 루트 노드에서 리프 노드까지의 최대 경로 길이입니다.이진 트리 (Binary Tree)이진 .. 2024. 8. 1. [알고리즘] 11. 심화 자료구조 Index 1. 우선순위 큐와 힙 2. 트리 3. 바이너리 인덱스 트리 4. 참고자료1. 우선 순위 큐와 힙우선순위 큐- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조- 데이터를 우선 순위에 따라 처리하고 싶을 때 사용- 삽입/삭제시 O(logN)- heap 정렬은 O(NlogN) 구현 종류1) 리스트 이용해 구현2) heap을 이용해 구현 Heap- 완전 이진 트리 자료구조: root 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 삽입되는 tree- Heap에서는 항상 root 노드를 제거- Min Heap / Max Heap 힙 정렬def heap_sort(iterable): h = [] result = [] for val in iterable: he.. 2024. 7. 20. [목차] 자료구조 1. 배열(Array)1.1 배열 정의1.2 배열 ADT1.3 프로그램 언어별 메서드2. 연결리스트(Linked List)2.1 연결리스트 정의2.2 연결리스트 종류: Singly Linked List, Doubly Linked List2.3 연결리스트 ADT2.4 연결리스트 구현2.5 프로그램 언어별 메서드3. 스택(Stack)3.1 스택 정의3.2 스택 ADT3.3 스택 구현3.4 프로그램 언어별 메서드4. 큐(Queue)4.1 큐 정의4.2 큐 ADT4.3 큐 구현4.4 프로그램 언어별 메서드5. 덱(Deque)5.1 덱 정의5.2 덱 ADT5.3 덱 구현5.4 프로그램 언어별 메서드6. 해시(Hash)6.1 해시 정의6.2 해시 ADT6.3 해시 구현6.4 프로그램 언어별 메서드7. 트리(Tree.. 2024. 7. 19. 이전 1 다음 반응형
