[C로 배우는 자료구조 및 여러가지 예제 실습 - 권오흠 교수님] 자료구조 강의 목록 http://alg.pknu.ac.kr/t/topic/482 [2017년 가을학기] 자료구조 및 실습 제1장 C언어 리뷰 강의자료 강의 소개 제1장 강의 슬라이드 제1주 (101분반 9/4, 9/7, 102분반 9/5. 9/8) 동영상 강의 01: 포인터, 배열과 포인터, 포인터 연산 동영상 강의 02-1: 동적메모리 할당 동영상 강 alg.pknu.ac.kr 자료구조 강의 후기 - 포인터, 배열, 연결 리스트, 스택, 큐의 개념뿐만 아니라 동작 원리와 코드를 개념을 따라 이해할 수 있게 되었다. - 함께 코딩하면서 개념을 복기하기 때문에 응용이 가능하다. - 가장 기초적이면서 기본적인 단계부터 강의하시기 때문에 초심자..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 정렬된 두 배열 합치기 1-1. 하나의 배열 복사 후 다른 배열 insert 정렬된 두 배열 a와 b에 저장된 m개와 n개의 데이터를 배열 c에 정렬된 상태로 저장하는 것 void merge_sorted_arrays(int m, int a[], int n, int b[], int c[]){ for(int i=0; iitem; i--) data[i+1] = data[i]; data[i+1] = item; } 첫 번째 for문에서 m 시간 소요 두 번째 for문에서 (m+1) + (m+2) + … + (m + n-1) 시간 소요 = m + nm + n(n-1)/2 = O(nm) 시간 복잡도(최악의 경우) 1-2. t..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. Stack - push and pop 1-1. 배열로 구현한 경우 void push(Stack s, Item i){ if(is_full(s)) //스택에 저장된 데이터 개수를 n이라고 하면 reallocate 함수의 시간 복잡도는 O(n) reallocate(s); //reallocate를 제외한 나머지 부분의 시간 복잡도는 O(1) s->top ++; s->contents[s->top] = i; } reallocate를 제외한 나머지 연산은 스택 안의 데이터의 개수와 무관하기 때문에 → O(1)의 시간 복잡도 일반적으로 함수의 시간 복잡도에서 reallocate는 제외 ~ 애초에 스택의 크기를 크게 잡으면 되기..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 검색 검색: 원하는 데이터가 있는지 없는지를 찾고, 있으면 어디 있는지를 찾는 것 1차원 list로 한정할 때 순차 검색(sequential Search) 는 순차적으로 하나 하나 비교하며 검색하는 것으로 O(n)의 시간 복잡도를 가진다. 배열과 연결리스트 모두에서 사용할 수 있다. 이진 검색(Binary Search) 2. 이진 검색 배열만 사용할 수 있다. 2. 이진 검색(Binary Search) 배열에 데이터들이 내림/오름차순으로 정렬되어 있어야 한다. first, last, middle=(first+last/2)로 중간값과 target의 값을 비교하여 검색 범위를 좁혀 나간다. 중앙값 < target →..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 알고리즘의 분석 구조화, 모듈화가 얼마나 잘 되었는지에 따라 프로그램의 재사용성과 리팩토링이 달라질 수 있다. 호환성 역시 마찬가지다. 하지만 이러한 기준은 정량화 되어 있지 않기 때문에 이 장에서는 정량화된 기준으로 분석을 한다. 알고리즘의 자원(resource) 사용량을 분석 실행 시간: 똑같은 시간 동안 얼마나 많은 일을 하는지 메모리: 얼마나 많은 메모리를 사용해서 일을 하는지, 과거에는 중요했지만 기술의 발전으로 중요도가 낮아짐 저장장치, 통신 등 2. 시간 복잡도(time complexity) 실행 시간은 실행환경(하드웨어, 운영체제, 언어, 컴파일러 등)에 따라 달라진다. 범용으로 실행 시간을 측정하..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 스택과 큐의 비교 2. 연결 리스트로 구현한 자료구조 2-1. 스택 연결 리스트의 맨 앞이 노드를 삽입/삭제하기에 편하다→ 맨 앞을 스택의 top으로 한다. typedef int Item; typedef struct stack_type *Stack; struct node{ Item data; struct node *next; } struct stack_type{ struct node *top; } //스택의 생성 Stack create(){ Stack s = malloc(sizeof(struct stack_type)); s->top = NULL; return s; } //삽입 void push(Stack s, I..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 미로 찾기 DFS(Depth First Search: 깊이 우선 탐색) - recursion, stack 더 이상 갈 곳이 없을 때까지 갔다가 다시 되돌아 나와서 진행 BFS(Breath First Search: 너비 우선 탐색) - queue 출발점에서 한 칸 떨어진 지점을 탐색 출발점에서 두 칸 떨어진 지점을 탐색 … 출발점에서 n 칸 떨어진 지점을 탐색 ~ 동심원 형태로 1-1. 너비 우선 탐색으로 미로 찾기 (1) 하나의 큐를 만든다. (2) 위치(0, 0)는 이미 방문한 위치임을 표시하고, 큐에 위치 (0,0)을 넣는다. (3) 큐가 빌 때까지 반복 (4) 큐에서 하나의 위치 p를 꺼낸다. (5) p에서..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 환형(circular) 배열 배열은 개수가 정해져 있기 때문에 인덱스가 배열의 범위를 벗어나게 되면 어떻게 되는지 배열로 구현한 큐는 front부터 rear까지 꽉 차 있어야 한다. 배열의 범위를 벗어난다고 해서 reallocate를 할 수 없는 이유 → ②처럼 빈 공간이 남아 있기 때문 ⇒ 환형 배열을 이용해서 큐를 구현할 수 있다. 2. 환형 배열을 이용한 큐 구현 queueADT_array.c // queueADT_array.c #include #include #include "queueuADT.h" #define INIT_CAPACITY 100 struct queue_type{ Item *contents;..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 큐(Queue) 큐는 일종의 리스트 일반 리스트: 아무 곳에서나 삽입/삭제 가능 스택: 삽입과 삭제가 한쪽 끝에서만 이루어짐 큐: 삽입은 한 쪽 끝에서, 삭제는 반대쪽 끝에서 일어남 삽입이 일어나는 쪽을rear, 삭제가 일어나는 쪽을 front라고 부름 FIFO(First-In, First-Out): 가장 먼저 들어간 애가 가장 먼저 나옴 2. 큐가 지원하는 연산 큐는 스택처럼 연산을 하나의 통일된 이름으로 부르지 않고, 다양한 이름으로 부른다. enqueue: 큐의 rear에 새로운 원소를 삽입하는 연산 insert, offer, push dequeue: 큐의 front에 있는 원소를 큐로부터 삭제하고 반환하는..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 자료구조 15강 스택: 삽입과 삭제가 한쪽 끝에서 이루어지는 리스트의 일종 삽입과 삭제가 일어나는 쪽을 스택의 top이라고 부름 LIFO: 가장 나중에 들어간 애가 가장 먼저 나옴 스택이 지원하는 연산 push: 스택에 새로운 원소를 삽입하는 연산 pop: 스택의 top에 있는 원소를 스택에서 제거하고 반환 peek: 스택의 top에 있는 원소를 제거하지 않고 값만 반환 → 스택은 변화 없음 is_empty: 스택이 비었는지 검사 배열을 이용한 스택의 구현 //int를 Item으로 부르겠다: 코드의 재사용성을 높이기 위해 typedef int Item; //*Stack이 가리키고 있는 장소에 있는 데이터의 타입이 st..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 미로 찾기 - 스택 2차원 NxN 배열 입구는(0, 0), 출구는 (N-1, N-1) 다음을 반복 현재 위치에 방문했다는 표시를 해서 무한 루프를 방지 현재 위치가 출구라면 종료 현재 위치에서 일정한 규칙으로 다음 위치로 이동 북→동→남→서 순서로 이동 아직 안 가본 위치이고 && 벽이 아니고 && 미로의 외부가 아니면 이동 만약 북, 동, 남, 서 어디로도 이동하지 못했다면 현재 위치에 도달하기 직전 위치로 이동한다. 만약 돌아갈 위치가 없다면 원래 길이 없는 미로 어떻게 돌아갈 것?? ⇒ 스택을 사용해서 현재 위치를 스택에 push하고 다음 위치로 이동 → 스택의 top에는 항상 직전 위치가 저장 이동할 수 ..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 후기 표기식으로 변환 - 괄호 있는 경우 여는 괄호는 무조건 스택에 push ~ 이때 스택 내의 어떤 연산자도 pop X 어떤 연산자를 스택에 push 할 때 스택의 top에 여는 괄호가 있으면 아무도 pop하지 않고 그냥 push 닫는 괄호가 나오면 스택에서 여는 괄호가 나올 때 까지 pop 해서 출력 ~ 닫는 괄호는 스택에 push X 2. 괄호가 있는 후기 표기식으로의 변환 코드 // infix_to_postfix.c #include #include "stackADT.h" struct stack_type{ Item *contents; //배열 int top; //스택의 top을 가리키는 변수 int size..