1. 검색 트리 검색 트리는 링크드 리스트나 큐처럼 자료들을 담는 컨테이너지만, 자료들을 일정한 순서에 따라 정렬한 상태로 저장해둔다. 이것은 입력이 주어진 순서에 따라 자료들을 배치하는 리스트나 큐와 다른 속성이다. 이런 속성은 원소의 추가 와 삭제만이 아니라 특정 원소의 존재 여부 확인 등의 다양한 연산을 빠르게 할 수 있다. 이진 검색트리는 특히 아주 널리 사용되기 때문에, 이들의 동작 원리와 장단점은 알아야한다. 대부분 이진 검색트리는 라이브러리에서 제공한다. 2. 이진 검색 트리 이진 트리(binary tree) 란 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리를 의미한다. 따라서, 이진 트리는 자식 노드들의 배열 대신 두 개의 포인터 left 와 right를 담는 ..

1. 트리 트리는 계층 관계를 갖는 객체들을 표현하기 위해 만들어진 자료 구조이다. 계층 관계표현 이외도 다른 구조보다 같은 연산을 더 빠르게 할 수 있다. (특히 탐색형 자료 구조) 탐색형 트리 자료구조의 유명한 이진 검색 트리는 모든 숫자에 최대 두개의 하위 숫자만 있으며 어떤 숫자에서든 왼쪽 가지를 따라 내려가면 더 작은 수를 오른쪽 가지를 따라 내려가면 더 큰 수를 만날 수 있다. 이와 같은 특별한 규칙에 의해 탐색을 lgn만에 할 수 있게 된다. 트리의 구성 요소 노드 node: 연결된 노드 간에는 상하위 관계가 있다. 간선 edge: 연결하는 선 상위 노드 parent 하위 노드 child 부모가 같은 노드 sibling 부모 노드와 그의 부모 노드들 ancestor 자식 노드와 그의 자식 노..

1. 트리 생성 이 문제는 외벽안의 성벽들을 트리로 나타낸다음 각 잎에서 잎까지의 경로가 가장 긴 거리를 구하는 문제이다. 따라서 일단 주어진 성벽들의 정보를 가지고 트리를 구성해야한다. 이 트리를 생성하는데 약 n*n*n 이 걸릴 것 같다. 1. 서로 비교하여 노드의 벡터에 포함되어있는것을 넣는다 -> 두개를 비교하니 n*(n-1)/2 2. 각 비교할때마다 부모노드에서 자식노드벡터를 제거해야한다 -> n(점점 작아진다 생각보다 빨리 실행될 것이다) 3. 넣은것들 또한 트리로 정리해야하므로 남은 것들을 재귀호출해야한다. -> n 2번은 총 n(n-1)/2 번 실행될것이고 , 1번 또한 n(n-1)/2 번 실행될것이니 대략 n^2만에 트리를 정리하여 서브 트리만 남겨놓는다. 서브트리를 재귀로 정리해야한다...

1. 트리의 순회 이 문제는 트리의 preorder와 inorder가 주어졌을 때 이 정보를 가지고 postorder을 생성하는 문제이다. preorder는 각 서브트리의 루트를 먼저 출력한다. 따라서 preord[0]은 이 트리의 루트가된다. inorder는 서브트리의 왼쪽끝쪽을 조사한다음 서브트리의 루트를 출력한다음 오른쪽을 조사한다. 즉, 트리의 루트가 출력될때 이미 이 루트의 왼쪽 부분은 탐색을 마친 상태이다. 트리의 루트의 오른쪽은 오른쪽 서브 트리이다. 위의 각 순회의 특성을 이용하여 재귀적으로 함수를 구현하면 답을 쉽게 얻을 수 있다. 이 코드의 시간복잡도는 r 과 for문에 지배된다 for문은 각 단계에서 대략 n번 수행되고 r = n이므로 O(N^2)의 시간 복잡도를 가진다. 1 2 3 ..

1. 완전 탐색 이 문제는 주어진 문자열 입력에 대해 중복된 부분 문자열의 개수를 센다음 k개 이상의 중복 문자열 중에서 가장 긴 부분 문자열을 찾는 문제이다. 하지만 부분 문자열을 전부 만들어서 카운트하면 시간안에 수행이 불가능하다. 2. 공통 접두사의 최대 길이 사용 접미사 배열을 만들고 공통 접두사의 최대 길이를 계산하면 시간안에 해결할 수 있다. 이 때 중요한 것은 k개를 더한것과 비교하는 것이다. 이는 k번째 접미사와 접두사가 일치하지않으면 0이되기 때문에 이는 완활히 작동된다. 다음은 책에있는 코드이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39..

1. 문자열 이 문제는 KMP알고리즘을 사용하면 간단하게 풀 수 있다. 아래 코드는 좀 복잡하게 구현하였는데, 사실 첫 상태와 비교하는게 아니라 이전 상태랑 비교하면 더 깔끔한 코드가 될 것이다. 또한 A를 시계방향으로 i만큼 돌린 결과가 B일때 이는 B를 반시계방향으로 i만큼 돌린 결과가 A라는 것을 이용하면 더 직관적 일 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include #include #include usi..