자료구조

세그먼트 트리(Segment Tree) 배열 간격에 대한 정보를 이진 트리에 저장하는 자료구조 여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조 세그먼트 트리의 특징 이진 트리 기반 각 노드는 left, right 노드 두 개만의 자식을 가질 수 있음 구간 정보 저장 각 노드는 자신이 나타내는 구간의 정보를 저장 배열에서 특정 구간의 합을 구하는 방법 배열을 이용하여 선형적으로 구하기 트리 구조를 이용하여 구하기 배열을 이용하여 선형적으로 구하기 배열 A 배열 A에서 Index 2 .. 8 까지의 합 구하기 트리 구조를 이용하여 구하기 트리 A 이러한 세그먼트 트리가 존재할 경우 구간 합을 구하는 시간은 O(logn) 세그먼트 트리 구현 구간 합 저장..

너비 우선 탐색 (Breadth First Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐하는 방법 Example private class BFSExample { private lateinit var visited: BooleanArray private val resultList = mutableListOf() fun solution( nodeSize: Int, edgeSize: Int, edges: Array ) { val sortedEdges = edges.map { it.sorted() }.toTypedArray() // for (i in 1 until sortedEdges.size) { // println("node = $i, child = ${sortedEdges[i]}") // }..

깊이 우선 탐색 (Depth First Search) 트리나 그래프에서 최대한 깊숙하게 탐색한 이후 가장 최근의 갈림길로 돌아가 다른 노드를 탐 DFS 구현 방법 재귀 호출을 이용한 구현 private fun dfs( edges: Array, node: Int = 1 ) { resultList.add(node) for (next in edges[node]) { if (!visited[next]) { visited[node] = true dfs(edges, next) visited[node] = false } } } 스택을 이용한 구현 private fun dfsUsingStack( edges: Array, node: Int = 1 ) { val deque = ArrayDeque() deque.add(no..

트리 순회 (Tree Traversal) 트리 구조의 모든 노드를 방문하는 방법 트리의 모든 노드를 한 번씩 방문하고 각 노드에 대해 원하는 작업을 수행하는 방법 전위 순회 (Preorder traversal) 현재 노드에 대한 작업을 수행 이후 각 자식 노드를 순서대로 방문하여 작업을 수행 Example fun preOrder(root: TreeNode) { print(root.data) root.left?.let { preOrder(it) } root.right?.let { preOrder(it) } } 중위 순회 (Inorder traversal) 현재 노드에 대한 작업을 수행 이후 각 자식 노드를 순서대로 방문하여 작업을 수행 Example fun inOrder(root: TreeNode) { r..