본문 바로가기

트리

(26)

최소 공통 조상 (LCA) LCA(lowest common ancestor) 트리에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드 탐색은 DFS나 BFS를 이용 1. 일반적인 LCA 구하기 트리를 만들 때 각 노드의 부모 노드와 깊이를 저장 a) 선택된 두 노드의 깊이가 다른 경우 더 깊은 노드의 노드를 부모 노드로 오려주면서 같은 깊이로 맞춘다. b) 깊이가 같은 경우 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복 이 때 처음 만나는 노드가 LCA 이 방식을 이용하면 구할 수 있지만! 트리의 높이가 크면 시간이 오래 걸린다. 2. 빠르게 LCA 구하기 with DP 서로의 깊이를 맞춰주거나 같아지는 노드를 찾을 때 ..

구간 곱 구하기 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 이 문제에서 주의해야하는 점 1. 입력으로 주어진 수가 0보다 크거나 같다. 업데이트할 때 기존의 값이 0일 때를 고려해야 한다. 구간 합 처럼 아래에서 위로 올라간다 0 * 변경된 데이터이므로 업데이트가 되지 않는다. // 값을 바꾸고 부모 = 왼쪽 노드 * 오른쪽 노드 while (idx > 1) { idx = idx / 2; tr..

최솟값과 최댓값 https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 구간합 구하기 문제에서 최솟값, 최댓으로 바꾸면 끝 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 ..

구간 합 구하기 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다 범위가 엄청 크고, 배열을 계속 업데이트한다. 세그먼트 트리를 쓰면 시간이 비교적 적게 걸리겠다. 배운 대로 세그먼트 트리를 구현해보자 1. 세그먼트 트리 만들기 2^k >= N을 만족하는 k의 최솟값..

세그먼트 트리 주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행 구간 합 OR 최대, 최소 구하기에 사용 1. 트리 초기화하기 리프 노드의 개수가 데이터 개수(N) 이상이 되도록 트리 배열을 만든다. 2^k >= N을 만족하는 k의 최솟값을 구하고 2^k * 2를 트리 배열의 크기로 정의 예를 들어 N = 8이면 k = 3 배열 크기를 16으로 정한다. 샘플 데이터 {5, 8, 4, 3, 7, 2, 1, 6} 2. 질의값 구하기 주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경 세그먼트 트리 index = 주어진 질의 index + 2^k - 1 질의에서의 시작 인덱스와 종료 인덱스에 대해 부모 노드로 이동하면서 주어진 질의에 해당하는 값을 구함 1. start_index % 2 == 1..

이진 트리 기초 이진 트리 각 노드의 자식 노드의 개수가 2 이하로 구성된 트리 완전 이진 트리 마지막 레벨은 왼쪽부터 채워지 마지막 레벨을 제외하고 완전하게 노드들이 채워짐. 이진 트리의 표현은 배열!! 그래프 표현 방식은 일반적으로 쓰지 않음. 루트 노드의 index는 1부터 시작해야한다!! 그래서 크기 초기화를 할 때, 2 ^ h + 1로 초기화를 한다. 루트 노드 -> index = 1 부모 노드 -> index = index / 2 왼쪽 자식 노드 -> index = index * 2 오른쪽 자식 노드 -> index = index * 2 + 1 트리 순회하기 preorder 현재 -> 왼쪽 -> 오른쪽 inorder 왼쪽 -> 현재 -> 오른쪽 postorder 왼쪽 -> 오른쪽 -> 현재 https://ww..

트라이 기초 트라이 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태 자료구조 특징 1. N진 트리 문자 종류의 개수에 따라 N이 결정 알파벳은 26개의 문자 -> 26진 트리 2. 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 해시 테이블로 풀었던 문제다. 트라이로 풀어보자. 좋은 코드는 아니다. 시간 엄청 걸린다. 현재 문자열을 가리키는 위치의 노드가 공백 ..

리프 노드 개수 구하기 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 노드를 어떻게 제거하는가? 루트 노드부터 dfs 탐색을 수행하면서 리프 노드(자식이 없는 노드)의 개수를 센다. 그리고 삭제 노드를 만나면 탐색을 종료! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48..

이전 1 2 3 4 다음

티스토리툴바