#011_자료구조와 알고리즘_Map

안녕하세요, 삽잡이입니다.

요즘 날씨가 진짜 해도해도 너무하게 덥네요...

주말 동안 힐링좀 하다보니 

여러모로 블로그에 공부한 내용을 정리하는 것이 좀 미뤄졌었군요...

흠... 다시 시작해보도록 하겠습니다.

이번시간에는 map에 대해서 알아보려고 합니다.

set, multiset, map, multimap ...

이 네 가지는 STL에서 제공하는 이진 탐색 트리들입니다.

자... 한번 생각해봅시다...

이진 탐색 트리에서는 중복 된 값을 보관할 수 없다고 했었습니다.

하지만, 중복 된 값을 보관하고자 하는 사용자들을 위해 STL에서는 

이진 탐색 트리와 전체적인 논리가 비슷하지만, 같은 키 값도 보관할 수 있도록 제공하는 것이

바로 multiset 과 multimap입니다.

흠... 당황스러우신가요... set과 map이 뭔지도 설명 안드리고 다짜고짜 mulit라니... 

지금부터 설명하도록 하지요...

set은, 기본 형식을 보관하는 용도로 쓰이고...

map은 UDP 즉, 사용자 정의 형식을 보관하는 용도로 쓰입니다.

set과 map은 결론적으로 자료구조의 일종으로써 데이터를 보관하는 용도로 쓰이겠지요.

이진 탐색 트리는 '검색 효율'이 높아 사용하는 빈도가 높습니다.

예를 하다 들어볼테니, 다시 한번 머리를 굴려봅시다.

학생 관리 프로그램을 만든다고 생각해 보도록 하겠습니다.

학생 객체를 생성할 것이고, 해당 객체를 이진 탐색 트리에 보관했다고 가정해보겠습니다.

추가적으로, 학생 객체내에는 학번과 학생 이름이라는 멤버 변수들이 있다고 해보죠...

학생을 검색한다는 기능은 무엇을 의미하는 것일까요?

중복되지 않는 고유의 학생을 구분할 수 있는 키 값(primary key)을 사용하여

학생의 정보를 불러들어오는 기능이라고 정의 할 수 있을 것 같습니다.

map이라는 자료구조를 사용하게 되면,

key와 value를 쌍으로 보관하게 되어 해당 키 값을 전달 받아 해당 자료를 찾기에 보다 용이합니다.

set의 경우 key만 보관하게 됩니다. 

map에 비해 데이터를 관리하고자 하는 목적이 있는 프로그램에서 사용 빈도가 적을 것 같은 느낌이 들군요...

음... set 또한 필요한 부분이 있을 것이고, 중요한 자료구조일 수 있으나

제 블로그에서는 여기까지만 소개를 하는 것으로 하겠습니다.

아무튼, 다시... 집중을 해보도록 하겠습니다.

이진 탐색 트리의 경우에는 데이터를 알아서 보관해줍니다. 

루트로 부터 시작하여 작으면 왼쪽, 크면 오른쪽 이런식으로 말입니다...

컴퓨터는 이진 탐색 트리로 데이터를 객체들을 보관한다고 했을때

정렬하는 기준 즉, 비교 논리를 알 수 있을까요?

모른다는 것이죠... 

위에서 설명했듯이, 이진 탐색 트리는 데이터를 알아서 보관해준다고 했으니 말입니다...

따라서 map에서는 위에서 말한 것과 같이,

key (비교에 사용할 형식)과 value (보관할 값)... 두 쌍을 보관하게 됩니다.

사용할 때 자료를 보관할 데이터와, 그 자료의 비교 논리에 해당되는 키를 쌍으로 보관한다는 것이죠...

map을 사용하는 경우는 다양하게 있을 것입니다.

insert, erase, iterator 등을 사용하는 방법들 있겠지만, 

이번에는 새롭게 [] 연산을 통해 map을 다뤄보려고 합니다.

실제 회원 관리를 하는 프로그램을 작성한다고 해보죠...

우리가 이전에 살펴본 vector에서 인덱스 검색을 했을 때에는,

primary key 값으로 int형태의 학생 번호나 순차적으로 id를 부여하는 형식으로 진행을 했었습니다.

하지만, 실제 관리하는 프로그램의 경우 id들은 int형이 아닌 string 형일 것입니다.

맞죠... 누가 id를 1, 2, 3... 이렇게 제공할까요...

sapzape, sapsape, zapzape 이렇게 사용하겠지요... 허허...

아무튼, 이와 같이 id를 제공할 경우에

int형의 key 값을 제공할 때와 다른 차이점들이 속출하게 됩니다.

기존의 int형 처럼 데이터의 길이가 들쭉 날쭉할 것이고... 

최대 id 값(최소 ~ 최대 값)도 모를 뿐더러 string형태이니 

결론적으로 vector를 이와 같은 상황에서 사용하게 된다면

전혀 효과적이지 못할 것입니다.

이와 같은 vector의 한계(?)를 극복하고자, 적재적소! map을 사용하려고 하는 것입니다.

여담으로 말씀드린다면, map은 dictionary라고도 많이들 부릅니다.

사전을 보면, 단어와 뜻이 있습니다. map에 적용해보자면 단어를 key, 뜻을 value 라고 할 수 있게 되죠...

아무튼, 회원을 보관할 때

비교논리에 사용할 키 형식(비교할 키 형식)을 통해 실질적으로 보관할 데이터 형식에 접근할 수 있도록

프로그램을 만들어 보도록 하죠...

참고로 map이라는 자료구조에서 인덱스 연산자로 접근 시

데이터가 없는 상태라면 0을 반환해줍니다.

다음 시간? 아마 주말정도에... 

map을 사용한 회원 관리 프로그램을 간단하게 구현해보고 소개해드리도록 하지요....

프로그램에서 map이 어떻게 사용되는지를 중점적으로 보시는 것이 좋을 듯합니다.

이상 삽잡이였습니다~!