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

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

안녕하세요, 삽잡이입니다. 요즘 날씨가 진짜 해도해도 너무하게 덥네요...주말 동안 힐링좀 하다보니 여러모로 블로그에 공부한 내용을 정리하는 것이 좀 미뤄졌었군요...흠... 다시 시작해보도록 하겠습니다. 이번시간에는 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라고 표현하는지 감을 잡으실 수 있을 것입니다. 노드들의 선형 집합... 그렇다면 자료구조에서 노드는 뭐라고 정의를 하고 있는가?바로, 데이터와 링크의 조합이라고 정의하고 있습니다.그렇다면 데이터는 알겠고.... 링크는?노드의 위치 정보라고 정의할 수 있습니다. 자 간략하게 연결 리스트에 사용되는 요소 및 용어에 대해서 알아봤습니다.그렇다면, 이제 연결 리스트를 도식화 해보..

안녕하세요 삽잡이입니다. 지난 시간에 Stack을 배워봤으니, 이번 시간에는 Queue를 배워보도록 하겠습니다. Queue와 같은 경우에는, 들어가는 순서대로 나갑니다.어찌보면... 현실에 맞는 자료구조가 아닐지...즉, 차례대로 자료를 보관하고 가장 오래전에 보관된 자료를 꺼내주는First In First Out 방식의 자료구조 형식을 가지고 있습니다. Queue에서는 보관할 위치를 꼬리에 보관한다고 하여 rear,가장 앞에 것을 꺼낸다 해서 front 이 두가지의 위치를 알고 있을 필요가 있습니다. stack에서는 나가는 구멍과 들어오는 구멍이 하나이기에 위치정보 하나만 알아도 상관이 없었지만,Queue는 나가고 들어오는 구멍들이 다르기에 두개의 위치정보를 알아야하는 것입니다. 자... 그렇다면 생각..

안녕하세요 삽잡이 입니다. 이번 시간에는 stack에 대해서 알아보고자 합니다.음... 물론 stack이 오늘의 main 주제는 아닌 것 같고요...아니다... stack을 사용하는.. 동적 프로그래밍에 대하여 알아본다고 해야하나? 참고로, 글이 정말 산으로 갈 것입니다. 등산 한다고 생각하시고...올라가는 과정은 힘들지만 정상에 올라갔을 때의 그 기분...산을 자주 올라가시는 분들은 아실터인데요...그 만큼, 산에 올라가는 과정을 글 속의 삽질로 적날히 보여드리도록 하지요....결국 결론은 나올 것입니다. 하지만 그 과정이 진짜 싫다 하시는 분들은... 뒤로... 흙 ㅠㅠ 하하... 아무튼... 시작해봅시다. 우선 간략하게 stack에 대한 소개를 해보도록 하겠습니다.stack은 보편적으로 알고 계시듯..

안녕하세요 삽잡이 입니다. 이번시간에는 '누구보다 빠르게 난 남들과는 다르게' ...이름 그대로 빠른, Quick Sort (퀵 정렬)에 대해서 알아보려고 합니다. 얼마나 빠르길래.... 하하...퀵 정렬을 이해하기 위해서는 우선, 알고리즘의 설계 방법들에 대해서 알아볼 필요가 있습니다. 알고리즘을 설계하는 방법은 여러가지가 있습니다.예를 들어 볼까요? 이전 시간에 본 삽입 정렬을 보도록 해봅시다. "i 장의 카드를 삽잡이는 손에 쥐고 있습니다.이때 한 장의 순서가 눈에 거슬리는 삽잡이는 그 카드 한 장을 뺀 나머지 i-1장들 사이에 비교를 통해 적절한 위치에 삽입을 하게 되죠."이와 같이 '점진적'인 방법을 삽입 정렬에서는 사용하고 있습니다... 설계하는 방법이 한가지는 아니겠죠 하하...그러다면, 이..