노드의 차수 : 어떤 노드가 가지고 있는 자식 노드의 개수 전체 트리의 차수 : 트리가 가지고 있는 노드의 차수중에 가장 큰값 트리의 레벨 : 트리의 각층에 번호를 매기는 것, 루트의 레벨은 0또는 1이고 한층씩 내려갈 수록 1씩증가 트리의 높이 : 트리가 가지고 있는 최대레벨을 말한다. 이진트리의 성질 - N개의 노드를 가진 이진트리는 N-1개의 간선을 가진다. 높이가 h인 이진트리는 최소 h개의 노드를 가지며, 최대 2^(h+1)-1 개의 노드를 가진다.(루트의 레벨을 0이라 가정) - 노드의 개수가 1 이상인 이진트리에서 차수(분지수)가 i인 노드의 개수를 Ni라고 할때, N0 = N2 +1 이다. 증명 ) n = n0+n1+n2 (전체 노드의 개수는 차수가0인 노드와 1인노드와 2인 노드의 개수를..
Major/Data Structure
1. 연결 리스트 1) 정의 : 자료가 순서를 가지고 나열된 자료구조를 이야기 한다. 2) 리스트의 표현 ⓐ 배열 이용 - 이 방식은 리스트의 각 원소마다 배열의 원소에 대응시킨다. - A[k]를 읽거나 교체하는 연산은 상수시간이 걸리지만, 삽입과 삭제 연산은 순차매핑을 유지하기 위해 원소의 이동을 필요로 하므로 많은 시간이 소요된다. * 순차 매핑 : 배열이 메모리의 연속적인 공간을 차지함 ⓑ 연결 리스트 이용 - 연결 리스트란 화살표로 표시되는 링크를 가진 노드의 순서 리스트 이다. - 첫번째 노드를 가르키는 포인터의 이름이 연결 리스트의 이름이다. * 연결리스트의 노드들은 메모리에 순차적으로 놓여있지 않을 수 있다. 🟡 포인터를 이용하여 연결 리스트 표현하기 - 하나의 노드는 데이터를 갖고있는 데이..
1. 퀵 정렬(분할정복법) 1) 과정 - 리스트에 원소 하나를 고른다(피벗) - 피벗과 다른 n-1개 원소 각각을 비교하여, 피벗보다 작은 것과 큰 것으로 분할한다. - 분할된 두 개의 작은 리스트를 재귀적으로 정렬한다. 2) 피벗 선택방법 - 중앙값(최선 피벗) - 랜덤선택 - 리스트 맨앞, 중간, 맨뒤에 있는 세 원소의 중앙값을 선택 3) 코드 void Quick_sort(int arr[],int i, int j) { int n, cnt = 0; if (i >= j) return; int pivot = arr[(i + j) / 2]; int left = i; int right = j; while (left pivot) right--; if (left
1. 정렬 알고리즘 - 정렬알고리즘은 알고리즘 중에 가장 기본적인 알고리즘 이다. - 이 글에서 살펴볼 알고리즘은 삽입, 선택, 거품(버블), 퀵, 합병(merge), 힙, 이진탐색 트리를 이용한 정렬이다. 1) 삽입정렬 - O(n^2) - 배열의 모든 원소를 앞에서부터 차례대로 배열 부분과 비교하여, 삽입함으로써 정렬하는 알고리즘 - 처음 key 값(처음으로 뽑아 비교할 원소)은 두번째 원소이다 > 과정 두번째 원소 10을 뽑아 첫번째 원소와 비교하여 29보다 작으므로 29왼쪽으로 삽입된다. 세번째 원소 14를 뽑아 두번째 원소와 비교하여 29보다 작으므로 29왼쪽으로 삽입된다. 14는 10보다 크므로 바뀌지 않는다. 네번째 원소 37를 뽑아 세번째 원소인 29와 비교한다. 37이 29보다 크므로 바뀌..
1. 문제 * 길이가 n인 배열 A[0], A[1], ..., A[n-1] 이 입력으로 주어 질때, i번째부터 j번째까지 원소드로 이루어진 배열 A[i], ..., A[j] 를 부분배열이라고 하고, A[i, j] 로 나타낸다. - 부분 배열의 속한 원소들의 합이 최대가 되는 부분 배열을 구하는 것이 이 문제의 목적이다. 이 때 길이가 0인 부분배열도 허용하며, 이 부분배열의 원소들의 합은 0이라고 정의한다. 예를 들어, 아래와 같은 배열이 있다면, -2 -1 3 5 2 -5 0 2 이 배열의 최대부분배열의 합은 몇일까? 3+5+2 = 10 이다. 2. 해결방법 - 최대부분배열의 원소합을 구하는 알고리즘에는 크게 4개가 있다. - 완전탐색, 중복제거한 탐색, 분할정복법, 동적계획법 1) 완전탐색(브루트포스..
