[Computer Science]

[Algorithm] 유클리드 호제법(최대공약수, 최소공배수)

1. 유클리드 호제법 : 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘 큰 수들의 최대공약수를 구할때 사용할 수 있습니다. 최소공배수도 응용을 거쳐 구할 수 있습니다. 2개의 자연수 a, b가 있을 때 a를 b로 나눈 나머지를 r이라 할때 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다. 단 (a > b)이어야 합니다. 과정을 b가 양수일때까지 반복하고 마지막의 a값이 최대공약수가 됩니다. def gcd(a, b): while b > 0: a, b = b, a % b return a 리턴 값 a가 최대공약수 2. 최소공배수 A와 B의 곱을 최대공약수로 나누어주면 최소공배수가 됩니다. 그래서 최소공배수를 구하기 위해선 최대공약수를 구하는 함수를 미리 만들어 놓는것이 좋습니다. A와 ..

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

이진트리란? : 모든 노드의 차수가 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): 트리의 최대..

[자료구조] 연결리스트(2) : C언어

1. 원형 연결 리스트 정의 : 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트 => 한 노드에서 다른 모든 노드로의 접근이 가능 => 원형이기 때문에 다른 노드들을 거쳐서 결국 자기자신으로 되돌아 올 수 있음 => 삭제나 삽입 시에는 항상 선행 노드를 가리키는 포인터가 필요 변형된 원형 연결 리스트 => 마지막 노드는 헤드 포인터인 헤드가 가리키고 첫번째 노드는 화살표 연산자를 이용해서 head -> link로 가리킴 => 헤드포인터가 마지막 노드를 가리키도록 구성하면 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 단순 연결 리스트에 비해 용이하다. 1. 원형 연결 리스트의 처음에 삽입 ListNode* insert_first(ListNode* head, element data) { ListN..