CS
-
[자료구조(C언어] 스택(Stack) 구현하기 2CS/자료구조&알고리즘 2020. 1. 29. 22:44
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 해결 1 스택이 동시에 2개 이상 필요한 경우, 하나의 함수를 여러 개의 스택에 공통으로 사용할 수 있도록 함수를 작성한다 → 스택을 매개변수로 넘겨 처리한다 1) 배열로 구현 stackADT.h (헤더파일) #ifndef STACKADT_H #define STACKADT_H #include /* C99 only */ typedef int Item; typedef struct stack_type *Stack; Stack create(); void destroy(Stack s); void make_empty(Stack s); bool is_empty(Stack s); void push(Stack s, ..
-
[자료구조(C언어)] 스택(Stack) 구현하기 1CS/자료구조&알고리즘 2020. 1. 29. 22:40
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 스택 구현하기 1) 배열을 이용한 구현 stack.c #include "stack.h" #define MAX_CAPACITY 100 char stack[MAX_CAPACITY]; int top = -1; // index of the top element void push(char ch) { if (is_full()) return; top++; stack[top] = ch; } void pop() { char tmp = stack[top]; top--; return tmp; } char peek() { return stack[top]; } int is_empty() { return top == -1; ..
-
[자료구조(C언어)] 이진검색CS/자료구조&알고리즘 2020. 1. 29. 22:31
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 많은 프로그램에서 가장 높은 빈도로 수행되는 알고리즘으로 이진검색과 정렬을 꼽을 수 있다. 이진검색 순차검색은 입력데이터가 배열이나 연결리스트 등일 때 실행할 수 있고, 앞에서부터 순차적으로 검색하는 것이다. 최악의 경우 시간복잡도는 O(n)이다. 이진검색(Binary Search)은 정렬된 배열에 대해서만 실행할 수 있다. (연결리스트에서는 이진검색을 할 수 없다. 가운데 데이터를 O(1)시간에 읽을 수 없기 때문이다.) 예를 들어 배열에 데이터들이 오름차순으로 정렬되어 저장되어 있을 때, 배열의 가운데에 있는 데이터를 내가 찾는 데이터와 비교한다. 가운데 데이터가 내가 찾는 데이터보다 작다면 뒤쪽..
-
[자료구조(C언어)] 점근적 분석의 예시CS/자료구조&알고리즘 2020. 1. 29. 22:28
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 점근적 분석의 예시 1) 상수 시간복잡도 int sample(int data[], int n) { /* 아래의 연산은 n의 크기에 관계없이 1번만 실행된다. */ int k = n/2; return data[k]; } 입력 데이터의 크기에 관계없이(n에 관계없이) 일정한 시간, 상수 시간이 소요된다. 이 경우 알고리즘의 시간복잡도는 O(1)이다. 2) 선형 시간복잡도 int sum(int data[], int n) { int sum = 0; for (int i=0; i
-
[C언어/자료구조] 시간복잡도와 점근적 분석의 개념CS/자료구조&알고리즘 2020. 1. 29. 22:25
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 시간복잡도 (time complexity) 단순 실행 시간을 분석하지는 않는다. 실행 시간은 실행환경에 따라 달라지기 때문이다. (하드웨어, 운영체제, 언어, 컴파일러 등) 실행 시간을 측정하는 대신에 연산의 실행 횟수를 카운트한다. 입력 데이터의 크기가 커지면 연산의 실행횟수도 커지므로 연산의 실행횟수를 입력 데이터의 크기에 관한 함수로 표현한다. 또한 데이터의 크기가 같더라도 실제 데이터에 따라 연산의 실행횟수가 달라질 수 있다. 따라서 평균 시간복잡도를 분석하거나 최악의 경우 시간복잡도를 분석한다. 평균 시간복잡도(average-case analysis)는 알고리즘이 복잡해질수록 구하기가 굉장히..
-
[C언어/자료구조] 스택(Stack)의 개념CS/자료구조&알고리즘 2020. 1. 29. 22:21
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 리스트 vs 스택 리스트(List) 배열 연결리스트 리스트에서 데이터의 삽입/삭제는 어느 위치에서든 할 수 있다(자유롭다) 스택(Stack) 일종의 리스트이지만, 데이터의 삽입/삭제를 한 쪽 끝에서만 할 수 있다(LIFO, Last-In First-Out). 삽입/삭제가 일어나는 쪽을 스택의 top이라고 부른다. 스택의 연산 push : 스택에 새로운 원소 삽입 pop : 스택의 top에 있는 원소 제거하고 반환 peek : 스택 top 원소를 제거하지 않고 반환 empty : 스택이 비었는지 검사 (예외처리를 위해서) 스택의 응용 예 - 괄호 검사 문제 여는 괄호의 개수 = 닫는 괄호의 개수더라도,..
-
[C언어/자료구조] 이중 연결리스트(double linked list)CS/자료구조&알고리즘 2020. 1. 29. 22:17
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 단방향 연결리스트(single linked list) 각 노드가 다음 노드의 주소만를 가지고 있음. 새로운 노드를 삽입하거나 삭제하려면 반드시 이전 노드의 주소가 필요함. 연결리스트의 첫번째 노드 주소를 담을 포인터(head)가 필요함 한쪽방향으로의 순회(traverse)만 가능하다. 이중/양방향 연결리스트(double linked list) 각 노드가 이전 노드의 주소(prev)와 다음 노드의 주소(next)를 모두 가지고 있음. 연결리스트의 첫번째 노드 주소를 담을 포인터(head)와 마지막 노드 주소를 담을 포인터(tail) 두 가지가 필요함. 양방향으로 순회(traverse)가 가능하다. st..
-
[자료구조] 큐(Queue)의 개념CS/자료구조&알고리즘 2020. 1. 25. 20:56
큐(Queue) 스택과 마찬가지로 일종의 리스트로, 대기 행렬(줄)과 같은 형태의 리스트이다. 데이터의 삽입은 한쪽 끝에서(줄의 맨 끝), 삭제는 반대쪽 끝(줄의 맨 앞)에서만 일어난다.큐에서 삽입이 일어난 쪽을 rear, 삭제가 일어나는 쪽을 front라고 부른다. *rear : 뒤쪽, 뒤쪽의 FIFO(First-In, First-Out)라고도 많이 부른다. 큐는 스택보다 자주 사용되는 자료구조이다. 여러 개의 프로그램이나 프로세스 등이 하나의 공유 자원을 사용하기 위해 대기하는 상황에서 큐를 주로 사용한다. (ex : 프린터 큐) 큐의 연산 - 큐의 rear에 새로운 원소를 삽입하는 연산 : insert, enqueue, offer(java), push(C++ STL) - 큐의 front에 있는 원소..