한글로는 삽잡이, 영어로는 shovelman

안녕하세요 삽잡이 입니다. 이진 탐색 트리는 검색을 보다 용이하게 하기 위해 만들어진 트리입니다.그런데 만약, 이진 탐색 트리가 한쪽으로 계속 쏠리게 되면 어떠한 현상이 벌어질까요? 자... 이와 같이 한쪽으로 쏠려있는 트리의 경우 검색 성능이 현저하게 떨어집니다.균형잡힌 트리에 비해 높이가 더 높아서 심하면 검색 속도가 선형 자료구조의 검색 속도와 차이가 없어 질 수 도 있습니다. 즉, 균형이 잡혀야 이진 탐색 트리는 속도가 나온다는 것이지요... 따라서 이번 시간에는 균형잡힌 트리를 만들기 위해서 어떻게 해야할지에 대해서이미 기울어진 트리를 균형잡는 방법과, 애초에 균형 잡히게 트리를 만드는 방법을 알아보겠습니다. 자, 우선 기울어진 트리를 어떻게 하면 균형을 잡을 수 있을까요?배열을 하나 준비해두고..

안녕하세요 삽잡이 입니다. 오늘은 카운트 정렬(count sort)와 기수 정렬(radix sort)에 대해서 알아보고자 합니다. 우선, count sort는 도수들의 개수를 파악합니다.그 다음에 도수들을 배치할 수 있는 최대 범위를 구한 뒤 정렬을 진행 하는 것이지요. 우선 도수란 무엇일까요?예전 중/고등학교 시절 수학시간에 들어본 말 아닌가요? 도수 분포표에서 말입니다.도수란, 각 계급에 속하는 자료의 수라고 합니다.예를 들어보자면 말입니다... 이와 같은 배열이 있다고 가정해보겠습니다. 이때 도수의 개수는 어떻게 될까요?도수는 각 계급에 속하는 자료의 수라고 했습니다.여기서 각 계급이란 a,b,c 라는 문자들이라고 볼 수 있겠군요.그렇다면 도수의 개수는 아래와 같습니다. 자 그렇다면 count so..

안녕하세요 삽잡이입니다. 오랜만에 포스팅을 하군요.... 사실... 좀 방황좀 하고 아주 푹~쉬웠던 것 같습니다. 하하... 뭐 어중간할 바에 바닥 한번 시원하게 찍고 높이 비상하는게 좋지 않겠습니까!? 다시 정신 부여잡고 시작해보도록 하지요! (사실 아직 정신 못잡은건 비밀입니다...) 지난 시간에 map이라는 자료구조를 잠시 알아봤었는데요, 이 시간에는 map이 어떻게 이루어져 있는지 알아보려고 합니다. 자... 우선, map은 'key'와 'value'를 쌍으로 하고 있는 pair를 보관하고있습니다. pair는 STL에서 제공하는 두개의 형을 하나로 보관할 수 있는 구조체라고 해야하나? 아무튼... pair 형태로 보관하고 있습니다. 이런식으로 생겨먹었지요... 1234567891011121314t..

안녕하세요 삽잡이입니다. 이번시간에는 병합 정렬에 대해서 알아보려고 합니다.병합정렬은 분할 정복 방식에 기반으로 한 정렬 알고리즘입니다.분할 정복? 많이 들어보시지 않았습니까? 맞습니다... 퀵정렬에 대해서 알아볼 때 언급된 내용입니다. 기억이 나시죠? 하하하... 분할 정복이 기억이 안나시는 분들을 위해 간략하게 설명을 드리자면,커다란 문제를 잘게 나눠서 작은 문제를 극복하는 것이죠...작은 문제를 해결함으로 나온 값들을 합쳐 결국 큰 문제를 해결하는 것이 분할 정복 방식의 핵심이라고 생각합니다. 병합 정렬은 분할 정복 방식을 기반으로 한다고 했습니다.다른 정렬들과 다르게 병합 정렬은 기존 데이터가 담겨있는 배열 이외에 추가적으로 또 다른 배일이 필요합니다. 이에 병합 정렬은 외부 정렬에 속하기도 합니..

안녕하세요, 삽잡이입니다. 요즘 날씨가 진짜 해도해도 너무하게 덥네요...주말 동안 힐링좀 하다보니 여러모로 블로그에 공부한 내용을 정리하는 것이 좀 미뤄졌었군요...흠... 다시 시작해보도록 하겠습니다. 이번시간에는 map에 대해서 알아보려고 합니다. set, multiset, map, multimap ...이 네 가지는 STL에서 제공하는 이진 탐색 트리들입니다. 자... 한번 생각해봅시다...이진 탐색 트리에서는 중복 된 값을 보관할 수 없다고 했었습니다.하지만, 중복 된 값을 보관하고자 하는 사용자들을 위해 STL에서는 이진 탐색 트리와 전체적인 논리가 비슷하지만, 같은 키 값도 보관할 수 있도록 제공하는 것이바로 multiset 과 multimap입니다. 흠... 당황스러우신가요... set과 ..

안녕하세요 삽잡이입니다. 이번 시간에는 이진 탐색 알고리즘에 대해서 정리해보려고 합니다.이진 탐색(Binary Search)은 오름 차순으로 정렬된 리스트가 준비 된 상태에서처음 중간의 값을 기준으로 탐색 범위를 1/2씩 줄여나가는 알고리즘입니다. 예를들어볼까요? 2 3 4 5 6 7 10 15 20 25 50 57 59 60 이런 오름차순 리스트가 있다고 가정해보도록 하겠습니다.여기서 저는 57이라는 값을 찾고자 한다면 임의의 수 즉, 데이터 집합의 중앙에 값과 비교를 합니다. 57은 15 보다 크니 15이하의 데이터들은 모두 배제를 하게 됩니다. 즉, 20 ~ 60까지의 리스트에서 또 중앙의 값과 비교를 시작합니다.중앙의 값의 50이라고 해보겠습니다.50보다 57은 크니 50이하의 값은 모두 배제를 ..

안녕하세요 삽잡이입니다.날이 정말로 real 덥네요... 하... 차라니 습하지만 않아도 좋을텐데... 아무튼...이번 시간에는 이진 탐색 트리를 알아보겠습니다. 트리... 영어 아시죠 Tree 푸하하 나무입니다.자료들이 나무형태로 쭉쭉 펴나가며 보관되는 방식입니다. 머릿속에 나무를 떠올려보세요...가지가 서로 붙어서 순환되는 모습인 나무가 있을까요?또한, 가지가 연결되 있지 않고 고립된 가지가 있는 나무가 있을까요? 없죠... 명백히트리의 경우 Cycle 즉, 순환적이지 않으며 고립된 부분이 없는 구조여야합니다. 이와 같은 트리 구조에는 부모와 자식간에 계층적인 구조를 지니게 됩니다.하나의 노드가 가질 수 있는 최대 노드의 개수가2 개이면 이진 노드, 3 개이면 삼진 노드 트리라고 말할 수 있습니다. ..

안녕하세요 삽잡이입니다. 이번 시간에는 지난 시간에 배웠었던 더미가 있는/없는 연결 리스트에 대한 코드를 소개하고자 합니다. 물론, 귀차니즘에 절정인 삽잡이는 전체 코드를 소개하지 않을 것입니다.푸하하... 더미가 없는 연결리스트는노드를 처음 생성할 때, 맨 앞에 추가할 때, 맨 뒤에 추가할 때, 중간에 추가할 때각각의 경우에 따라 코드의 차이가 있습니다. 하지만 더미가 있는 연결리스트의 경우에는더미가 없는 연결리스트에서 중간에 노드를 추가하는 방식과 차이가 없기 때문에어떠한 경우에서도 코드의 차이가 없습니다. 그렇다면, 잔소리는 집어치우고...각각의 경우 어떻게 코드를 구현하면 좋을지에 대해서 소개하겠습니다. 물론, 이 코드는 굳이 이해하실 필요는 없습니다.간략하게 list의 기능들 중 push_bac..

안녕하세요 삽잡이 입니다. 이번 시간에는 더미 노드가 없는 상태의 리스트를 만들 때에 대해서 알아보려고 합니다. 일반적으로 지난시간에 봤듯이 더미노드가 있는 상태의 리스트에서는 데이터가 담긴 노드가 10개 일지라도,총 노드의 개수는 12개였습니다.왜냐? 더미 노드가 있는 연결 리스트에서는 데이터가 없는 노드 두 개가 있었기 때문입니다. 하지만 더미 노드가 없는 리스트의 경우데이터가 보관 된 노드의 개수와 실제 리스트에 총 노드의 개수가 동일합니다. 음... 그렇다면 더미 노드가 있는 리스트와 차이점은 이게 끝일까요?아닙니다... 더미 노드가 있는 리스트는 리스트 최초 구현시 Head와 Tail 이라는 더미 노드들이 생성되기 때문에데이터를 추가하거나, 삭제할 때 둘다 모두 방법이 동일합니다. iterato..

안녕하세요 삽잡이 입니다. 오늘은 연결 리스트에 대해서 알아보도록 하겠습니다.연결 리스트는 STL 에서 제공하는 자료구조 중에 하나로써,비슷한 친구로 지난 시간에 배운 vector가 있습니다. 연결리스트는 '노드'들의 선형 집합을 말합니다. 영어로는 node. 즉, 나무 줄기의 마디를 뜻합니다.이 글을 진행하다 보면 결국은 왜 node라고 표현하는지 감을 잡으실 수 있을 것입니다. 노드들의 선형 집합... 그렇다면 자료구조에서 노드는 뭐라고 정의를 하고 있는가?바로, 데이터와 링크의 조합이라고 정의하고 있습니다.그렇다면 데이터는 알겠고.... 링크는?노드의 위치 정보라고 정의할 수 있습니다. 자 간략하게 연결 리스트에 사용되는 요소 및 용어에 대해서 알아봤습니다.그렇다면, 이제 연결 리스트를 도식화 해보..