All Posts

이진 트리 이진 트리는 각 정점의 자식의 수가 최대 2개인 트리이다. 이때 자식은 왼쪽 자식 혹은 오른쪽 자식으로 지정된다. 트리 운행 트리의 각 정점을 정확히 한 번씩 방분하는 체계적 방법으로 트리를 운행한다. 순회라고도 한다.이진 트리에서 운행은 전위 운행법(preorder traversal), 중위 운행법(inorder traversal), 후위 운행법(postorder traversal)이 존재한다. 전위, 중위, 후위에서 전, 중, 후는 운행 중 루트의 위치를 말한다. 전위는 루트를 먼저 처리하고, 중위는 중간에, 후위는 마지막에 처리한다. 전위 운행법입력: $ T $ (이진 트리의 루트 혹은 트리가 비어있음을 나타내는 NULL)출력: $ \text{process} $ 에 따라 종속적preord..

신장 트리 $ T $ 가 그래프 $ G $ 의 모든 정점을 포함하는 부분 그래프이면서 트리라면 $ T $ 를 $ G $ 의 신장 트리라 한다.일반적으로 그래프는 여러 개의 신장 트리를 가진다.예를 들어 위와 같은 그래프에는 아래와 같은 신장 트리가 있을 수 있다. 주황색 선으로 표시된 것이 신장 트리이다.그래프 $ G$ 가 신장 트리 $ T $ 를 가지고 있다는 것과 $ G $ 가 연결되어 있다는 것은 동치이다. 증명은 다음과 같다.그래프 $ G $ 가 신장 트리 $ T $ 를 가진다 가정하고, $ a, b \in V_G $ 를 가정하자. 그렇다면 $ a, b \in V_T $ 이다. $ T $ 가 트리이므로 $ a $ 에서 $ b $ 로의 경로 $ P $ 가 존재하며 따라서 연결되어 있다.반대로 $ G..

고윳값과 고유벡터 $ n $ 차 정사각행렬 $ A $ 와 $ \mathbf{x} \in \mathbb{R}^n $ 및 $ \lambda \in \mathbb{R} $ 에 대해 다음이 성립하면 $ \lambda $ 를 $ A $ 의 교윳값이라 하고, $ \mathbf{x} $ 를 $ \lambda $ 에 대응하는 고유벡터라 한다.$$ A \mathbf{x} = \lambda \mathbf{x} $$즉 행렬과의 곱이 실수와의 곱과 동일할 때 고윳값과 고유벡터를 말할 수 있다.$ \mathbf{x} \in \mathbb{R}^n $ 에 대하여 $ I_n \mathbf{x} = 1 \times \mathbf{x} $ 이므로 단위행렬 $ I_n $ 의 고윳값은 $ \lambda = 1$ 뿐이고, 영벡터가 아닌 $..

트리 트리는 $ \forall v, w \in V $ 에 대해 $ v $ 에서 $ w $ 로의 유일한 단순 경로가 존재하는 그래프를 말한다. 루트 트리(rooted tree)는 특별한 정점이 루트(뿌리)로 지정된 트리이다. 근 트리라고도 한다.어떤 정점 $ v $ 의 레벨(level)은 루트에서 $ v $ 로의 단순 경로의 길이가 되고, 루트 트리의 높이(height)는 최대 레벨 값이 된다.$ T $ 가 루트 $ v_0 $ 를 가진 루트 트리이고, $ x, y, z \in V $ 이며 $ (v_0, v_1, \dots, v_n ) $ 을 $ T $ 에서의 단순 경로라 하면 기본적인 용어들은 다음과 같다.부모 (parent): $ v_{n-1} $ 은 $ v_n $ 의 부모조상 (ancestor): $ ..

기수 정렬  여러 정렬들이 각 값을 비교한 후 알맞은 위치를 찾아가는 것과 다르게 어떤 정렬들은 값을 비교하지 않고 정렬한다. 기수 정렬이 대표적인 예시이다.사용하는 진법에 맞게 버킷을 만들고, 버킷에 차례대로 넣고, 작은 순서대로 꺼내면 정렬이 된다. 한자리 수들로 이루어진 리스트를 정렬하는 경우 버킷에 넣다 빼는 것을 한번만 하면 되지만, 두자리 수가 있다면 두번, 세자리 수가 있다면 세번 넣었다 빼야한다. 즉 리스트의 길이에 큰 영향을 받는 다른 정렬 방식과 다르게 리스트 내 최대값의 자리수에 영향을 더 많이 받는다는 특징이 있다. 예시 예를 들어 위와 같은 리스트를 정렬한다고 해보자. 먼저 아래와 같이 버킷을 만들어주어야 한다.가장 낮은 1의 자리를 기준으로 버킷에 차례로 담아준다.$$ \vdot..

병합 정렬   리스트를 균등하게 분할하고, 병합하면서 정렬하는 방법이다. 분할 정복 알고리즘의 대표적 예시 중 하나이다. 합병 정렬이라고도 한다.정렬은 데이터를 크기가 1이 될때까지 분할하고 다시 병합하면서 일어난다. 병합할 때 분할된 왼쪽 부분 리스트와 오른쪽 부분 리스트의 첫번째 값부터 차례대로 읽으면서 작은 값을 임의의 리스트에 넣어 정렬하는 것이다. 그렇게 병합이 된다면, 다시 상위의 부분 리스트와 병합하여 정렬하고, 다시 상위의 부분 리스트와 병합하여 정렬하여 최종적으로 분할된 모든 리스트를 병합하면 정렬이 끝난다. 이때 분할에서 재귀가 사용된다.새로운 리스트를 만들어서 병합 과정에서 사용하기 때문에 별도의 메모리 공간이 필요하고, 각 분할을 재귀로 구현해야하기 때문에 스택 메모리도 많이 사용한..

힙 정렬  최소 힙이나 최대 힙을 이용하는 정렬 방법이다. 최소 힙이나 최대 힙에 삽입한 후에 루트노드부터 삭제하면서 추출하면 정렬이 된다.힙을 구현하는 것이 귀찮을 뿐 힙이 구현되어 있다면 간편하게 구현할 수 있는 정렬 방법이고, 시간복잡도도 삽입에서 $ \mathcal{O}(\log_2 n) $, 삭제에서 $ \mathcal{O} (\log_2 n) $ 인데, 각 원소마다 삽입 삭제가 일어나므로 $ \mathcal{O} (n \log_2 n) $ 의 시간복잡도를 가지기 때문에 준수한 정렬 방법이다.힙과 관련된 내용은 링크를 참고하면 된다. 구현 | C void heap_sort(int list[], int n) { Heap heap; init(&heap); for (int i = 0;..

퀵 정렬  정렬을 사용할 때 일반적인 상황에서 가장 우수한 정렬 방법 중 하나이다. 분할정복법을 활용하는데, 리스트를 두개의 부분리스트로 비균등 분할하고 임시 정렬한 후 다시 분할하는 방법으로 정렬한다.피벗, 즉 축을 정해서 축을 기준으로 피벗보다 작은 값과 피벗보다 큰 값으로 분할하고 다시 그렇게 분할된 리스트에서 피벗을 설정하고 그 피벗을 기준으로 작은 값과 큰 값으로 분할하고, 다시 그렇게 분할된 리스트에서... 반복하여 정렬하는 방식이다. 왼쪽부터 오른쪽으로의 탐색이 하나, 오른쪽에서 왼쪽으로의 탐색이 하나 있어 만약 왼쪽에서 오른쪽으로 이동하다가 피벗보다 큰 값을 만나면 멈추고, 오른쪽에서 왼쪽으로 이동하다가 피벗보다 작은 값을 만나면 멈춘다. 두개 모두 멈추면 두 값을 교환하고, 다시 반복한다..

셸 정렬  어느 정도 정렬된 상태에서 삽입 정렬이 효율적인 것에 착안하여 만들어진 정렬 방법이다. 삽입 정렬은 요소들이 이웃한 위치와만 교환이 이뤄지기 때문에 특정 값이 멀리 이동하는 데에 많은 교환이 필요하다. 이때 요소를 멀리 떨어진 위치와 교환할 수 있다면 더 적은 교환으로 요소를 이동시킬 수 있을 것이다. 즉 삽입 정렬에서 한 칸이면 간격을 늘린다면 더 멀리 떨어진 요소를 효율적으로 옮길 수 있다는 것인데, 이런 방식의 정렬을 사용하는 것이 셸 정렬이다.먼저 정렬 대상 리스트를 일정 간격의 부분 리스트로 나누고 나뉜 각 부분 리스트를 삽입 정렬한다. 정렬이 끝난 후 다시 간격을 줄이고 정렬하고, 반복하여 간격이 1인, 즉 원래의 삽입 정렬과 똑같이 될 때까지 부분으로 나누고 정렬한다. 마지막 간격..

삽입 정렬  차례에 해당하는 수를 앞쪽 올바른 자리에 삽입하는 정렬 방식이다. 이미 정렬되어 있다면 정렬된 것을 확인하고 정렬이 종료된다는 장점이 있다.정렬은 두번째 자리의 값부터 확인한다. 두번째 자리의 값의 바로 앞 값이 자신보다 크다면 그 값을 교환한다. 그 후 세번째 자리의 값을 선택하여 자신의 앞의 값과 비교하고 자신보다 크다면 교환한다. 만약 교환되었다면 다시 자신의 앞의 값과 비교하고, 크다면 교환한다. 이를 끝까지 반복하면 정렬이 완료된다.따라서 만약 자신의 앞의 값이 자신보다 작다는 것이 확인된다면 정렬되어 있다는 뜻이기 때문에 따로 교환이 일어나지 않고 넘어간다. 즉 이미 정렬되어 있다면 모든 값이 정렬되어 있다는 것을 확인하고 정렬 알고리즘이 종료되기 때문에 버블 정렬, 선택 정렬이 ..