알고리즘/알고리즘_theory (3) 썸네일형 리스트형 트리에서의 다이나믹 프로그래밍 기본적인 dp 문제에서 관점과 새로운 사고를 할 상황들이 많아지는 알고리즘인 것 같다. 수학적 개념이 부족하여 dp의 점화식과 일반항 도출이 어려웠는데 트리 dp에서도 비슷한 한계를 느낀다. 하지만 새로운 방법론과 사고 방법은 다른 알고리즘보다 재미있다. 관점과 다른 시각으로 트리를 보고 이용해야 한다는 점에서 더욱이 그렇다. 중등부 정 올 트리 dp 문제가 그러하다. 문제 자체에서는 o(n^2) 도 부분 점수를 보장하지만 만점을 받기 위해서는 특정한 규칙을 찾아야 한다는 흐름이 좋았다. 간선의 관점, 노드의 관점, 루트와 서브 트리의 관계 등등 생각이 많아지지만 이런 문제을 즐기게 된 게 얼마만인가. 노오오력! next level 유니온 파인드 유니온 파인드 서로서 집합(disjoint-set) 자료 구조, 또는 합집합을 만드는 연산 union과 같은 집합인지 찾는 (merge_find )로 이루어짐. 파인드(find) : 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. 재귀적인 구조로 "대표" 하는 원소를 찾고 두 원소가 같은 지를 판단함. 유니온(union) : 두 개의 집합을 합친다. ("대표" 와 "대표를 비교하여 하나의 "대표"를 저장) 기본 구조 단순 배열로 구현가능. 1~n까지 n개의 노드가 있다고 가정하면 각 노드의 값으로 저장될 배열을 하나 생성. parent [n] 원소 1 2 3 4 5 6 7 대표값 1 2 3 4 5 6 7 union 원소들의 대푯값을 하나로 만들어줘야 함. union(2,3) 원소 1 2 3 4.. 병합 정렬 병합 정렬 병합정렬(Merge Sort)은 퀵정렬과 비슷한 시간 복잡도(nlog(n))을 가진 것 처럼 보이지만 퀵정렬에서는 최악의 경우에 N^2 의 시간 복잡도가 발생할 수 있다. 병합 정렬은 최악의 경우도도 nlong(n)의 시간 복잡도를 보장한다. 병합 정렬은 "분할정복 방법"을 채택한 알고리즘으로 일단 "반으로 나누고 나중에 합쳐서 정렬하는 알고리즘 "이다 분할 과정 정렬되는 과정은 퀵정렬과 매우 유사하다. 합쳐지는 과정에서 정렬이 이루어 지는데 양쪽 시작점을 i 와 j 로 놓고 서로 비교하면서 임시 배열에다 저장한다. 그렇게 되면 배열의 길이만큼의 반복으로 정렬되는 새로운 배열을 얻을 수 있다. 합쳐지는 과정에서의 시간 복잡도는 N 이고 분할되는 시간복잡도는 logN이기 때문에 이 알고리즘의 시.. 이전 1 다음
