매일 매일 성장하는 섭섭군

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

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

이번에 풀어볼 문제는 백준 6416번 '트리인가?'라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/6416 6416번: 트리인가? 문제 트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 �� www.acmicpc.net 이번 문제는 문제에서 제시한 트리를 만족하는 조건을 잘 구현해 주면 된다. 편의상 들어오는 간선은 부모 노드, 나가는 간선은 자식 노드라고 하겠습니다. (위의 제일 왼쪽 트리에서 5의 자식 노드 : 3,6,2 , 6의 부모노드 : 5 ) 1. 단 하나의 루트만 존재한다. -> 루트노드가 2개 이상 있으면 ..