알고리즘이란?
알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다. 알고리즘을 설계하기 위해서는 우선 해야 할 작업을 명확하게 명시해야 한다. 설계하려는 알고리즘이 "무엇을" 하는지는 입력과 출력에 의해 명시할 수 있다. 예를 들어, 학생 100명의 시험점수를 입력으로 받아 최고점을 출력하는 작업을 한다면 입출력을 다음과 같이 표현할 수 있다. 입력 : 100개의 점수출력 : 입력된 100개의 점수 중 최대값 이 입출력을 다음과 같이 좀더 구체적으로 표현할 수도 있다. 입력 : 100개의 변수 x[1],...,x[100]의 값출력 : x[1],...,x[100] 중 최대값 이런 입출력을 요구하는 알고리즘은 대략 다음과 같은 모양을 가질 것이다. maxScore(x[], n..
레드블랙 트리(Red-black tree)
이진검색트리는 저장과 검색에 평균 Θ()시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 잘 이루지 못한다. 균형이 많이 깨지면 Θ(n)에 근접한 시간이 소요될 수도 있다. 그래서 고안해 낸 것이 균형잡힌 이진검색트리이다. 균형잡힌 이진검색트리는 최악의 경우에도 이진트리의 균형이 잘 맞도록 유지한다. 균형잡힌 이진검색트리로 대표적인 것은 레드블랙트리와 AVL트리다. 레드블랙 트리는 자가균형이진탐색 트리(self-balancing binary search tree)로써, 대표적으로 연관배열(associative array) 등을 구현하는데 쓰이는 자료구조이다. 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다. 트리에 n개의 원소가 있을때..
이진트리의 순회 (Binary Tree Traversal)
이진검색트리같은 이진트리(Binary tree) 구조의 자료구조에서 검색, 출력 등의 이유로 전체 노드들을 방문(visit)하는 것을 순회(traversal)이라고 합니다. 아시다 싶이 이진트리의 구조는 최상위에 루트(root)가 존재하고 좌측에는 왼쪽 서브트리가 , 오른쪽에는 오른쪽 서브트리의 모양을 갖습니다. 대표적인 이진트리 순회 방법에 3가지의 방법이 있습니다. 루트의 방문 순서에 따라 구분이 됩니다. 1. 전위 순회 (Preorder Traversal)Root -> Left Tree -> Right Tree ( 루트를 제일 처음에 방문 )2. 중위 순회 (Inorder Traversal)Left Tree -> Root -> Right Tree ( 루트를 중간에 방문 )3. 후위 순회 (Posto..