Computer Science/Data structures

큐의 구현 큐는 두가지 방법을 통해서 구현할 수 있다 배열을 활용하여 선형 형태로 큐를 구현하는 것. 배열을 활용하여 원형 형태로 큐를 구현하는 것 선형 큐 다음처럼 선형 큐는 일반 선형 배열 형태로 구현한다. Front 와 Rear를 통해 큐의 맨 앞과 뒤를 표시한다. 초기상태의 표시를 위해 front와 rear는 -1로 시작한다. Front위치에는 아무것도 저장하지 않는다 공백 상태 : Front = Rear 포화 상태 : Rear = Max_index 선형 큐의 문제는 dequeue를 통해 요소를 큐에서 제거함에도 불구하고 배열 크기만큼의 데이터만 저장할 수 있다는 점에 있다. 즉, 아무리 dequeue연산을 통해서 요소를 제거해도 이미 이전에 5개의 요소를 저장한 바가 있다면 더 이상 해당 큐를 ..

큐 먼저 들어온 데이터가 먼저 나가는 형태의 자료구조를 말한다. 이를 선입선출(FIFO)이라고 한다. 큐의 가장 대표적인 예시는 매표소에서의 대기열을 들 수 있다. 먼저 대기줄에 들어온 사람이 먼저 나가게 되므로 이는 큐를 이해하기 적절한 예시이다. ADT 객체 : 0개 이상의 요소들로 구성된 선형 리스트 연산 : create(max_size) ::= 최대 크기가 max_size인 공백 큐를 생성한다. init(q) ::= 큐를 초기화 한다. is_empty(q) ::= size == 0이면 true 반환 is_full ::= size == max_size이면 true 반환 peek(q) ::= 큐의 가장 앞의 요소 값을 반환한다. enqueue(q, e) ::= 큐의 가장 뒤에 요소 e를 추가한다 de..

Queue & Deque 이번 챕터에서는 큐와 덱에 대해서 알아본다. 이전에 알아보았던 스택까지 합쳐서 스택, 큐, 덱에 대한 아주 간단한 아이디어는 다음과 같다. Stack 후입 선출 LIFO 예) 접시 쌓기 Queue 선입 선출 FIFO 예) 줄서기 Deque Double ended queue 즉, 앞과 뒤 말단에서 삽입,삭제 이루어짐. 이번 챕터에서 다루게 될 내용은 다음과 같다. 큐 선형 큐 원형 큐 예시) 버퍼 덱 선형 원형

Stack이름에서 알 수 있듯이 후입선출하는 형태의 자료구조. 접시를 쌓아서 보관하는 것을 예로 들 수 있다. ADT객체 : 0개 이상의 원소를 가지는 유한한 길이의 선형 리스트연산 : create(size) ::= 최대 크기 size인 스택 생성is_full(s) ::= 스택의 모든 자리에 원소가 차있다면 true 반환is_empty(s) ::= 스택이 모두 비어 있다면 true반환push(s,item) ::= s스택에 item원소 추가pop(s) ::= s스택의 가장 위 원소를 반환하고 제거한다.peek(s) ::= s스택의 가장 위 원소를 반환한다.

Stack이번 챕터에서는 스택에 대해서 다룬다. 스택, ADT배열 구현구조체 활용동적 할당 활용괄호 검사수식 표기(전위, 중위, 후위)수식 변환미로탐색

구조체구조체는 타입이 다른 데이터를 하나로 묶는 방법이다.배열은 타입이 같은 데이터를 하나로 묶는다. 구조체는 각 요소를 멤버(필드)라고 하고, 멤버 변수의 이름으로 접근한다.배열은 각 요소를 인덱스로 접근한다. 선언선언은 struct 키워드를 통해서 다음과 같이 한다.접근은 맴버 변수의 이름을 통해 접근한다. TypedefC언어에서 typedef 키워드는 기존 타입에 새로운 이름을 붙일 때 사용한다.구조체 변수를 선언할 때 매번 앞에 struct를 작성해야한다는 번거로움이 있으므로 typedef를 통해 코드를 한 단어라도 줄여볼 수 있다.

배열배열은 같은 타입의 변수 여러개 만드는 경우에 사용한다.ADT객체 : 쌍의 집합연산 : create(size) ::= size개의 요소를 저장할 수 있는 배열 생성get(A, i) ::= 배열 A의 i번째 요소 반환set (A, i, v) ::= 배열 A의 i번째 위치에 v값 저장

배열 구조체,포인터 앞으로 배우게 될 자료구조를 학습하는데 있어서 기본이 되는 배열, 구조체, 포인터와 관련 알고리즘에 대해서 배워보도록 한다. 문법에 대한 이야기는 대부분 생략하고 작성한다. 배열 구조체 다항식 표현 희소행렬 포인터 동적 할당 구조체와 포인터

피보나치 수열피보나치 수열의 경우에는 순환 호출을 사용하면 비효율적인 예시이다. 피보나치 수열은 다음과 같이 공식으로 표현한다. 구현과 성능순환 호출과 반복문을 각각 활용하여 피보나치 수열의 값을 계산하는 함수를 구현하자.구현을 통해서 왜 피보나치 수열에서 순환 방식이 반복보다 비효율적인지 알아본다.순환종료 조건 : n이 1이나 0인 경우fib(n)=fib(n-1)+fib(n-2)로 순환 호출하여 계산한다.순환호출로 함수를 구현하면 사실 알아보기 쉽고 간단해 보인다.그러나 외연과 달리 효율성은 저멀리로 :D 날아간 코드라고 할 수 있겠다. 먼저 이 함수를 살펴보면, 함수 내에서 비교연산을 한번 수행하고, 이후 2개의 fib함수를 호출하여 연산한다. 따라서 n을 처음 넣었을 때, fib함수 호출을 몇번 하..