⭐️ 난이도 Silver 1 ⭐️ 문제 https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net ⭐️ Idea flow 먼저 이 문제에 써져 있는 설명을 보면 상근이가 어떤 순서로 도시를 방문하는지에 대한 규칙이 적혀있다. 간단하게 정리를 해보자면 1. 왼쪽 자식이 있다면 왼쪽 자식이 없을 때까지 방문을 하고 해당 노드를 방문한다. 2. 왼쪽 자식들을 모두 방문 했다면, 현재의 노드를 방문한다. 3. 현재 노드를 방문했다면, 오..
Coding test/Baekjoon
⭐️ 난이도 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을 이용해서 후..
⭐️난이도 골드 5 ⭐️문제 https://www.acmicpc.net/problem/1068 트리의 노드의 개수와 각 노드의 부모가 주어진다. 입력으로 "지울 노드의 번호"가 주어진다. 입력으로 주어진 노드를 지우고 난 후, 트리에 남은 노드들 중 리프 노드(자식이 없는 노드)의 개수를 출력하면 되는 문제이다. 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net ⭐️ 내 풀이 & Code 분류가 트리로 되어 있어 처음엔 이진 트리라고 생각했고, 이진 트리를 이용하여 문제를 풀 생각이었다. 하지만 잘 읽어보..
