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

안녕하세요 삽잡이입니다. 이번 시간에는 이진 탐색 알고리즘에 대해서 정리해보려고 합니다.이진 탐색(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장들 사이에 비교를 통해 적절한 위치에 삽입을 하게 되죠."이와 같이 '점진적'인 방법을 삽입 정렬에서는 사용하고 있습니다... 설계하는 방법이 한가지는 아니겠죠 하하...그러다면, 이..

안녕하세요 삽잡이입니다. 이번 시간에는 지난 시간, 버블 정렬과 선택 정렬에 이은 삽입 정렬에 대해서 알아보려고 합니다. 삽입 정렬은 배열의 부분 배열을 정렬 시켜 나가는 정렬 방식입니다. 예를 들어보도록 하겠습니다. 삽잡이가 '원카드' 게임을 한다고 가정해보죠... 해당 게임에 사용하는 카드는 다이아, 하트, 스페이드, 클로버 모양과 각각 순서에 맞는 카드를 제공해줍니다.카드를 뒤섞어 놓고 상대와 본인은 한장씩 뒤집힌 카드를 가져갑니다. 왼손에 한장씩 카드를 가져오는데 평소 조그마한 정리 조차 하지 않으면 미칠듯이 불안감에 빠지는 삽잡이는한장, 한장 카드를 집어 왼손으로 가져올 때마다카드를 순서대로 정리합니다...그리고 정해진 수의 카드를 가져갔다면, 이제 게임은 시작 됩니다. 이게 삽입 정렬입니다. ..

안녕하세요 삽잡이입니다. 이번시간에는 find_if 함수에 대해서 간략하게 알아보려고 합니다...자료구조 배열에 대해서 알아보다가find_if 함수가 뭔지 하는... 처음에 이해가 안갔었는데그 이유가 함수 객체에 대한 이해 부족 때문이었습니다... 왜 안되지 하며 한참 째려보기만 했다는... 하지만 째려보면 반드시 승리하게 되있습니다. 계속해서 째려보세요~!뭔 x소리인지... 죄송합니다. 참고로, 함수 객체에 대한 이해가 부족하시다면...C++ 글의 함수 객체에 대한 글을 참고하시길 바랍니다... 우선, find_if 함수는STL 에서 제공하고 있는 알고리즘인데요,컨테이너... 그러니까 자료를 보관하고 있는 메모리 구조에서 원하는 데이터를 찾을 수 있도록제공해주는 알고리즘입니다. 우선 원형을 살펴보시지요..