큐를 구현하는 방법은 크게 2가지가 있다. 배열을 이용하는 방법 비교적 간단하게 구현할 수 있다. 크기 제한이 있는 배열의 특성에 따라 큐의 크기가 고정되는 단점이 있다. 연결 리스트를 이용하는 방법 배열을 이용하는 방법보다는 구현이 까다롭다. 크기 제한이 없는 연결 리스트의 특성에 따라 큐의 크기도 제한이 없다. 아직 연결 리스틀 다루지 않았기 때문에 지금은 배열로 큐를 구현하고, 후에 연결 리스트를 다룬 뒤에 다시 연결 리스트로 큐를 구현해보자. 배열을 이용한 큐 선형 큐(Linear Queue) 1차원 배열을 이용한 정수를 저장하는 선형 큐를 생각해보자. 큐를 처음 생성했을 때는 큐의 앞단(front)과 뒷단(rear)을 가리키는 변수를 -1로 초기화해준다.(배열 인덱스는 0부터이기 때문) enqu..

큐란? 영어 사전에 queue를 검색해보면 "대기열"이라는 뜻으로 나온다. 큐를 생각할 때는 놀이공원의 대기열이나 맛집의 대기 번호표를 생각하면 된다. 놀이공원에서는 먼저 줄을 선 사람이 먼저 놀이기구를 탈 것이다. 맛집에서 번호표를 받고 기다릴 때는 먼저 온 사람이 빠른 대기 번호를 받고, 먼저 불려질 것이다. 즉, 먼저 온 사람이 먼저 무언가를 하게 되는 구조인 것이다. 이것이 큐의 특징인 선입선출(FIFO, First-In First-Out)이다. 큐는 가장 먼저 입력된 데이터가 먼저 삭제되는 구조를 가지고 있다. 입출력이 항상 같은 위치(스택의 최상단)에서만 일어나는 스택과 달리, 큐는 입력과 출력의 위치가 다르다. 위 그림처럼 큐에서의 입력은 후단(rear)에서 일어나고 출력은 전단(front)..

앞에서 배열을 이용해 스택을 직접 구현해보았다. 이번에는 C++에서 제공하는 표준 템플릿 라이브러리(STL)을 이용해보자. STL은 프로그래밍에서 공통적으로 사용되는 자료구조와 알고리즘에 대한 클래스이다. 템플릿을 기반으로 작성되었기 때문에 어떤 자료형(사용자 정의 자료형 포함)에도 사용할 수 있다. 스택 템플릿 stack을 사용하려면 소스 코드에 헤더파일을 포함시키면 된다. #include using namespace std; // stack 이름; stack stack_name; stack의 멤버 함수 void push (const value_type& val); void push (value_type&& val); stack 최상단에 데이터를 삽입한다. void pop(); stack 최상단의 데이..

스택을 구현하는 방법은 크게 2가지가 있다. 배열을 이용하는 방법 간단하게 구현할 수 있다. 크기 제한이 있는 배열의 특성에 따라 스택의 크기가 고정되는 단점이 있다. 연결 리스트를 이용하는 방법 배열을 이용하는 방법보다는 구현이 까다롭다. 크기 제한이 없는 연결 리스트의 특성에 따라 스택의 크기도 제한이 없다.(isFull() 연산이 필요가 없게 된다.) 아직 연결 리스트를 다루지 않았기 때문에 지금은 배열로 스택을 구현하고 , 후에 연결 리스트를 다룬 뒤에 다시 연결 리스트로 스택을 구현해보자. 배열을 이용한 스택 구현 배열을 이용해 정수(int)를 저장하는 스택을 구현해보자. 일단 정수를 저장할 1차원 배열이 필요하다. 이를 int data[MAX_STACK_SIZE] 라고 하자. (MAX_STAC..

스택(Stack)이란? 영어 사전에 stack을 검색해보면 "(깔끔하게 정돈된) 더미" 혹은 "(깔끔하게 정돈해) 쌓다"의 의미라고 나온다. 이것이 스택이다. 말 그대로 쌓아져 있는 형태를 갖는 자료구조이다. 쌓아져 있는 접시나 상자를 생각하면 스택을 쉽게 이해할 수 있다. 아래 쪽에 있는 접시나 상자를 꺼내고 싶다면 먼저 그 위에 쌓아져 있는 것들을 꺼내고 난 뒤에야 꺼낼 수 있다. 이것이 스택의 특징인 후입선출(LIFO, Last-In First-Out)이다. 스택은 가장 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조를 가지고 있다. 항상 입출력은 스택의 최상단에서만 이루어지고, 그 외의 장소에서는 데이터를 삽입하거나 삭제할 수 없다. 위 그림을 보며 스택..

ADT - Class Diagram - C++ 자료구조를 표현하기 위해 위 3가지 방법을 따를 것이다. 추상 자료형: 자료구조의 추상 자료형(ADT)를 생각해본다. 그 자료구조에서 필요한 데이터는 무엇이고 어떤 연산들을 필요로 하는가를 정의한다. UML 다이어그램: ADT로 표현된 자료구조를 문제 해결에 적용하기 위해 필요한 클래스들을 보다 구체적으로 설계하는 단계 C++ 클래스: 구체적으로 설계된 UML 다이어그램을 바탕으로 해당 자료구조를 C++ 클래스로 구현한다. UML Diagram UML(Unified Modeling Language, 통합 모델링 언어)은 소프트웨어 개발에서 시스템의 구조와 상호 작용, 컴포넌트 관계 객체 간의 메시지 전달, 업무 흐름 등을 표현하는 통합된 객체지향개발 표준 통..

빅오 표기법 일반적으로 시간 복잡도 함수 T(n)은 입력의 개수 n에 대한 복잡한 수식으로 나타낼 수 있다. 그런데 이 T(n)식은 n이 커질수록 최고차항의 영향력이 절대적이 되고 다른 항들은 무시될 수 있을 정도로 작아진다. 따라서 시간 복잡도 함수에서 중요한 것은 n에 대한 연산이 몇 번인가가 아니라 n이 증가함에 따라 무엇에 비례하는 수의 연산이 필요한가이다. 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법이라고 한다. 어떤 알고리즘이 n에 비례하는 실행 시간을 가진다(시간 복잡도 함수에서 최고 차항이 n)고 말하는 대신 시간 복잡도가 O(n)이라고 하는 방식이다. (빅오 of n이라고 읽음) 빅오 표기법은 n에 따른 함수의..

요즘 컴퓨터는 엄청난 계산 속도와 큰 용량의 메모리를 갖고 있다. 그렇다면 프로그램 작성 시에 계산 시간을 줄이고 메모리를 효과적으로 사용하기 위한 고민은 필요 없을까? 전혀 그렇지 않다. 컴퓨터의 성능이 좋아진 만큼 컴퓨터 프로그램이 다루는 자료의 양을 엄청나게 늘어났고 프로그램의 규모도 커졌다. 입력 자료의 개수 프로그램 A : n^2 프로그램 B : 2^n n = 6 36초 64초 n = 100 10000초 2^100초(4*10^22)년 자료의 크기가 작을 때는 두 프로그램의 성능이 크게 차이나지 않지만, 자료의 크기가 커지면 두 프로그램의 성능 차이는 극명하게 벌어진다. 프로그램의 성능에 대해 고민해야 하는 또 다른 이유는 사용자들은 여전히 빠른 프로그램을 선호하기 때문이다. 경쟁 프로그램보다 성..