Song 컴퓨터공학

미로 찾기 문제는 대표적인 스택과 큐의 응용 예제입니다. Ex. 7*15 미로 0 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 1은 벽이고, 0은 이동할 수 있는 길입니다. 이 문제의 경우 동서남북만 이동할 수 있는 것이 아니라 아래 처럼 8방향으로 모두 이동이 가능합니다. 실제 미로는 테두리로 1을 삥 두를 것이기 때문에 미로를 저장하는 배열은 maze[7][15] 이 아닌 maz..

컨테이너 클래스(Container class)란 다수의 데이터 객체들을 수용 또는 저장하는 자료 구조를 표현하는 클래스 를 말합니다. 컨테이너 클래스는 일반적으로 객체들을 삽입하거나 삭제할 수 있으며, 앞에서 보았던 배열도 컨테이너 클래스의 일종입니다. 앞으로 여러 형태의 컨테이너 클래스들을 보게 될텐데, 오늘은 C++ pesudo code 를 위주로 Bag, Stack, Queue 를 확인해보도록 하겠습니다. 각 개념에 대한 설명은 C 자료구조에서 자세히 해놨기 때문에 링크만 걸고 코드 위주로 보겠습니다. Bag 클래스란 이름 그대로 가방입니다. 삽입(Push)하고, 삭제(Pop)하고, 비었는지 확인하고(IsEmpty), 안에 몇 개가 들어가 있는지를 확인(Size)하는 기능이 담겨 있습니다. 템플릿 ..

아마 많은 프로그래밍을 배우는 학생들 중 행렬을 어떻게 저장하는가에 대한 고민을 안해본 사람도 있으실 것 같습니다. 파이썬에서 손 쉽게 행렬을 리스트나, 여러 자료구조로 다루지만 실제적으로 어떻게 저장해야 효율적인가? 는 이미 많이 최적화된 상태로 사용하고 있기 때문이죠. 그래도 행렬의 표현을 고민해보는 것은 자료구조를 이해하는데 있어 좋은 예제 중 하나입니다. 그 중에서도 희소 행렬(Sparse matrix)란 행렬의 원소 중에서 0인 값이 더 많은 행렬을 의미합니다. 이런 행렬은 추후 자연어처리 부분에서도 나타나기 때문에 어떻게 이를 안쓰고 효율적으로 모델링 할 수 있을까? 등 많이 고려되는 사항 중 하나입니다. 일반적으로 행렬은 $a[i][j]$ 와 같은 형태의 2차원 배열을 흔히 사용합니다. 그러..

배열을 이용한 매우 기초적인 다항식의 ADT 구현 코드입니다. 1차원 배열을 이용해 덧셈과 곱셈까지만 구현합니다. 다항식은 기본적으로 계수(coefficient)와 지수(exponet)로 나타낼 수 있죠. 따라서 (계수,지수)의 쌍으로 다항식의 한 term을 나타낼 수 있습니다. 다항식의 덧셈과 곱셈을 정의하려면 다항식의 몇 가지 특성을 알아야 합니다. 예를 들어 덧셈은 같은 차수에 대해서 계수를 더해야한다는 것, 각 term 들의 곱셈은 지수법칙에 의해 차수의 덧셈으로 구성되어야 한다는 점 등등.. 기본적인 내용은 생략하도록 하겠습니다. // Polynomial.h file #ifndef POLYNOMIAL_H #define POLYNOMIAL_H class Polynomial { public: Pol..

[C++] STL 정리 ( pair, vector, stack, queue, deque, map, set, algorithm ) STL(Standard Template Library) 는 C++ 에서 가장 자주 사용되는 라이브러리 중 하나입니다. PS (Problem Solving)을 공부하기 전에 필수적으로 익혀야 하는 라이브러리입니다. 문제를 푸는데 필요한 알고리즘 songsite123.tistory.com 위 포스팅에서 STL에 대해 전반적으로 총정리를 해봤습니다. 오늘은 이 중에서도 자주 사용되는 pair, vector, list 컨테이너에 대해 집중적으로 살펴보고 iterator 의 응용, 그리고 algorithm 을 사용해보는 방법까지 알아보도록 하겠습니다. STL(Standard Templa..

[C++] 템플릿 ( Template ) - 함수 템플릿 / 클래스 템플릿 C++ 이 가지는 특징 중 하나로 일반화 프로그래밍(Generic programming) 을 들 수 있습니다. 일반화 프로그래밍이란 쉽게 말하자면 일반적인, 다양한 상황에서도 같은 코드로 적용할 수 있는 것을 말합 songsite123.tistory.com 위 포스팅에서 제너릭의 개념과 이를 위한 template 의 사용법과 예제를 확인했습니다. 맨 마지막에 제네릭 클래스에 대해 다루긴 했는데요 너무 간단하게 다룬 것 같아 오늘은 예제 위주로 확인해보며 template 를 이용한 제네릭 클래스에 대해 더 자세히 알아보는 포스팅입니다. 제네릭 클래스를 만들기 위해서는, 클래스의 선언부와 구현부를 모두 template 로 선언해야 합..

[C++] 가상 함수와 오버라이딩 ( Virtual function and overriding ) 오버라이딩이란, 부모 클래스로부터 상속받은 메소드의 내용을 재정의(변경) 해야 하는 것을 오버라이딩이라고 합니다. 다른 말로 파생 클래스에서 기본 클래스에 작성된 가상 함수를 재작성하 songsite123.tistory.com 위 포스팅에서 가상함수와 오버라이딩의 개념에 대해 알아보았습니다. 이번 포스팅에서는 순수 가상 함수를 사용한 추상 클래스에 대해 알아보도록 하겠습니다. 순수 가상 함수 (Pure virtual function) 먼저 순수 가상 함수(Pure virtual function) 이란 함수의 코드가 없고 선언만 있는 가상 함수 를 말합니다. 순수 가상 함수는 멤버 함수의 원형 뒤에 = 0; ..

[C++] 생성자와 소멸자 ( Constructor and Destructor ) 포스팅의 목차 / 링크 1. 생성자 (Constructor) 2. 디폴트 생성자 (Default Constructr) 3. 복사 생성자 (Copy Constructor) 4. 소멸자 (Destructor) 5. 생성자/소멸자 실행 순서 클래스를 통해 객체를 생성하면, 해당 객 songsite123.tistory.com 클래스는 생성자와 소멸자가 최소 1개씩 있으며, 객체의 생성과 호출에 생성자와 소멸자가 각각 실행되는 걸 위 포스팅에서 배웠습니다. 오늘 포스팅은 상속에 초점을 맞추어 파생 클래스의 객체가 생성되거나 소멸 될 때, 기본 클래스의 생성자와 소멸자가 호출되는지, 파생 클래스의 생성자와 소멸자가 호출되는지, 그 사..

오버라이딩이란, 부모 클래스로부터 상속받은 메소드의 내용을 재정의(변경) 해야 하는 것을 오버라이딩이라고 합니다. 다른 말로 파생 클래스에서 기본 클래스에 작성된 가상 함수를 재작성하여 기본 클래스에 작성된 가상 함수를 무력화 시키고, 파생 클래스에서 재작성한 함수를 사용하는 것입니다. 무슨 소리이고 이런 걸 왜 하나 싶으실텐데, 하나의 예시를 들어보겠습니다. 우리가 자동차를 하나 샀습니다. 자동차를 샀으면 우리는 운전을 하겠죠? 운전을 하기 위해 '엑셀' 과 '브레이크' 라는 것을 통해 운전을 하게 될 겁니다. 이를 간단히 클래스로 표현해보면 class Car{ int speed; public: virtual void Accelerator() {} virtual void Break() {} ... } ..

상속 (Inheritance) 는 객체 지향 언어의 가장 중요한 특성 중 하나입니다. 상속을 통해 소프트웨어의 재사용이 가능해지고, 동적 바인딩을 통해 객체 지향 프로그래밍을 할 수 있고 계층적으로 프로그램을 관리할 수 있습니다. C++ 에서의 상속은 두 클래스 사이의 부모-자식(기본-파생) 상속 관계를 의미합니다. 상속 (객체 지향 프로그래밍) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 객체 지향 프로그래밍(OOP)에서, 상속(inheritance)은 객체들 간의 관계를 구축하는 방법이다. 클래스로 객체가 정의되는 고전 상속에서, 클래스는 기반 클래스, 수 ko.wikipedia.org 상속의 정의는 위 링크를 참조해주세요. 예제 코드 위주로 상속을 알아보겠습니다. #incl..