⭐️ 난이도 Gold 4 ⭐️ 문제 https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 각 테스트 케이스마다 이진 트리의 전위 순회, 중위 순회의 결과가 주어진다. 이때, 이진 트리의 후위 순회의 결과를 구하시오. ⭐️ Idea flow 문제에서 전위 순회(preorder)과 중위 순회(inorder)의 결과가 주어진다. 전위 순회를 root 노드를 먼저 방문하는 방법이고, 중위 순회는 root 노드를 중간에 방문하는 방법이다. 이와 같..
Baekjoon
⭐️ 난이도 Silver 1 ⭐️ 문제 https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net ⭐️ Idea flow 먼저 이 문제에 써져 있는 설명을 보면 상근이가 어떤 순서로 도시를 방문하는지에 대한 규칙이 적혀있다. 간단하게 정리를 해보자면 1. 왼쪽 자식이 있다면 왼쪽 자식이 없을 때까지 방문을 하고 해당 노드를 방문한다. 2. 왼쪽 자식들을 모두 방문 했다면, 현재의 노드를 방문한다. 3. 현재 노드를 방문했다면, 오..
⭐️ 난이도 Silver 1 ⭐️ 문제 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하시오. ⭐️ Idea flow 우선 이 문제에서 노드의 갯수가 몇 개 인지 알려주지 않는다. 따라서 eof를 사용해야 한다. while문으로 수를 계속 받아주다가 eof를 만나면 break를 해준다. 전위 순회(preorder)는 root노드를 먼저 방문하는 순..
⭐️난이도 Gold 2 ⭐️문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net ⭐️ Idea Flow 먼저 문제를 해석해보면 친구 관계는 모두 이어져있는 것이 아니라 여러 개의 친구 관계로 이루어져 있을 가능성이 높다. 이 때 바로 생각난 것이 바로 Disjoint Set(서로소 집합)이다. Union-Find 방식을 이용하면 될 것이라고 생각했다. 그리고 Disjoint set를 사용하려면 각 이용자에게 index를 부여해야 한다..
⭐️난이도 Silver 1 ⭐️문제 https://www.acmicpc.net/problem/1927 최소 힙을 구현하면 되는 간단한 문제이다! 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net ⭐️ 내 풀이 & Code 📌 C++에서는 priority_queue를 제공하므로 이를 이용하면 풀 수 있는 문제였다. #include #include #include #include #include #define INF 100000000 using namespace std; int n; // 연산의..
⭐️난이도 Silver 3 ⭐️문제 https://www.acmicpc.net/problem/1935 후위 표기식과 각 피연산자에 대응하는 값이 주어졌을 때, 해당 식을 계산한 결과를 출력하면 되는 문제이다! 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net ⭐️ 내 풀이 & Code 후위표기식은 대학 수업 자료구조 시간에 배운적이 있어서 그렇게 어렵진 않았다. 📌내가 생각한 이 문제에서의 처리 포인트 ① 입력에서 주어지는 피 연산자에 해당하는 값을 어떻게 매핑할 것인가? ② Stack을 이용해서 후..
