Song 컴퓨터공학

[C 자료구조] 큐(Queue) - 선형큐 / 원형큐 배열 구현 큐(Queue) 란? 스택의 경우, 나중에 들어온 데이터가 먼저 나가는 LIFO 구조인 반면, 큐(Queue) 는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다. 이런 특성을 FIFO (First-In First-Out) 이라고 합니다. songsite123.tistory.com 지난 포스팅에서 큐에 대해 설명하고, 선형큐와 원형큐를 배열을 사용해 구현해보았습니다. 오늘은 배열이 아닌 연결 리스트를 사용하여 큐를 구현하는 법에 대해 다뤄보겠습니다. 다시 한 번 큐에 대해 간단히 복습해보면 큐는 front 에서 dequeue ( 삭제, 꺼냄 ) 연산이 진행되고 rear 에서 enqueue ( 삽입 ) 연산이 진행되는 자료구조입니다. 연결리스..

큐(Queue) 란? 스택의 경우, 나중에 들어온 데이터가 먼저 나가는 LIFO 구조인 반면, 큐(Queue) 는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다. 이런 특성을 FIFO (First-In First-Out) 이라고 합니다. 스택은 아래 부분이 막히고 윗 부분이 뚫린 형태였다면 큐는 양쪽이 뚫린 통입니다. 스택이 맨 위에서만 데이터를 삽입하고 삭제했다면 큐는 삽입과 삭제가 다른 쪽에서 일어납니다. 양 끝의 이름을 일반적으로 front 와 rear 라고 부르며 데이터의 삽입이 일어나는 곳을 rear 라고 하고 데이터의 삭제가 이뤄지는 곳을 front 라고 합니다. 데이터 삽입을 스택에서는 push 라고 했지만 queue 에서는 enqueue 라고 합니다. 삭제 연산은 dequeue 라고 합니..

연결리스트(Linked list) 란? 구조체를 활용한 연결 리스트(Linked list using structure) 연결 리스트에 대해 알아보기 전에 이것을 왜 사용하는지 부터 알아보도록 하겠습니다. 이전에 정적 메모리... blog.naver.com 연결 리스트를 왜 배우는가에 대한 내용은 위 포스팅을 참조해주시면 됩니다. 연결 리스트(Linked List) 란 노드가 연결되어 있는 구조로 각 노드는 데이터와 포인터를 가집니다. 즉 각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식으로 데이터를 저장하는 자료구조 를 연결 리스트 라고 합니다. 맨 처음의 노드는 head 포인터가 가리키고 있으며, 다음 노드를 가리키는 포인터는 다음 노드의 데이터의 주소를 값으로 가집니다. 단순 연결리스트 (Sin..

스택(Stack)이란? 스택(Stack)은 자료구조의 한 종류입니다. 두 개의 포인터로 많은 양의 데이터를 관리하는 이론? 구조? 이죠. 자료구조 중에서 '선형구조'에 해당하는 자료구조인데요, 어려울 거 없이 프링글스를 생각하시면 됩니다. 자료 구조 설명하는데 왜 뜬금없는 과자가 나오나 싶지만, 이 구조가 스택 구조와 매우 유사합니다. 우리가 프링글스를 먹을 때 맨 아래 프링글스나 중간 프링글스를 먼저 먹을 수 있나요? 아니죠. 위에서 순서대로 먹어야만 합니다. 그리고 아래에는 구멍이 안 뚫려있고, 위에만 구멍이 뚫려 있는 구조입니다. 위에는 뚫려있고, 위에서 부터 가져올 수 있으며 반대로는 뺄수없는 형태를 스택구조 라고 합니다. 이를 FILO(First In Last Out), 혹은 LIFO(Last ..

STL(Standard Template Library) 는 C++ 에서 가장 자주 사용되는 라이브러리 중 하나입니다. PS (Problem Solving)을 공부하기 전에 필수적으로 익혀야 하는 라이브러리입니다. 문제를 푸는데 필요한 알고리즘들을 빠르게 구현할 수 있기 때문입니다. 자료구조에서 배우는 스택, 큐, 트리, 등등을 일일히 구현하고 문제를 푸는 것도 중요하지만 매번 그럴 수가 없기 때문에 STL을 활용해서 문제를 해결하는 것도 중요한 것이죠. STL은 크게 4가지 ( container, iterator, algorithm, functor ) 로 나뉩니다. PS에서 중점적으로 볼 부분은 자료구조라고 할 수 있는 컨테이너(container) 와 각 컨테이너를 다룰 수 있는 여러 함수들이 구현되어 ..

C++ 이 가지는 특징 중 하나로 일반화 프로그래밍(Generic programming) 을 들 수 있습니다. 일반화 프로그래밍이란 쉽게 말하자면 일반적인, 다양한 상황에서도 같은 코드로 적용할 수 있는 것을 말합니다. C++ 에서 일반화 프로그래밍을 할 수 있는 대표적인 기능 중 하나가 바로 템플릿(Template) 입니다. 말로는 무슨 소리인지 이해가 잘 안가죠. 간단한 예를 들어보겠습니다. #include #include int max(int a, int b) { if (a > b) return (a); else return(b); } float max(float a, float b) { if (a > b) return (a); else return(b); } int main(void) { int ..

포스팅의 목차 / 링크 1. 생성자 (Constructor) 2. 디폴트 생성자 (Default Constructr) 3. 복사 생성자 (Copy Constructor) 4. 소멸자 (Destructor) 5. 생성자/소멸자 실행 순서 클래스를 통해 객체를 생성하면, 해당 객체는 그 즉시 메모리에 생성됩니다. 그러나 이 객체는 모든 멤버 변수를 초기화 하기 전에는 사용할 수 없습니다. 객체의 멤버 변수는 사용자나 프로그램이 일반적인 초기화 방식으로 초기화 할 수 없는데요, 그 이유는 객체의 멤버 중 private 멤버가 있는 경우 이런 멤버에 직접 접근할 수 없기 때문입니다. 따라서 private 멤버에 접근할 수 있는 초기화 만을 위한 public 함수가 필요한데, 이런 초기화 함수는 객체가 생성된 후..

클래스란 C++ 에서 지원하는 문법으로, 구조체의 상위 호환으로 생각할 수 있습니다. 구조체는 서로 다른 타입의 변수들을 묶어서 하나의 자료형으로 정의할 수 있었습니다. 클래스는 멤버로 함수를 포함할 수 있기 때문에 C 언어의 구조체보다 더 확장된 의미를 가집니다. 클래스의 멤버 변수를 property, 멤버 함수를 메소드(method) 라고 합니다. C++ 에서는 이러한 클래스를 가지고 객체 지향 프로그램을 작성할 수 있습니다. 객체 지향 프로그래밍(OOP, Object-Oriented Programming) C++ 은 객체 지향 프로그래밍 언어다. 이런 말을 모두 들어보고 C++ 공부를 시작하셨겠죠? 객체 지향 프로그래밍에서는 모든 데이터를 객체(object)로 취급하며, 객체가 프로그래밍의 중심이 ..

함수 오버로딩(Function overloading)은 같은 이름의 함수를 중복하여 정의하는 것을 말합니다. 이러한 것을 굳이 왜 사용하느냐, C++ 에서 새로 추가된 함수 오버로딩은 여러 함수를 하나의 이름으로 연결해줍니다. 즉, 함수 오버로딩이란 같은 일을 처리하는 함수를 매개변수의 형식을 조금씩 달리하여 하나의 이름으로 작성할 수 있도록 해주는 것입니다. 이런 함수 오버로딩은 객체 지향 프로그래밍의 특성 중 다형성(polymorphism)의 구현입니다. 함수 시그니처(Function signature) 함수 시그니처란, 함수의 원형에 명시되는 매개변수 리스트 를 뜻합니다. 함수 오버로딩의 핵심이라고도 할 수 있습니다. 만약 두 함수가 매개변수의 개수와 그 타입이 모두 같다면, 이 두 함수의 시그니처..

문자열(string) 이란 메모리에 저장된 일련의 연속된 문자들의 집합을 의미합니다. C++ 에서는 2가지 방법으로 문자열을 생성할 수 있습니다. 1. C와 동일한 방식 (배열) 2. string 클래스를 이용한 문자열 먼저 C와 동일한 방식으로 문자열을 간단히 만들어보고, 왜 string 클래스를 써야 하는가에 대해 알아봅시다. C와 동일한 방법으로 C++에서는 문자열을 입력받기 위해 문자열이 저장될 문자형 배열을 미리 선언해야 합니다. #include using namespace std; // std라는 name space에 속한 정의들은 이름 안붙이고 사용 가능 int main() { const int SIZE = 10; char name[SIZE]; char address[SIZE]; cout >..