병합 정렬   리스트를 균등하게 분할하고, 병합하면서 정렬하는 방법이다. 분할 정복 알고리즘의 대표적 예시 중 하나이다. 합병 정렬이라고도 한다.정렬은 데이터를 크기가 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인, 즉 원래의 삽입 정렬과 똑같이 될 때까지 부분으로 나누고 정렬한다. 마지막 간격..

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

선택 정렬  작은 수를 선택해서 앞쪽에 배치하는 정렬 방식이라 선택 정렬이다. 효율적이지는 않지만, 버블 정렬과 함께 구현이 쉽고, 가장 쉽게 생각할 수 있는 정렬 방식이다.정렬은 가장 앞 수를 선택한 후 자신보다 작은 수가 나오면 교환하는 방식으로 진행된다. 끝의 수까지 비교하고, 작을 때 교환했다면 가장 앞에는 리스트에서 가장 작은 수가 올 것이다. 이제 두번째 수를 선택하고 다시 비교, 교환하고, 그 후에는 세번째 수를 선택하고, ... 반복하여 마지막 수 직전에 도달하면 모든 수가 정렬된다. 예시 예를 들어 위와 같은 리스트를 정렬한다고 해보자.먼저 위와 같이 가장 앞을 선택하고 그 다음 수와 비교한다. 선택된 수인 9가 비교 대상인 2보다 크다.그러므로 두 수를 바꿔준다. 그 후 아래와 같이 다..

버블 정렬  정렬할 때 큰 수를 뒤로 미루는 것 때문에 거품이 올라오는 것 같아 이름 붙여진 정렬 방식이다. 효율적이지는 않지만, 구현이 쉽고, 가장 쉽게 생각할 수 있는 정렬 방식이다.정렬은 인접한 두 수를 선택한 후 비교하고, 큰 수가 앞에 있다면 두 수를 교환하는 방식이 반복되며 일어난다. 첫번째 수와 두번째 수를 선택한 후 비교, 교환하고, 두번째 수와 세번째 수를 선택한 후 비교, 교환하고, ... 반복하여 마지막 수에 도달한다면 가장 큰 수가 가장 마지막 자리에 도달하게 된다.이제 다시 첫번째 수와 두번째 수를 선택한 후 비교, 교환하고, 두번째 수와 세번째 수를 선택한 후 비교, 교환하고, .. 반복하여 마지막 수 앞 칸에 도달하면 뒤 두 수가 정렬된다. 앞선 정렬을 통해 마지막 수가 정렬되..

그래프 동형사상 어떤 두 그래프가 겉보기에는 완전히 다른 그래프처럼 보이지만, 구조만 때어놓고 본다면 같은 구조를 가진 그래프일 수 있다. 아래 그래프를 보면 정점과 간선의 이름, 생김새가 다르게 보인다.그러나 재배열 한다면 비슷한 그래프처럼 보인다.이처럼 구조가 같은 그래프를 동형이라 한다. 좀더 명확하게는 다음과 같이 정의힌다.그래프 $G_1 = (V_1, E_1)$ 과 그래프 $G_2 = (V_2, E_2)$ 가 동형(isomorphic)이라 할 때 다음 조건을 만족하는 함수 쌍 $f$ 와 $g$ 가 존재하고, 이를 동형사상(혹은 동형함수)이라 한다.$f: V_1 \to V_2$ 와 $g: E_1 \to E_2$ 는 전단사 함수이다. 즉 $f$ 는 $V_1$ 의 모든 정..

행렬표현 일반적으로 $n$ 차원 벡터공간 $V$ 에서 $m$ 차원 벡터공간 $W$ 의 선형변환을 행렬변환으로 나타낼 수 있고, 이는 좌표벡터를 통해 확인해볼 수 있다.$n$ 차원 벡터공간 $V$ 의 순서 기저를 $S = \{ \mathbf{x_1}, \mathbf{x_2}, \cdots, \mathbf{x_n} \}$ 이라 하고, $m$ 차원 벡터공간 $W$ 의 순서 기저를 $R = \{ \mathbf{y_1}, \mathbf{y_2}, \cdots, \mathbf{y_m} \}$ 이라 하며, $T: V \to W$ 를 선형변환이라 하자. $\mathbf{x_i} \in S$ $(i = 1, 2, \cdots, n)$ 에 대하여 $ T(\mathbf{x_i})..

한글 깨짐 VS Code 에서 코딩하면 기본적으로 UTF-8로 인코딩된다. 그런데 Code Runner 를 이용하면 터미널을 이용해서 코드를 컴파일하고 출력하는데, 이때는 윈도우 설정인 EUC-KR(혹은 CP949)로 인코딩된다. 따라서 한글이 깨지게 된다.이를 해결하기 위해서 터미널에 다음 명령어를 입력하여 UTF-8로 인코딩해주어야 한다. 물론 아예 코드를 EUC-KR로 작성하는 것도 방법일 수 있지만, 이렇게 작성된 코드는 깃허브에 올리거나 할 때 깨지기 때문에 윈도우 터미널 설정을 건드는 것이 좋다.-encoding UTF-8이제 이 입력어를 Code Runner 를 이용할 때 마다 입력되도록 하면 될 것 같다.VS Code 의 좌측 확장을 클릭하고 Code Runner 를 찾은 다음 톱니바퀴를 ..