랄뚜기의 코딩일기

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한..

https://www.acmicpc.net/problem/11812 11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net 오랜만에 보는 매우 쉬운 문제. 자식 노드를 N이라고 할 때, 부모 노드는 (N-1)/K라는 것을 이용하면 금방 풀린다. 단, 출력이 많으므로 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);을 하는 것을 잊지말자!(개고생함) #include using namespace std; long long..

https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 이진트리에서 전위순회와 중위 순회가 주어졌을 때, 후위 순회를 구하는 문제이다. 저번에 후위 순회와 중위 순회가 주어졌을 때 전위 순회를 구하는 문제를 풀어서 쉽게 풀 수 있었다. https://coderecord.tistory.com/5 [BOJ] 2263 트리의 순회 C++ https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤..

https://www.acmicpc.net/problem/19581 19581번: 두 번째 트리의 지름 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리 www.acmicpc.net 트리의 지름을 구하는 것을 응용한 문제이다. 아래 문제를 먼저 풀고 들어오면 괜찮을 것 같다. https://coderecord.tistory.com/9 [BOJ] 1167 트리의 지름 C++ https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 1..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 이 문제를 대충 요약하자면 트리에서 정점->정점까지 가장 긴 거리를 구하는 것이다. 내가 이 문제를 보고 무조건 시작 또는 끝에는 트리의 리프노드일 것을 알았다. 그래서 모든 리프노드(연결 된 노드가 하나밖에 없는 노드)를 구해서 dfs를 각각 돌려 그 중 최댓값을 구하면 되겠다고 생각했는데 바로 시간초과가 떴다. 고민을 하다가 다른 분의 코딩을 참조 했는데 알고리즘은 다음과 같다..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 이 문제는 숫자가 추가로 저장 될 때마다 저장된 숫자 중 가운데 값을 말하는 문제이다. 주어진 시간이 단 0.1초이므로 sort를 쓰게 되면 무조건 시간초과가 나게 된다. 나는 중간이라는 말을 듣고 최대 힙과 최소 힙을 사용하면 되겠다고 생각했다. 중간값을 최대 힙의 탑으로 정하고 중간값 보다 값이 작으면 최대 힙에 값이 크면 최소 힙에 넣어주고 최소 힙의 탑의 값이 바뀌는 경우 ..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 일반적인 계산식(중위 표기식)이 주어졌을 때, 이를 후위 표기식으로 바꾸는 문제이다. 괄호가 들어가서 예외 처리를 많이 해야 하는 문제이지만 다행히 사람들이 많은 반례를 구해놓아서 쉽게 구할 수 있었다. 후위->중위, 중위->후위로 변환할 때는 stack을 이용하면 된다. 또, 이 문제를 풀 때 개념은 계산순서의 우위를 이용해야 한다는 것이다. 1. * , / 이 올 경우 자신보다 계산순..

https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 후위 표기식이 주어졌을 때 이를 계산하는 문제이다. 스택을 만들고 연산기호( * , / , + , - )가 오는 경우는 위에서 두개를 계산하고 push 그 외에는 그냥 push해주면 된다. 코드 #include #include #include #include #define ch 65 using namespace std; string s; double alpa[26]; int main()..

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 트리를 공부 중이라면 꼭 풀어야 할 문제라고 생각한다. 전위 순회, 중위 순회, 후위 순회의 관계를 알아야 풀 수 있는 문제이다. 위와 같은 트리를 중위 탐색 후위 탐색한 결과이다. 위를 보고 재귀를 사용하면 쉽게 풀 수 있을 것이라 생각했다. 중위 순회은 루트노트 1의 기준으로 보았을 때, 1의 왼쪽에는 왼쪽 서브트리의 노드들이 오른쪽에는 오른쪽 서브트리의 노드들이 있음을 알 수 있었다. 후위 순회는 처음에 직관적으로 중위 순회..