백준 개미굴 14725 백준 개미굴 문제의 경우 전형적인 trie문제이다. trie이란 트리 구조를 활용하여 여러 개의 문자열 중 자신이 갖고 있는 문자열을 찾을 수 있는 알고리즘이다. hoony-gunputer.tistory.com/entry/%ED%8A%B8%EB%9D%BC%EC%9D%B4 트라이 트라이는 문자열의 집합을 표현하는 트리 자료 구조로, 집합 내에서 원하는 원소를 찾는 작업을 O(M) 시간만에 할 수 있습니다. 문자열 집합 S={"BE", "BET", "BUS", "TEA", "TEN" }를 저장하는 트리의 예는 hoony-gunputer.tistory.com 입력되는 문자열을 기준으로 layer을 구성해서 출력하는 문제이다. 이문제에서 체크해주어야 하는 상황은 몇가지가 있다. 1. 이 ..

문제는 아니고 이론이다. 특정한 트리가 주어졌을 때 이 트리가 이진탐색 트리의 조건에 만족하는지 만족하지 못하는지 체크하는 문제이다. 이진 탐색 트리를 만족하기 위해서는 부모의 노드 오른쪽에는 큰 값 왼쪽에는 작은 값이 위치하는 것을 체크해주면 된다. 하지만 이를 하나하나씩 다 체크해주면 확인하기에는 시간복잡도 부분에서 오래걸리게 된다. 따라서 O(n)만에 해결하는 방법을 작성해보려고 한다. 우선 아래 그림을 보자 해당 노드의 최대 값과 최소 값을 지정한 후 이 사이에 있다면 참이고 그 반대면 거짓이 된다. 참과 거짓을 밝히는 if문은 아래와 같다. if(minValue value) true; if(minValue > value || maxValue value valu..