목록 트리 (2)
반응형

Stargazer

[백준] 1991번: 트리순회 C++ 풀이

접근: 트리를 이용해서 푸는 문제 트리를 순회하는 순서만 생각하면 된다. 전략: 우선 트리 저장을 배열 형태로 저장하는데, 저장 방식은 다양하나 나는 각 알파벳을 숫자로 치환해서 저장하도록 하겠다. (공간을 많이 잡아먹지 않는 문제이기 때문에, 편한 대로 쓰도록 하겠다. 즉, 최적화된 건 아님) 순회할 때 필요한 정보는 현재 위치와 자식 노드의 유무이다. 구현: #include #include using namespace std; struct Node{ int left; int right; }; vector nod; int n; int c2n(char a){ return (a != '.') ? static_cast(a - 'A') : -1; } char n2c(int a){ return (a + 'A')..
Undergraudate basics(학부생 기초)/자료구조, 알고리즘 2022. 5. 13. 18:10
[자료구조] 트리 후위순회 결과와 깊이 순서로 트리 구조 구하기

*자료구조 시간에 문제풀다가 배운 내용을 정리한 것입니다. 입력: 후위 순회한 결과와 그 노드의 깊이 출력: 전위 순회한 결과 예를 들어 후위 순회한 결과가 다음과 같이 주어 졌을때, 값: 5 2 8 9 10 6 7 3 4 1 깊이: 2 1 3 3 3 2 2 1 1 0 출력은 다음과 같다 1 2 5 3 6 8 9 10 7 4 트리를 그림으로 그리면 다음과 같다. #솔루션 우선 깊이의 개념을 이해해야한다. 깊이는 노드가 루트에서부터의 간선의 개수이다. 그리고 후위 순위는 가장 왼쪽 것부터 그리고 가장 깊이가 깊은 것부터 처리한다. 따라서 깊이의 변화로 이들의 관계가 무엇인지 알 수 있다. 우선 노드 1의 자식은 깊이가 1인 녀석들이다. 그래서 입력값으로부터 2 3 4 임을 알 수 있다. 여기서 더 내려가면..
Undergraudate basics(학부생 기초)/자료구조, 알고리즘 2021. 4. 23. 00:31
Prev 1 Next