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

트라이는 문자열의 집합을 표현하는 트리 자료 구조로, 집합 내에서 원하는 원소를 찾는 작업을 O(M) 시간만에 할 수 있습니다. 문자열 집합 S={"BE", "BET", "BUS", "TEA", "TEN" }를 저장하는 트리의 예는 아래와 같습니다. 여기서 진한 노드들은 종료 노드들로 해당 위치에 대응되는 문자열이 트라이가 집합에 표현되어 있다는 것을 의미합니다. BE, BET 등을 나타내는 노드들은 종료 노드지만 TE의 경우에는 그렇지 않습니다. 트라이에서 중요한 점은 루트에서 한 노드까지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 접두사를 얻을 수 있습니다. 즉 각 노드별로 대응되는 문자열을 저장할 필요가 없습니다. 트라이의 한 노드는 자손 노드들을 가리키는 포인터 목록과 이 노드..

KMP 알고리즘을 배우기전 엄청 큰 문자열 더미에서 특정 문자열을 찾기 위해서는 아래와 같이 O(N*H)의 시간복잡도를 사용하여 찾았을 것이다. N은 찾을려는 문자열 H는 문자열 더미이다. for(int begin = 0; begin + N.size()

union-find(Disjoint-set) union-find(Disjoint-set)은 데이터들을 하나의 집합으로 묶어 표현할 필요가 있을 때 사용된다. 예를 들어 게임에서 하나의 파티를 표현하고 싶을 때 같은 1번 파티라는 것을 표현하기 위해 사용된다. 이와 같은 연산을 하기 위해서 필요한 3가지 연산이 있습니다. 1. 초기화(init): 초기에는 특별한 집합이 없는 자기 자신을 가리키는 초기화를 만듭니다. 2. 합치기(union): 두 원소 a와 b가 주어졌을 때 이 둘을 하나의 집합으로 만듭니다. 3. 찾기(find): 해당 원소가 어떤 집합에 속해있는지 찾습니다. 이러한 집합을 표현하는데 있어서 가장 쉬운 방법은 트리를 이용한 것입니다. 트리에서 한 집합에 속하는 원소들을 하나의 트리로 묶어줍..

가가오 문제 중 투포인터가 나왔다 필자는 투포인터라는 존재를 모른채 이진 탐색 문제인줄 알고 오지게 삽질하다가 못풀었다. 그래서 그 분노로 투포인터에 대해 공부하고 백준 문제 4문제 정도를 풀었다. 투 포인터는 이름 그대로 두개의 점을 사용하여 연속된 수의 집합의 합 및 개수들을 구할 수 있게 해준다. 여기서 주의 할 점은 연속된 집합이다. 시작은 start, end 둘다 첫 요소를 가리키며 시작한다. 목표하는 숫자에 비해 작으면 end를 계속 늘려가주며 더해준다. 그러다 목표하는 숫자에 비해 커지거나 같아지면 start요소의 값을 빼주고 start를 늘린다. 사실 글만 보면 어떤 느낌인지 느낌이 안올 것이다. 그래서 그림을 준비했다. 위 그림을 통해서도 알 수 있지만 크게 생각할 점은 두가지다. 집합의..

최단 경로(3) 벨만 포드 벨만포드는 다익스트라와 다르게 각 정점을 하나씩 제외하면서 우선순위 큐에 넣는 것이아닌 입력된 모든 path를 반복문 돌려서 최단 경로를 구할 수 있다. 또한 다른 알고리즘과 다르게 -가중치의 값또한 해결할 수 있다. 하지만 -가중치로 인한 계속 -가되는 -cycle이 생성될 수 있다. 그러므로 알고리즘을 작성한 후 -cycle이 존재하는지 체크해야할 필요가 있다. 그리고 다른 최단거리 알고리즘과 Relax 함수는 비슷하다. if(vertex[end] > vertex[start] + map[start][end]) vertex[end] = vertex[start] + map[start][end]; 초기 정점의 설정 값은 INF로 설정해준다. 만약 알고리즘을 돌다가 시작점이 INF..