분류 전체보기
-
[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에 있는 원소..
-
[C언어/자료구조] 연결리스트 - 다항식CS/자료구조&알고리즘 2020. 1. 19. 18:21
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 다항식이란 ? 1원다항식(일변수 다항식) : 변수가 하나인 다항식 단항식 : 하나의 항으로 이루어진 식 다항식/n항식 : 여러 개의 항으로 이루어진 식/n개의 항으로 이루어진 다항식 상수항 : 변수를 포함하지 않는 항 계수 : 변수의 거듭제곱에 곱하는 수 ( x2 - 2x + 3의 세 항의 계수는 각각 1, -2, 3 ) 차수 : 변수를 거듭제곱한 지수 ( x2의 차수는 2 ) 동류항 : 차수가 같은 항 ( x2 + 3x - x + 3에서 3x와 -x는 동류항 ) 동류항이 있는 다항식 : 정리되지 않은 다항식으로, 계수를 더해 동류항들을 하나의 항으로 만들어야 한다. ( x2 + 3x - x + 3 ..
-
[C언어/자료구조] 연결리스트(Linked list) 기본 연산 예제 (인프런)CS/자료구조&알고리즘 2020. 1. 17. 20:44
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 연결리스트 만들기 / 출력하기 연결리스트를 사용하기 위해서는 먼저 하나의 node를 담을 구조체를 선언해야한다. struct node { char *data; /*데이터 필드 : 하나의 문자열 저장 */ struct node *next; /*링크 필드 : 다음 노드의 주소 저장 */ } typedef struct node Node; Node *head = NULL; /* 첫 번째 노드의 주소를 저장할 포인터 */ Node라는 이름의 구조체를 선언하고, 첫번째 노드의 주소를 따로 보관할 수 있는 포인터 변수도 선언했다. 이제 세 개의 노드로 구성된 연결리스트를 만들고 출력하는 코드를 작성할 것이다. i..
-
[C언어/자료구조] 연결리스트(Linked list) 개념 (인프런)CS/자료구조&알고리즘 2020. 1. 16. 15:23
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. List와 Set List (리스트) 순서 O (1, 2, 3) =/= (3, 2, 1) Set (집합) 순서 X {1, 2, 3} = {3, 2, 1} 리스트 (List) 리스트를 구현하는 대표적인 두 가지 방법은 배열, 연결리스트가 있다. 삽입(insert), 삭제(remove), 검색(search) 등 기본적인 연산이 가능하다. 배열 vs 연결리스트 배열 크기가 고정되어있어 reallocation이 필요하다. 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 한다. 랜덤 액세스 가능. 연결리스트 길이 제한 x 다른 데이터의 이동없이 중간에 삽입이나 삭제 가능. 랜덤 액세스 불..
-
[C언어/자료구조] 전화번호부 v5.0 (인프런)CS/자료구조&알고리즘 2020. 1. 14. 07:00
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다. 전화번호부 v5.0의 개선사항 https://skm1104.tistory.com/29 전화번호부 v1.0 https://skm1104.tistory.com/30 전화번호부 v2.0 https://skm1104.tistory.com/31 전화번호부 v3.0 https://skm1104.tistory.com/32 전화번호부 v4.0 v4.0에서부터 구조체 배열을 만들어 데이터를 담는 데 사용했다. 그런데 C 프로그래밍에서 구조체 배열을 만들어 사용하는 것은 일반적인 경우는 아니다. 구조체의 크기가 클 경우 비효율적일 수 있기 때문이다. C언어에서는 함수를 호출할 때 매개변수의 전달방식이 call-by-v..