매일 매일 성장하는 섭섭군

KMP Algorithm KMP 알고리즘이란? KMP(Knuth-Morris-Pratt) 알고리즘은 어떤 문자열에서 특정 문자열을 찾고자 할때 유용한 알고리즘입니다. KMP 란 이름이 붙은 이유는 Knuth, Morris, Pratt 세사람이 함께 만들어냈기 때문이라 합니다. KMP 알고리즘을 살펴보기전에 어떤 문자열에서 특정 문자열을 찾고자 한다면 어떻게 해야할까? 단순히 두 문자열을 앞에서부터 차례대로 비교해 나아가면 된다. 효율적이진 않지만 매우 직관적이며 간단합니다. 단순 비교 알고리즘 원본문자열과 찾을 문자열은 다음과 같습니다. 원본 문자열 : "abcdef" 찾을 문자열 : "cd"찾을 문자열이 원본문자열에 있을지 판단하는 과정은 다음과 같이 진행됩니다. 쉽고 단순하게 찾을 수 있지만 O(M*..

Trie(트라이) Trie의 개요 Trie 는 트리 자료구조 중 하나이다. 특히 여러개의 문자열을 저장하는 자료구조인데 특정 문자열을 검색할 때 효율적이다. 가령 최대 길이가 m인 문자열 n개가 있는 집합에서 길이가 m인 임의의 문자열이 있는지 확인하려면 어떻게 해야할까? 단순히 직관적인 방법으로 하나씩 꺼내서 비교하면 된다. 하지만 최악의 경우 O(nm)의 시간복잡도가 소요된다. 그렇다면 Trie는 어떻게 문자열을 저장하길레 문자열을 검색할때 효율적일까? 바로 우리가 사전에서 단어를 찾듯이 문자열을 저장한다. 우리는 사전에서 "Apple"이란 단어를 찾을 때 다음과 같이 찾을것이다. 1. A가 있는 곳을 찾는다. 2. 두번째 글자가 p인 곳을 찾고 세번째가 p인 곳을 찾는다. 3. 마지막 글자까리 위와..

정렬 (Sorting) 정렬은 가장 기초적이면서도 많이 사용하는 알고리즘 입니다. 이미 좋은 정렬 함수들이 많이 존재하고 있어서 직접 만들어서 사용한 경우는 적은 편 입니다. 가장 기초적인만큼 어떤 정렬 알고리즘이 있는지 알고 넘어가면 좋을 것 같습니다. 이번 포스팅에서는 기초적인 알고리즘 3가지를 알아보도록 하겠습니다. 선택정렬(Selection Sort) 버블정렬(Bubble Sort) 삽입정렬(Insertion Sort) 선택정렬 (Selection Sort) 선택정렬은 자리를 선택한 후 해당 자리에 올 요소를 집어넣는 경우입니다. 오름차순으로 정렬을 잰행한다면 첫번째 인덱스에는 가장 작은수를 찾아서 넣고, 두번째 인덱스도 두번째 인덱스부터 가장 작은 수를 찾아서 정렬합니다. 다음 그림을 보면 이해..

트리(Tree) 트리(Tree)란 무엇일까? 자료구조, 코딩문제 등을 보다보면 트리라는 말이 자주 들린다. 트리는 노드(Node)란 것으로 이루어진 자료구조이며 다음과 같은 개념으로 정리된다. - 노드들 간에 1:N 관계를 가지는 비선형 자료구조 - 원소들 간에 계층관계를 가지는 계층형 자료구조 - 상위 원소에서 하위 원소로 내려가면서 확장되는 자료구조처음 트리를 접한다면 무슨 말인지 이해가 잘 안갈 수 있으니 다음 그림을 보면서 함께 이해해 보자!! 나무(Tree) 그림이다. 큰 줄기에서부터 시작해서 가지를 거쳐 나뭇잎들을 가지고 있다. 트리 자료구조는 나무와 같은 모양이라 "Tree"라는 이름이 붙혀졌다. 용어들도 실제 나무가 가지고 있는 것과 거의 일치한다. 실제 자료구조에서 좀 더 이해하기 쉽도록..

Trie(트라이) Trie의 개요 Trie 는 트리 자료구조 중 하나이다. 특히 여러개의 문자열을 저장하는 자료구조인데 특정 문자열을 검색할 때 효율적이다. 가령 최대 길이가 m인 문자열 n개가 있는 집합에서 길이가 m인 임의의 문자열이 있는지 확인하려면 어떻게 해야할까? 단순히 직관적인 방법으로 하나씩 꺼내서 비교하면 된다. 하지만 최악의 경우 O(nm)의 시간복잡도가 소요된다. 그렇다면 Trie는 어떻게 문자열을 저장하길레 문자열을 검색할때 효율적일까? 바로 우리가 사전에서 단어를 찾듯이 문자열을 저장한다. 우리는 사전에서 "Apple"이란 단어를 찾을 때 다음과 같이 찾을것이다. 1. A가 있는 곳을 찾는다. 2. 두번째 글자가 p인 곳을 찾고 세번째가 p인 곳을 찾는다. 3. 마지막 글자까리 위와..

Hash(해시) Hash란? Hash가 무엇일까? 사전에서 Hash의 뜻을 보면 다음과 같다. Hash 1. 해시(고기와 감자를 잘게 다져 섞어 요리한것) -> 아마 해시브라운 같은것일까?? 2. 전화기에서의 우물정자(#) -> 해시테그 여기에서 나온것!!그냥 일반적인 뜻으로는 전혀 컴퓨터와 관련이 없을것 같다. 하지만 숙어를 살펴보면 대략 감을 잡을 수 있다. - make a hash of something : ~를 엉망으로 하다뭔가를 엉망으로 만든다! 그렇다 해시함수는 들어온 입력에 대해서 출력을 엉망으로 만들어버린다. 해시는 암호화 기법중 한가지이다. 그래서 원래 정보를 잘 숨겨야 하는데 이를 엉망으로 만들어 알아 볼 수 없게 만든다면 보다 암호화 하는데 용이할 것이다. 간결하게 해시를 표현한다면 ..

Stack & Que Stack(스택) 스택이란? Stack 이란 무엇일까? 사전에서 검색해보면 다음과 같이 나온다. 1. (보통 깔끔하게 잘 정돈된) 무더기 2. 많음, 다량 3. (깔끔하게 정돈하여) 쌓다, 쌀이다, 포개지다.사전적 의미에서 잘 알 수 있듯이 스택은 무엇인가를 잘 쌓아 올린것이다. 컴퓨터에서는 무엇을 쌓아 올릴까? 대표적으로 메모리를 쌓아올린다. 그렇다면 어떻게 쌓아 올릴까? 스택의 과정 스택은 LIFO(Last In First Out) 구조를 따른다. 즉 마지막으로 넣은 데이터가 먼저 출력된다는 의미이다. 다음 그림을 살펴보자! 1칸당 1byte씩 총 4byte가 있는 메모리가 있다. 지금은 빈 메모리이지만 이곳에 메모리가 하나 둘씩 추가될 것이다. 이 메모리 구조는 아래에서부터 차..