728x90 트리 썸네일형 리스트형 [백준알고리즘] 4256번: 트리-C++ 4256번: 트리 (acmicpc.net) 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 이전에 풀었던 '트리의 순회' 문제와 유사하다. [백준알고리즘] 2263번: 트리의 순회-C++ (tistory.com) [백준알고리즘] 2263번: 트리의 순회-C++ 2263번: 트리의 순회 (acmicpc.net) 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 suri78.. 더보기 [백준알고리즘] 2263번: 트리의 순회-C++ 2263번: 트리의 순회 (acmicpc.net) 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 정답률과 골드 문제여서 쉽게 봤다가 시간을 많이 잡아먹었다. 그런데 접근법 자체 때문인 건 아니고, 메모리 초과가 발생했어서 코드를 약간 수정하는 게 너무 귀찮아서 오래 걸렸다. list를 여러번 생성하면서 재귀적으로 문제를 풀었는데, 10만 개가 한 줄로 이어진 경우에는 스택이 모자란 것으로 보인다. 그래서 list를 매번 생성해서 넘겨주는 것이 아닌, 인덱스로 접근하는 방법을 선택했다. 그러다 보니, list를 vector로 변경해주었.. 더보기 [백준알고리즘] 5639번: 이진 검색 트리 -C++ [백준알고리즘] 5639번: 이진 검색 트리 -C++ 5639번: 이진 검색 트리 (acmicpc.net) 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 생각보다 애를 먹었다. 처음에 list 자료형을 이용해 splice 함수로 이리저리 preorder를 postorder로 바꾸려고 시도해봤다. 동작은 하는 것 같으나, 시간 초과/메모리 초과가 발생해 고민을 많이 했다. 그러다가 배열을 쓰는게 훨씬 빠르다는 것을 보고, 배열과 인덱스를 이용해 처리하도록 변경했다. 문제 풀이 트리 탐색 방법은 전.. 더보기 [백준알고리즘] 1991번: 트리 순회 -Python [백준알고리즘] 1991번: 트리 순회 -Python https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다. www.acmicpc.net 이번 문제는 tree traversal (트리 순회) 문제이다. 트리 순회에는 문제에서 요구하는 데로 3가지 방법이 있다. 1. preorder traversal (전위 순회) 2. inorder traversal (중위 순회) 3. postor.. 더보기 이전 1 다음