본문 바로가기

Algorithms/tree13

알고리즘 문제 해결 전략 2 06장 트리 (2) 21.5 문제 요새 성벽들의 정보가 주어질 때 임의의 두 지점 간을 이동하기 위해 최대 몇 번이나 성벽을 넘어야 하는지 계산하는 프로그램을 작성하시오. 21.6 풀이: 요새 성벽들은 서로 닿거나 겹치지 않는다는 조건에 주목하면 성이 계층적 구조로 구성되어 있음을 알 수 있음. 따라서 성벽들 간의 포함 관계를 트리로 나타내서 문제를 풀어낼 수 있음. 이렇게 트리를 구성하고 나면, 한 구역에서 인접한 다른 구역으로 가기 위해 성벽을 넘는 일은 이 트리에서 간선을 따라 다른 노드로 옮겨가는 것으로 대응됨. 따라서 두 지점을 왕래하기 위해 성벽을 가장 많이 넘어야 하는 경우를 찾는 문제는 트리에서 가장 멀리 떨어진 두 노드를 찾는 문제가 됨. 트리에서 가장 긴 경로 찾기 이와 같은 모델링 과정을 거치면 이 문제.. 2021. 7. 3.
알고리즘 문제 해결 전략 2 06장 트리 (1) void printPostOrder(const vector& preorder, const vector& inorder) { const int N = preorder.size(); if (preorder.empty()) return; const int root = preorder[0]; const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin(); const int R = N - 1 - L; printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L)); printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N)); cou.. 2021. 7. 1.
5-1 비밀 어떤 비밀 이야기. 앤명의 아이들 유치원, 선생님 아이들 비밀 이야기 어떻게 전달되었는지에 대한 정보 주어짐. 이 정보로 알 수 있는 각 아이들이 친하다고 생각하는 친구들의 수를 구함 어떤 비밀이 전달될 수 있는 가장 긴 길이도 구하자 에이가 비를 친하다고 생각하더라도, 비가 에이를 친하다고 생각하지 않을 수 있음을 유의. 인풋에 대한 정보 오케이 #include #define MAX_N 10 #define MAX_K 30 int N, K, M; int INPUT[MAX_K][MAX_N + 1]; int MAP[MAX_N + 1][MAX_N + 1]; int FRIEND[MAX_N + 1]; int visit[MAX_N + 1]; int result; int path[MAX_N + 1]; #define .. 2018. 11. 12.
4-3 Inversion Counting 길이 앤의 수열 에이가 주어짐. 에이의 원소들을 각각 에이, 에이, 에이앤 이라고 할 때 아이 2018. 11. 12.

티스토리툴바