johyeongseob 님의 블로그

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 6.1 리스트 추상 데이터 타입리스트의 소개 리스트(list)는 우리들이 자료를 정리하는 방법 중의 하나이다. 리스트에는 항목들이 차례대로 저장되어 있다. 리스트의 항목들은 순서 또는 위치를 가진다. 리스트는 집합하고는 다르다. 집합은 각 항목 간에 순서의 개념이 없다.L = [item(0), item(1), item(2), ... , item(n-1)]리스트는 다음과 같은 기본적인 연산들을 생각할 수 있다.리스트에 새로운 항목을 추가한다(삽입 연산).리스트에서 항목을 삭제한다.(삭제 연산).리스트에서 특정한 항목을 찾는다(탐색 연산). 6.3 연결 리스트 이번 절에서 연결된 표현(linked representation)에 대하여 ..

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 5.1 큐 추상 데이터 타입 큐(queue)는 먼저 들어온 데이터가 먼저 나가는 다시 말해, 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조로 이러한 특성을 선입선출(FIFO: First-In First-Out)이라고 한다. 큐에서 삽입이 일어나는 곳을 후단(rear)라고 하고 삭제가 일어나는 곳을 전단(front)라고 한다. 큐에서 가장 중요한 연산은 삽입과 삭제 연산인 enqueue와 dequeue이다. enqueue 연산은 큐에 요소를 추가하는 연산으로서 큐의 맨 뒤에 새로운 요소를 추가한다. dequeue 연산은 큐의 맨 앞에 있는 요소를 꺼내서 외부로 반환한다. 큐의 응용으로 예를 달면 운영 체제에는 ..

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 4.1 스택이란?  스택이란 '(건초, 밀집 따위를 쌓아놓은) 더미, 낟가리'를 의미한다. 식당에 쌓여있는 접시 더미, 책상에 쌓여있는 책, 창고에 쌓여있는 상자 등이 스택의 전형적인 예이다. 스택에서 가장 최근에 들어온 것이 가장 위에 있게 되고, 또 먼저 나가게 된다. 이런 입출력 형태를 후입선출(LIFO: Last-In First-Out0이라고 한다. 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 스택에서 입출력이 이루어지는 부분을 스택 상단(Stack top)이라 하고 반대쪽인 바닥 부분을 스택 하단(stack bottom)이라고 한다. 스택에 저장되는 것을 요소(element)라 부른..

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 3.1 배열  배열은 동일한 타입의 데이터를 한 번에 여러 개 만들 때 사용된다. 대량의 데이터를 저장하기 위하여 배열을 사용하면 "연속적인 메모리 공간"이 할당되고 인덱스(index) 번호를 사용하여 쉽게 접근이 가능하기 때문에 반복 루프를 이용하여 여러 가지 작업을 손쉽게 할 수 있다. 배열 ADT  배열은 의 쌍의로 이루어진 집합으로 정의할 수 있다. 즉 인덱스(index)가 주어지면 해당하는 값(value)이 대응되는 자료 구조이다. 수학적으로 배열은 인덱스에서 값의로의 사상(mapping)에 해당된다.3.2 구조체구조체의 개념 복잡한 객체어는 다양한 타입의 데이터들이 한데 묶여져서 있다. 배열이 타입이 같은 데이터의 모임이..

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 2.1 순환의 소개 순환(recursion)이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 순환은 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다. 순환 호출의 내부적인 구현  순환을 이해하기 위하여 먼저 함수 호출의 과정을 살펴보자. 프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출하는 것은 다름 함수를 호출하는 것과 동일하다. 즉 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수(parameter)와 지역 변수를 스택으로부터 할당받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드(activation record)라고 한다. 순환 ..

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 1.1 자료구조와 알고리즘자료구조란?  사람들이 사물을 정리하여 저장하는 것과 마찬가지로 프로그램에서도 자료들을 정리하여 보관하는 여러 가지 구조들이 있다. 이를 자료 구조(data structure)라 부른다. 알고리즘이란?   컴퓨터로 문제를 풀기 위한 단계적인 절차를 알고리즘(algorithm)이라고 한다. 엄밀하게 이야기하면 알고리즘이란 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것이다. 따라서 알고리즘은 특정한 일을 수행하는 명령어들의 집합이다. 입   력: 0개 이상의 입력이 존재하여야 한다.출   력: 1개 이상의 출력이 존재하여야 한다.명백성: 각 명렁어의 의..