전체 카테고리

[자료구조] 이진트리와 시간복잡도 로그의 의미

이진트리란? : 모든 노드의 차수가 0 이상 2 이하인 트리 이진트리의 시간복잡도는 O(log(n))이라고 들어왔을 겁니다. 하지만 그 과정은 모르는 경우가 많다.(필자도 그랬다) 그래서 과정을 설명하려고 합니다. 그리고 왜 이진트리를 사용할수록 2배씩 빨라진다고 말하는지도 알아보도록 하겠습니다. 1. 이진트리 시간복잡도 계산 트리는 h의 높이를 가질때 최대 n = 2h - 1의 노드 수를 가지고 최소 n = h의 노드 수를 가집니다. 최대 n = 2h - 1 최소 n = h 기억할 것은 최대 노드의 개수!! 왜냐하면 빅오 표기법은 최악을 기준으로 삼기 때문에 가장 오래 걸리는 기준은 노드 수가 가장 많은 경우이기 때문입니다. n = 2h - 1 n + 1 = 2h log(n + 1) = h h = lo..

[자료구조] 정렬 : C언어

1. 정렬이란? : 정렬은 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것 단순하지만 비효울적인 방법 삽입정렬, 선택정렬, 버블정렬 복잡하지만 효율적인 방법 퀵정렬, 히프정렬, 합병정렬, 기수정렬 2. 선택 정렬(selection sort) #include #include #define MAX_SIZE 10 #define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) int list[MAX_SIZE]; int n; // void selection_sort(int list[], int n) { int i, j, least, temp; for (i = 0; i < n - 1; i++) { least = i; // 최소값 탐색 for (j = i + 1; j < n; ..

[자료구조] 트리_하 : C언어

1. 수식 트리 : 후위 순회를 사용 루트 노드보다 자식 노드를 먼저 방문하여 수식의 값을 계산 연산자와 피연산자로 구성 연산자(operator) : 비단말노드 피연산자(operand) : 단말노드 계산 순서는 다음과 같다. 32*56*+ ==> 36 #include typedef struct TreeNode { int data; struct TreeNode* left, * right; } TreeNode; // + // * + // 1 4 16 25 TreeNode n1 = { 1, NULL, NULL }; TreeNode n2 = { 4, NULL, NULL }; TreeNode n3 = { '*', &n1, &n2 }; TreeNode n4 = { 16, NULL, NULL }; TreeNode n..

[자료구조] 트리_상 : C언어

1. 트리의 개념 리스트, 스택, 큐 등은 선형 자료 구조(linear data structure) 선형으로 나열되어 있는 구조 트리는 계층적인 구조를 나타내는 자료구조 트리는 부모 - 자식 관계의 노드들로 이루어진다 가족의 가계도나 회사의 조직도 등 트리에서 사용되는 용어 노드(node): 트리의 구성요소 루트(root): 부모가 없는 노드(A) 서브 트리(subtree): 하나의 노드와 그 노드들의 자손들로 이루어진 트리 비말단노드: 적어도 하나의 자식을 가지는 노드(A, B, C, D) 단말 노드(terminal node): 자식이 없는 노드(E, F, G, H, I, J) 자식, 부모, 형제, 조상, 자손 노드: 인간과 동일 레벨(level): 트리의 각층의 번호 높이(height): 트리의 최대..

[Python] 파이썬 .set() 생성자 사용법

1. set은 딕셔너리와 같이 중괄호를 이용하지만 key가 없이 value만 있습니다. s = { 1, 2, 3, 4, 5 } set을 생성할때 s = set() 이런 방식의 set() 생성자를 이용하는 방법이 있습니다. 2. set은 중복되는 원소를 자동으로 제거해줍니다. s = { 1, 1, 2, 2, 3, 4, 5, 5, 6 } print(s) ==> {1, 2, 3, 4, 5, 6} 3. set의 원소 추가 .add() 메서드를 이용 s = { 5, 55, 77, 999 } s.add(40) print(s) ==> {5, 999, 40, 77, 55} set에는 정해진 순서가 없어서 어떤 원소가 먼저 출력될지 모릅니다. 4. set의 원소 제거 .remove() 메서드 사용 s = { 5, 55,..

[Python] 딕셔너리 : .keys(), .values(), .items() 메서드 사용법

.keys() : 딕셔너리의 key만 선별해주는 함수 map = { "자료구조" : 2, "알고리즘" : 3, "컴퓨터구조" : 2, "운영체제" : 3 } print(map.keys()) ==> dict_keys(['자료구조', '알고리즘', '컴퓨터구조', '운영체제']) dict_keys([~~~]) .values() : 딕셔너리의 value만 선별해주는 함수 map = { "자료구조" : 2, "알고리즘" : 3, "컴퓨터구조" : 2, "운영체제" : 3 } print(map.values()) ==> dict_values([2, 3, 2, 3]) dict_values([~~~]) .items() : 딕셔너리의 key와 value를 하나의 튜플로 묶어주는 함수 map = { "자료구조" : 2, ..