Algorithm & Data Structure

들어가며 큐는 먼저 들어간 원소가 먼저 나오게 되는 구조여서 FIFO(First In First Out) 자료구조라고 부른다. 그리고 C++ STL에 큐가 구현되어 있어 쉽게 이용할 수 있다! 큐는 BFS, Flood Fill 알고리즘에 보통 사용한다. 큐(Queue) 란? 큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 프린터의 출력 처리나 윈도 시스템의 메시지 처..

들어가며 앞으로 세 가지 관련 있는 자료구조인 스택, 큐, 덱에 대해서 다룰 것이다. 스택은 먼저 들어간 원소가 제일 나중에 나오게 되는 구조여서 FILO(First In Last Out) 자료구조라고 부르기도 한다. 또한 반대로 나중에 들어간 원소가 제일 먼저 나오게 되는 구조이므로 LIFO(Last In First Out)의 형태를 띠는 자료구조이기도 하다. 그리고 C++ STL에 스택이 구현되어 있어 쉽게 이용할 수 있다! 스택(Stack) 이란? 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last I..

들어가며 연결 리스트(Linked List)는 3가지 종류가 있다. 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List)가 이에 해당한다. 그리고 C++ STL에 연결 리스트가 구현되어 있어 손쉽게 사용할 수 있다! 연결 리스트(Linked List)란? 연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스..

들어가며 STL은 C++에서 제공되는 라이브러리이다. STL에는 다양한 알고리즘과 자료구조가 구현되어 있다. 따라서 직접, 힘들게 우리가 구현하지 않고 사용할 수 있어서 코드 작성에 큰 도움을 준다. STL 이란? 표준 템플릿 라이브러리(STL: Standard Template Library)는 C++을 위한 라이브러리로서 C++ 표준 라이브러리의 많은 부분에 영향을 끼쳤다. 이것은 알고리즘, 컨테이너, 함수자 그리고 반복자라고 불리는 네 가지의 구성 요소를 제공한다. - 위키백과 STL Vector Vector는 배열과 비슷한 기능을 한다. C++에서는 배열을 선언할 때 크기를 명시해야 하고, 무조건 해당 크기 안에서만 사용해야 한다. 하지만, vector는 동적으로 원소를 추가할 수 있고 크기가 늘어..

들어가며 컴퓨터는 1초에 대략 3~5억 개 정도의 연산을 처리할 수 있다. 예를 들어서 시간 제한이 1초인 문제가 있으면 이는 3~5억번의 연산 안에 답을 내고 종료하여 시간 초과가 아닌 코드를 짜라는 것을 알려주는 것이다. 밑에 함수 하나를 보고 생각해보자. int func(int arr[], int n) { int cnt = 0; for (int i = 0; i < n; i++) { if (arr[i] % 5 == 0) { cnt++; } } return cnt; } 위의 함수에서 연산이 몇 번 필요할까? cnt 변수를 선언하고 0을 넣는 과정에서 1번, for문의 i에 0을 대입할 때 1번, n번에 걸쳐 반복되는 일에서 i가 n보다 작은지 확인하고 작으면 i++ 과정을 하니까 연산 2번, if문으로..