CS/자료구조&알고리즘
-
[자료구조(C언어)] 정렬 2 - 삽입 정렬 (insert sort)CS/자료구조&알고리즘 2020. 1. 30. 18:54
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 삽입 정렬 (insert sort) 하나의 배열에 데이터들이 이미 정렬되어있을 때, 정렬을 유지하면서 새로운 데이터를 삽입하는 알고리즘이다. 새로운 데이터를 정렬된 배열의 앞에 있는 데이터부터 차례대로 비교하면서 자신의 위치를 찾아 삽입한다. 이러한 삽입 연산을 반복적으로 수행함으로써 데이터들을 정렬한다. 오름차순 삽입 정렬 코드 void insertion_sort(int n, int data[]) { for (int i=1; i=0 && data[j]>tmp) { /* tmp보다 큰 값들을 뒤로 한 칸씩 옮긴다. */ data[j+1] = data[j]; j-; } /* tmp보다 작은 값을 발견하..
-
[자료구조(C언어)] 정렬 1 - 버블 정렬 (bubble sort)CS/자료구조&알고리즘 2020. 1. 30. 18:47
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 버블 정렬 배열에서 서로 인접한 두 원소를 검사하여 큰 값을 뒤로 보낸다. 이것을 배열의 끝에 도달할 때까지 반복하면 인덱스 0 ~ n-1까지의 원소들 중에서 가장 큰 값(/작은 값)을 맨 뒤(n-1)로 보내게 된다. (n-1은 다음 정렬에서 제외된다. 정렬이 수행될 때마다 제외되는 원소가 뒤에서부터 하나씩 늘어난다. ) ↓ 같은 방법으로 0~ n-2까지의 원소들 중에서 가장 큰 값을 n-2로 보내기 (n-2가 정렬에서 제외됨) 0~ n-3까지의 원소들 중에서 가장 큰 값을 n-3으로 보내기 (n-3이 정렬에서 제외됨) ... 0~1까지의 원소들 중에서 큰 값을 1로 보내기 위와 같은 과정을 거쳐 오..
-
[자료구조(C언어] 배열로 큐(Queue) 구현하기CS/자료구조&알고리즘 2020. 1. 30. 16:58
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 환형 배열로 큐 구현하기 큐의 경우 배열보다는 연결리스트로 구현하는 것이 좀 더 간단한데, 배열은 크기가 정해져있기 때문이다. 환형 배열(Circular array)을 이용해 큐를 구현하면 배열의 끝에 도달할 때마다 재할당을 해서 크기를 늘리지 않아도 된다. 배열의 앞에서부터 순서대로 데이터들을 저장한다. 데이터를 삭제하게 되면, 먼저 저장한 데이터부터(앞에서부터) 지워나간다. 이렇게 해서 배열의 앞에는 공간이 있고, 배열의 끝에는 데이터가 저장되어있는 상태에서 새로운 원소를 또 추가한다면, 다시 배열의 첫번째 칸에서부터 추가한다. 이와 같이 원형으로 순환하며 데이터를 저장한다. 헤더 파일은 연결리스..
-
[자료구조(C언어] 연결리스트로 큐(Queue) 구현하기CS/자료구조&알고리즘 2020. 1. 30. 07:00
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 단방향 연결리스트로 큐 구현하기 연결리스트의 맨 앞에서는 삽입과 삭제가 모두 어렵지 않다. 그러나 연결리스트의 맨 뒤에서는, 삽입은 괜찮지만 삭제를 하기가 어렵다. 단방향 연결리스트에서 어떤 노드를 삭제하기 위해서는 이전 노드의 주소를 알아야하기 때문이다. 따라서 연결리스트의 뒤쪽을 삽입이 일어나는 rear로, 앞쪽을 삭제가 일어나는 front로 하는 것이 유리하다. 삽입을 하기 위해서는 마지막 노드의 주소를 항상 기억해야 하므로, 연결리스트 포인터 구조체에 첫번째 노드의 주소를 저장하는 front변수(=head) 외에도 rear 변수를 따로 둬서 마지막 노드 주소를 저장하는 데 사용한다. 헤더파일 ..
-
[자료구조(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