이진 탐색 트리(BST)모든 노드가 다음의 규칙을 만족하는 이진트리 왼쪽 subtree의 모든 값들은 현재 노드보다 작고 오른쪽 subtree의 모든 값들은 현재 노드보다 크다.(단, 보통은 중복 허용 안함) BST의 탐색 찾으려는 값에 따라 작으면 왼쪽, 크면 오른쪽으로 가기 만약 leaf에 도달해도 못 찾았다면 해당 요소가 없다BST의 삽입 적당히 탐색하고 알맞은 위치에 넣기BST의 삭제만약 leaf 노드라면 그냥 삭제만약 leaf 노드가 아니라면해당 노드 기준 왼쪽 subtree의 제일 큰 값또는 노드 기준 오른쪽 subtree의 제일 작은 값을 선택해 노드 삭제한 자리에 넣기연산의 시간 복잡도 최선평균최악탐색O(1)O(logN)O(N)삽입O(1)O(logN)O(N)삭제O..

기존까지 다뤘던 배열, 연결 리스트, 스택, 큐는 선형 자료구조!트리특징부모-자식 관계    root 노드를 제외하면 전부 부모 가짐    leaf 노드를 제외하면 전부 자식 가짐계층의 분화가 일어난다: 여러 레벨로 데이터가 구조화된다.탐색에 효율적임: O(logn)효율적인 삽입 연산현실 반영을 잘 함: 실제 현실의 구조와 많이 비슷함선형 구조보다 더 복잡한 구조 표현 가능배열과 연결 리스트의 단점 보완트리 ADT노드: 데이터가 저장된 요소엣지: 노드 사이를 잇는 선용어뿌리(root), 잎(leaf), 비단말(non-terminal)뿌리: 맨 위에 있는 노드잎: 맨 끝에 있는 자식이 없는 노드비단말: 뿌리도 잎도 아닌 노드부모(parent), 자식(child), 형제(sibling):부모: 어떤 노드를 ..

머지 정렬 (merge sort)배열을 쪼개서 정렬 -> 다시 합치며 정렬예) 4 3 2 1 를 정렬한다면    분할 1: (4 3) (2 1)    분할 2: (4) (3) (2) (1)    병합 1: (3 4) (1 2)    병합 2: (1 2 3 4)void merge(int arr[], int left, int mid, int right) { int i, j, k; int n1 = mid - left + 1; int n2 = right - mid; int* L = (int*)malloc(n1 * sizeof(int)); int* R = (int*)malloc(n2 * sizeof(int)); // 호출될 때마다 요소 개수가 바뀌므로 동적할당 if ..

// 중간에 순서를 바꾸는 경우를 위해 swap 함수를 정의해놨다.void swap(int[] arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;} 버블 정렬 (bubble sort)옆에 있는 것과 비교하며 계속 이동예) 4 3 2 1 를 정렬한다면    round 1: 3 2 1 4    round 2: 2 1 3 4    round 3: 1 2 3 4-> 정렬 라운드마다 맨 끝의 수가 정렬된다.void bubble_sort(int[] arr){ for (int i = 0; iarr[j+1]) swap(arr, j, j+1) } }}2중 중첩 반복문에 각 반복문마다 ..

큐큐: FIFO방식의 자료구조먼저 들어온 것이 먼저 나간다큐의 쓰임작업 스케줄링네트워킹큐 ADT데이터 큐도 연결 리스트의 일종head: 큐의 맨 앞을 가리키는 포인터rear: 큐의 맨 뒤를 가리키는 포인터연산endqueue(): 큐의 맨 뒤에 데이터 넣기dequeue(): 큐의 맨 앞에 있는 데이터 가져오고 삭제isFull(): 큐가 가득 찼는지 확인 isEmpty(): 큐가 비었는지 확인  배열로 만든 큐기본 골조는 다음과 같다.const int MAX_SIZE = 5;int queue[MAX_SIZE];int head = -1, rear = -1; //큐가 비어있다는 뜻isEmpty, isFullbool isEmpty(int &head, int &rear){ if (head == -1 && re..

스택스택: LIFO방식의 자료구조먼저 들어온 것이 나중에 나간다스택의 쓰임ctrl+z수식의 valid 평가 (괄호 판별)함수 호출 관리스택 ADT데이터 스택도 연결 리스트의 일종top: 스택의 맨 끝을 가리키는 포인터연산push(): 스택의 맨 위에 데이터 넣기pop(): 스택의 맨 위에 있는 데이터 가져오고 스택에서 삭제peek(): 스택의 맨 위에 있는 데이터 가져오기만 하기isFull(): 스택이 가득 찼는지 확인 isEmpty(): 스택이 비었는지 확인  배열로 만든 스택기본 골조는 다음과 같다.const int MAX_SIZE = 5;int stack[MAX_SIZE];int top = -1; //스택이 비어있다는 뜻isEmpty, isFullbool isEmpty(int &top){ if..

연결 리스트: 데이터와 그 다음을 가리키는 포인터를 저장하는 자료 구조리스트의 유동성은 여기서 나온다!종류singly linked list: 한 방향으로만 포인터가 있는 연결 리스트doubly linked list: 앞, 뒤로 포인터가 있는 연결 리스트circular linked list: 끝의 포인터가 맨 앞을 가리키는 연결 리스트연결 리스트 ADT데이터: node 라고 불림head: 리스트의 시작을 저장하는 포인터tail: 리스트의 끝은 저장하는 포인터 (굳이 없어도 됨)연산삽입삭제방문 등...실제 구현 (singly linked list)기본 뼈대데이터와 포인터로 이루어진 구조체 정의typedef struct node { int data; //int형 데이터 담음 struct node* ..

ADT(Abstract Data Type): 추상 데이터 타입데이터를 어떻게 저장하는지 정의-> 데이터, 데이터 연산 정의 배열: 데이터의 모음    같은 자료형만 넣는다    메모리에 연속적으로 배열되어 있다 2차원 배열 = 1차원 배열의 결합int arr[2][2]일때1차원 int 더블 포인터 배열 arr는 arr[0], arr[1]을 가리킴1차원 int 포인터 배열 arr[0]는 arr[0][0], arr[0][1]을 가리킴int인 arr[0][0], arr[0][1]에는 값들이 담겨있다. 배열의 ADT데이터: 연산    create(size): size 크기의 배열 생성    get(array, index): array의 index에 있는 element를 가져옴    set(array, index..

재귀: 자기 자신을 호출하는 함수base case: 재귀 호출이 끝나는 조건recursive case: 자기 자신을 호출하는 부분base case 빠트리면 재귀가 안끝나니 주의!재귀함수의 동작-> 스택을 이용한다 (컴퓨터 구조 14 참고)함수가 호출되면 스택을 할당받는다자기 자신이 불릴 때마다 스택을 받는다base case에 도달하면 LIFO로 나중에 불린 함수부터 스택을 반환한다.예) 팩토리얼 계산 함수int factorial(int n){ if (n==0) return 1; else return (n * factorial(n-1));}base case = if (n==0) return 1; recursive case = return (n * factorial(n-1));실제로 프로그램을 돌려보면 각 ..

점근 표기법: 알고리즘의 시간/공간 복잡도를 입력 데이터 크기 N에 대해 표기하는 방법아주 큰 N에 대해 고려 (N->무한)가장 영향을 많이 주는 것만 고려예) x^2+100x -> x^2상수나 계수는 무시5x -> x종류Big-O (가장 최악의 경우): 가장 많이 쓰는 표기법Big-Ω (가장 최고의 경우)Big-Θ: (Big-O == Big-Ω)수학적 정의Big-O임의의 함수 f(n)에 대해 양의 상수 c와 n0에 대해f(n)=n0) 이런 c, n0이 존재한다면이때 f(n)은 O(g(n))의 복잡도를 가진다.-> 즉, 일정 수준 이상에서 항상 f(n)보다 더 큰 g(n)을 찾는 것!예) f(n) = 3n^2+n+100일때, 4n^2만 되어도 n0= 10.6 근처 이후로 4n^2이 계속 크다.따라서 g(..