트리와 잣의 데이터 구조 및 변환
트리의 저장 방식
부모 표현법
각 노드를 배열로 관리하며, 각 요소는 데이터와 부모의 인덱스를 포함한다.
typedef struct {
TElemType data;
int parent; // 부모 노드의 인덱스
} PTNode;
#define MAX_TREE_SIZE 100
typedef struct {
PTNode nodes[MAX_TREE_SIZE];
int root; // 루트 위치
int count; // 총 노드 수
} PTree;
자식 ...
7월 27일 20:21에 게시됨
점분치 학습 노트
점분치란
트리 구조상의 경로 문제를 해결하기 위해 분치 tư duy를 적용하는 기법입니다. 경로를 두 부분으로 나눌 때, 하나는 중앙 노드를 지난 경로이고, 다른 하나는 중앙 노드를 지난 경로가 아닙니다.
중앙 노드를 지난 경로를 처리할 때는 분치 tư duy를 재귀적으로 하여 서브 트리로 문제를 전가합니다. 기본적으로 O(n²)의 복잡도를 가지지만, 각 단계에서 서브 트 ...
7월 13일 01:18에 게시됨
트리(Tree) 자료구조의 기본 개념과 활용
자료구조는 프로그램의 효율성과 직결되는 중요한 요소입니다. 다양한 자료구조 중에서도 트리(Tree)는 계층적 데이터를 효과적으로 표현하는 비선형 자료구조의 대표적인 예시입니다. 특히 웹 프론트엔드 개발에서 자주 접하는 DOM(Document Object Model)이 트리의 한 형태로 구현되어 있어, 트리에 대한 이해는 웹 개발자에게 필수적입니다. 이 글에서는 트리 ...
7월 5일 02:58에 게시됨
AGC005 문제 해설
A - STring
스택을 이용한 시뮬레이션으로 해결합니다. 문자열을 순회하면서 'S'는 스택에 추가하고, 'T'가 등장할 때 스택 상단이 'S'이면 제거합니다. 최종적으로 남은 스택 크기가 정답입니다.
#include <iostream>
#include <stack>
using namespace std;
int main() {
string str;
cin >> str;
stack<char> stk;
for (char c ...
5월 31일 02:30에 게시됨
NOI 2025 연습 문제 풀이 기록 (제5회)
라운드 #77 - 20250521
A. 직렬 연결 (link)
문제 요약
각 정점에 두 가중치 \(a_i, b_i\)를 가진 트리가 주어진다. 단순 경로가 "좋은 경로"가 되려면 경로상의 \(b\) 합계와 경로상의 최소 \(a\) 값의 곱이 상수 \(V\) 이상이어야 한다. 모든 좋은 경로 중 \(\sum b\)의 최솟값을 구한다.
핵심 아이디어
정점 분할을 적용하면 조건은 \((B_u+B_v)\min(A_u,A_v) \ge V\) ...
5월 24일 02:35에 게시됨