TIL (2022.04.04)

1. 병합 정렬

동일한 문제로 나누고 해결 후 합치는 것 = 분할 정복 (Divide and Conquer)
시간 복잡도는 O(NlogN) = 배열 합치는 과정 N번 반복 + 계속 쪼개기 logN번 반복

병합 정렬 - 엔지니어 대한민국
병합 정렬 - 코딩하는거니

int mergeSort(int low, int high){
    if(low<high){
        int mid = (low+high)/2;
        mergeSort(low,mid);
        mergeSort(mid+1,high);
        merge(low,mid,high);
    }
}

void merge(int low,int mid,int high){
    int i=low,j=mid+1,k=low;

    while(i<=mid && j<=high){
        if(arr[i]<=arr[j])
            merged[k++]=arr[i++];
        else
            merged[k++]=arr[j++];
    }

    while(i<=mid){
        merged[k++]=arr[i++];
    }
    while(j<=high){
        merged[k++]=arr[j++];
    }
    for(int k=low;k<=high;k++){
        arr[k]=merged[k];
    }
}

2. 트리

트리 - 정점끼리 연결되어 있으면서 사이클이 존재하지 않는 것
리프 노드 - 자식이 없는 노드

이진트리 - 자식의 수가 최대 2개인 트리, 자식의 수가 1,0가 되어도 2 이하이기 때문에 이진트리.

• 특정 노드의 위치가 i 라면, 오른쪽은 i2+1 왼쪽은 i2

재귀를 사용하면 쉽게 탐색할 수 있으며, 방문 순서에 따라 세 가지로 나뉨
(1) 전위 = 부모 - 왼 - 오
(2) 중위 = 왼 - 부모 - 오
(3) 후위 = 왼 - 오 - 부모