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

정렬(선택, 버블, 삽입, 병합)들을 다시 한번 정리해봐야 하는 일이 생겼습니다. 그래서 예전에 정리해두었던 글들을 보고 있는데... 좀 어렵다.... 하.... 물론 코드로 되어있고,기존 방식들과 좀 다르게 구현된 것들도 있어서 그렇겠지만... 우선은 각 정렬들에 대한 정의 이해가 부족한 상태로다시 코드를 봐서 그런것이라는 결론을 내리게 되었습니다! 기사79에서 잘 나온 그림이 있어서 참고하여 올립니다.(문제시 삭제하도록 하겠습니다.) 우선, 선택 정렬에 대한 진행도 입니다. 다음으로 버블 정렬에 대한 진행도입니다. 그리고 삽입 정렬에 대한 진행도입니다. 마지막으로 병합 정렬에 대한 진행도 입니다.A, B 배열을 비교해가며 하나로 합칠 수 있지요. 이렇게 정렬되어지는 과정에 대한 도식화를 이해하게 된다..

안녕하세요 삽잡이입니다. 이번에는 간단하게 해시 테이블과 의사 결정 알고리즘에 대해서 알아보려고 합니다.물론... 코드는 없고... 간략하게 알아보도록 하겠습니다.사실 정리용... 하하... 해시 테이블은 해싱이라는 작업을 통해 자료를 보관하는 테이블을 말합니다.그렇다면 해싱(Hashing)이란 무엇일까요?해싱이란, 특정 알고리즘으로 자료를 보관할(한) 위치를 판단하는 과정을 말합니다.여기서 특정 알고리즘이란 해시 함수를 말하는 것입니다. 결과적으로 해시 테이블을 통해서 어떠한 자료를 집어넣었을때 보관한 자료의 인덱스를 보내줄 것이고 인덱스를 따라가면 특정 자료가 보관되어 있게 되는 것입니다. 해시 테이블에는 해시 함수를 통해 자료를 보관하려고 했지만,이미 해당 공간에 자료가 보관되어있을 때 충돌이 나서..

안녕하세요 삽잡이 입니다. 이번 시간에는 그래프를 알아보려고 합니다.이전에 트리에 대해서 배웠던 적이 있습니다.트리의 특징을 살펴봤을때에 고립되있지 않고, 순환되지 않는 노드들의 연결 집합을 트리라고 했었습니다.이 외에 모든 것들을 그래프라고 말할 수 있을 것 같습니다. 그래프를 표현한다는 자체가 목적에 따라 다 다르겠지만, 가장 얘기가 많이 나오는 것중 하나가 바로, 정점과 간선의 집합체에 대해서 많이들 얘기합니다. 정점(vertex) 와 간선(edge) 이 둘로 그래프를 표현할 수있습니다.그래프로 표현할 때에 어떠한 정점에서 어떠한 정점으로 갈 수 있는 방향성이 간선에 표현된다면,출발 정점과 끝정점이 나타날 수 있을 것입니다.이런 그래프를 방향성 있는 그래프라고 할 수 있겠지요. 모든 간선이 양방향으..

안녕하세요 삽잡이입니다. 이버 시간에는 Heap 정렬에 대해서 간략하게 설명하려고 합니다. Heap 정렬은 Heap 트리를 이용한 정렬입니다.Heap 트리는 완전 이진 트리로 최대 힙과 최소 힙을 가지고 있습니다.최대 힙은 당연하게도 자식보다 부모의 값이 더 크겠지요. 최소 힙은 그와 반대이겠구요...즉, 최대 힙같은 경우에 맨 상단에 있는 겂이 최대 값이 되겠습니다.반대로 가장 끝에 있는 것이 최소 값이 되겠지요... 힙 트리의 경우 완전 이진 트리인 특징을 가지고 있습니다. 또한, 배열로 표현할 수 있어야합니다.여기서 생각해볼 것은 완전 이진트리를 배열로 표현하는 것입니다. 완전 이진트리를 배열로 나타내기 위해 정규식으로 표현해보겠습니다.왼쪽 자식 노드 = 2*x + 1오른쪽 자식 노드 = 2*x +..

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

안녕하세요 삽잡이입니다. 이번 시간에는 수식 트리에 대해서 알아보려고 합니다.우선 이번 내용에는 절대적으로 코드는 없습니다... 그냥 어떻게 해야할지 정리해보는 시간이기 때문이죠... 허허... 아무튼, 시작해보도록 하겠습니다. 만약에 수식 인자를 받아서 계산하는 프로그램을 만들어본다고 하지요.4+2*3-9/2 이렇게 말입니다... 그렇다면 계산의 순서는 어떻게 진행될까요? 왼쪽부터 차례대로? 푸하하... 그렇게하면 안된다는건 너무도 당연하게 아시리라 믿습니다... 자... 그럼 우리는 어떻게 계산을 하게 해야할까요?우선 연산자 우선순위에 의해서 곱하기 및 나누기를 우선적으로 연산해줘야 하는데요, 간단하게 stack을 사용하여 우리는 이 문제를 해결할 수 있게 됩니다.스택은 순차적으로 값을 저장하고 맨 ..

안녕하세요 삽잡이 입니다. 오늘은 카운트 정렬(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과 ..