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..

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