해시(Hash) 자료구조란? 해시는 너무도 유명한 자료구조이기 때문에, 컴퓨터를 공부하는 분들이라면 누구나 한번쯤은 들어보셨을 것입니다. 이 자료구조는 왜 그렇게 중요한 것일까요? 아래의 상황을 보겠습니다. 3명의 사람 (김연아, 손흥민, 서장훈) 이 위와 같이 부탁을 했습니다. 그리고 이러한 기능을 C++ 를 사용해서 구현해달라고 했습니다. 파이썬과 다르게, 기본적으로 C++ 에서는 이런 기능을 지원하지 않습니다. 어떻게 기능을 구현해야 가장 효율적이고, 빠른 자료구조가 될까요? 답은, 각각의 이름(텍스트)에 대해서, 유일한 Key 값을 가지게 하는 것입니다. 만들어진 Key 값을 이용해서 자료에 접근한다면 O(1) 시간만에 접근할 수 있습니다. 아래와 같이 말입니다. 해시(Hash)의 동작원리 해시에..

최대 힙 (Heap) 이란? 최대 힙 (Max Heap) 은 아래 그림과 같이, 부모의 값이 자식의 값보다 항상 큰 자료구조이다. 항상 루트에 최대 값을 가지기 때문에, 이를 이용해서 우선순위 큐 (Priority Queue) 를 구현할 수 있다. 최대 힙의 시간 복잡도는 삽입 (Push) 할 때 O (log N), 삭제 (Pop) 할 때 O (log N) 이므로, 굉장히 합리적인 자료구조임을 알 수 있다. * 참고로 위의 그림에서 루트가 최소가 되는 구조라면 최소 힙 (Min Heap) 이 된다. 동작 원리 최대 힙은 배열을 통해서 구현한다. 위의 최대 힙을 배열로 나타내면 다음과 같다. 이 그림에서 알 수 있듯이, 배열을 통해서 구현하면 다음의 사실을 이용할 수 있다. - 부모의 인덱스 * 2 = 왼..

원형 큐를 사용하는 이유 자료구조를 배우셨다면 큐 (Queue) 에 대해서 배우셨을 겁니다. 선입선출 (FIFO) 의 구조를 가지기 때문에, 수많은 알고리즘에서 큐가 사용됩니다. 만약 큐를 배열에 저장한다면 다음과 같은 상황이 만들어집니다. 이 상황은 어떤 상황일까요? 현재 큐에는 7, 5 라는 값이 들어있고, 출력 시 순서대로 7, 5 이 출력됨을 아실겁니다. (만약 이 부분이 이해가지 않는다면, 큐를 공부하시면 되겠습니다.) 이 상황에서, 인덱스가 0인 공간을 활용하려면 어떻게 해야 할까요? 물론 배열의 모든 원소들을 앞당겨줄수도 있지만, 비용상의 문제로 이러한 작업은 비효율적입니다. 즉, 앞당김 작업없이 지속적인 큐의 사용을 위해서 우리는 원형 큐를 사용해야 합니다. 동작 원리 큐를 이해하고 있다면..

1. 문제 현상 비주얼 스튜디오 혹은 웹 IDE로 문제를 푸는데 배열의 크기를 int arr[1000][1000] 같이 할당했을 때, 에러가 나면서 종료되는 경우가 있었을 것이다. 참고로 이러한 에러가 발생할 때 뜨는 팝업은 다음과 같다. 2. 해결 방법 에러에 대한 해결법을 검색해보았는데, 의외로 굉장히 간단한 문제였다. 지역 변수로 배열을 선언하면 힙 영역에 할당되고, 전역 변수는 스택에 할당된다고 한다. 그런데 힙 영역에 할당되는 Default 크기가 매우 작기 때문에 이러한 에러가 발생하는 것이다. 그러므로 다음과 같은 2가지의 해결 방법이 가능하다. 1) 배열을 전역 변수로 설정하기 가장 간단한 해결 방법이고, 문제 풀이 과정이라면 추천하는 방법이다. 2) 비주얼 스튜디오라면, 다음과 같이 '설..

1. 언제 사용하는가? 정렬은 가장 기본적인 알고리즘임과 동시에 중요한 알고리즘이다. 하지만 그 구현이 쉽지 않고, 실제로 구현해서 사용하기에는 오류가 많기에 문제 하나 하나를 풀때마다 정렬을 코딩하는 것은 비현실적이다. 이를 위해, C++의 STL에서는 사용자가 빠르게 정렬할 수 있는 함수를 제공하는데, 이것이 'sort' 함수이다. 퀵소트를 기반으로 만들어졌다고 한다. 2. 사용 방법 다음과 같이, 'algorithm' 헤더를 include하여 사용한다. vector를 정렬하는 방법과, 배열을 정렬하는 방법은 다르므로 사용법을 익혀야 한다. 기본적으로 vector는 begin와 end 지점을 명시해주며, 배열은 그 크기를 입력해주는 것으로 사용한다. #include #include #include u..

1. 구분자(delimiter)를 이용한 파싱 처리란? 가장 대표적인 예는 엑셀의 .csv 파일이다. .csv 파일은 ',' 기호로 셀을 나누고 있는데, 다음과 같은 모양을 갖추고 있다. 서울특별시,인천광역시,부산광역시 위의 .csv 파일을 ',' 구분자로 구분하면 다음 3개의 항목을 얻을 수 있는 것이다. (1) 서울특별시 (2) 인천광역시 (3) 부산광역시 이와 같이 특정한 구분자를 사용해서 string을 파싱하는 경우가 종종 있는데, 이 때 사용하는 것이 stringstream 객체와 getline 함수이다. 2. 코드 (내용 추가 예정) #include #include #include int main(void) { string s = "seoul,busan,incheon"; stringstream..