Computer Science/Data Structure and Algorithm
-
Stack, Queue, Deque ( 스택, 큐, 덱 )Computer Science/Data Structure and Algorithm 2020. 4. 2. 10:20
✔️ Stack ( 스택 ) ◾ 먼저 들어간 데이터가 나중에 나오는 자료구조 ◾ LIFO ( Last-In, First-Out ) ◾ 후입선출 ( 後入先出 ) ⏱️ 시간복잡도 ◾ Push : O(1) ◾ Pop : O(1) 💾 소스 코드 더보기 #include #include #define STACK_SIZE 100 int stack[STACK_SIZE]; int top = -1; void push(int item) { if (top >= STACK_SIZE - 1) { printf("Stack is Full.\n"); return; } stack[++top] = item; } int pop() { if (top == -1) { printf("Stack is Empty.\n"); return 0; } r..
-
Array, Linked List ( 배열, 연결리스트 )Computer Science/Data Structure and Algorithm 2020. 4. 2. 10:19
✔️Array ( 배열 ) ◾ 논리적인 순서와 물리적인 순서가 같기 때문에 데이터에 엑세스 하기쉽다. (인덱스로 쉽게 탐색 가능) ◾ 삽입, 삭제 연산 후에 연속적인 물리적 순서를 유지하기 위해 나머지 원소들을 이동 시키는 오버헤드가 발생한다. ⏱️ 시간복잡도 ◾ 탐색 : index를 통해 O(1)에 해당 원소로 접근 가능 ◾ 삽입 : 원소를 삽입하려면 배열내의 원소를을 shift 해줘야한다. O(n) 시간 ◾ 삭제 : 삭제한 원소보다 큰 index를 갖는 배열내의 원소들을 shift 해줘야한다. O(n) 시간 💾 소스 코드 더보기 #include int main() { int arr[10] = { 0,1,2,3,4,5,6,7,8,9 }; for (int i = 0; i < 10; i++) { print..
-
Big-O (시간 복잡도, 공간 복잡도)Computer Science/Data Structure and Algorithm 2020. 4. 2. 10:17
✔️ 개요 ◾ 우리는 잘 동작하는 알고리즘은 물론이거니와 좋은 성능의 알고리즘을 설계 해야한다. 따라서 우리는 자료구조와 알고리즘을 분석하고 평가할 수 있어야 한다. ◾ 알고리즘을 평가하는 요소는 두 가지 요소는 '속도'와 '메모리 사용량'이다. ◾ '속도'에 해당하는 알고리즘의 수행시간 분석결과를 가리켜 '시간 복잡도(time complexity)라고 한다. ◾ '메모리 사용량'에 대한 분석결과를 가리켜 '공간 복잡도(space complexity)'라고 한다. ◾ 일반적으로는 알고리즘을 평가할 때 메모리 사용량보다 실행속도에 초점을 둔다. ◾ 우리는 '속도'를 측정하기 위해 알고리즘의 연산 횟수를 센다. 그리고 처리해야할 데이터의 수 n에 대한 연산횟수의 함수를 구성한다. ◾ Big-O는 '데이터 수..
-
Divide and Conquer ( 분할 정복 )Computer Science/Data Structure and Algorithm 2020. 4. 2. 00:56
✔️ 분할 정복 ◾ 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산하는 알고리즘 기법 ◾ 분할 정복은 대개 아래와 같이 3가지의 구성요소를 가지고 있다. ◾ 문제를 더 작은 문제로 분할하는 과정(Divide) ◾ 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(Merge) ◾ 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(Base Case) ✔️ Binary Seach(이분 탐색) ◾ 정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘 ⏱️ 시간 복잡도 ◾ 탐색 : 리스트의 크기가 N일때 O(logN)의 시간이 걸린다. 💾 소스 코드 더보기 int binarySear..
-
Hash Table ( 해쉬 테이블 )Computer Science/Data Structure and Algorithm 2020. 4. 1. 13:31
✔️ 테이블 자료구조 ◾ 저장되는 데이터는 키(key)와 값(value)이 하나의 쌍을 이룬다. ◾ 키(key)가 존재하지 않는 값은 저장할 수 없다. ◾ 모든 키(key)는 중복되지 않는다. ◾ 테이블 자료구조는 사전구조 혹은 맵(map)이라 불리기도 한다. ✔️ 해쉬 함수와 충돌💥 ◾ 해쉬 함수는 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 한다. ◾ 위 그림의 f(x)는 mod 100 연산을 하는 함수이다. 위 해쉬 함수를 사용하여 8자리의 키를 2자리의 키로 바꾸었다. ◾ 위 그림에서 보이듯이 서로 다른 두 개의 키가 해쉬 함수를 통과했는데, 그 결과가 03으로 동일하다. 이러한 상황을 가리켜 충돌(Collision)이라고 한다. ✔️ 좋은 해쉬 함수의 조건 ◾ 위 그림은 테이블의 메모리 ..