반응형 [PCCP] Lv3: 길 찾기 게임(42892) 해설 문제- 문제 링크: 길 찾기 게임 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: nodeinfo의 길이. 노드의 개수- 이진 트리 구축 과정에서 nodeinfo를 정렬하는 시간 복잡도: O(NlogN)- 노드를 추가하는 과정에서 최악의 경우는 노드가 한 줄로 연결된 경우이므로 시간 복잡도는 O(N^2)- 전위 순회와 후위 순회는 노드를 한 번씩 탐색하므로 시간 복잡도는 O(NlogN)- 최악의 경우 시간 복잡도는 O(N^2)더보기#include #include #include using names.. 2024. 12. 24. [PCCP] Lv3: 다단계 칫솔 판매(77486) 해설 문제- 문제 링크: 다단계 칫솔 판매 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: enroll의 길이- M: seller의 길이- seller별로 enroll을 탐색하는 시간복잡도: O(N*M)더보기#include #include #include using namespace std;vector solution(vector enroll, vector referral, vector seller, vector amount) { vector answer; unordered_map pa.. 2024. 12. 24. [PCCP] Lv2: 예상 대진표(12985) 해설 문제- 문제 링크: 예상 대진표 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 참가한 인원 수- 같은 번호가 될 때까지 계속해서 2로 나누는 연산: O(logN)더보기#include using namespace std;int solution(int n, int a, int b){ int answer = 0; do { a = (a + 1) / 2; b = (b + 1) / 2; ++answer; } while (a != b); return .. 2024. 12. 24. [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 다음 반응형
