매일 매일 성장하는 섭섭군

트리(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 : ~를 엉망으로 하다뭔가를 엉망으로 만든다! 그렇다 해시함수는 들어온 입력에 대해서 출력을 엉망으로 만들어버린다. 해시는 암호화 기법중 한가지이다. 그래서 원래 정보를 잘 숨겨야 하는데 이를 엉망으로 만들어 알아 볼 수 없게 만든다면 보다 암호화 하는데 용이할 것이다. 간결하게 해시를 표현한다면 ..