kkoon9

신장 트리? 스패닝 트리라고도 한다. 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프를 뜻한다. 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴(사이클이 존재하지 않음) 대표적인 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘이 존재한다. 크루스칼 알고리즘 그리디 알고리즘의 아이디어를 착안한 알고리즘 각 정점간의 가중치를 List 혹은 배열로 만든다. 모든 간선을 비용(가중치)을 오름차순으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다. (그리디 알고리즘의 성질) 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. ⇒ 사이클이 안 생기게 하려고 크루스칼 알고리즘은 간선의 개수가 E일..

다이나믹 프로그래밍 다이나믹 프로그래밍은 동적 계획법이라고 불리는 알고리즘 입력 크기가 작은 부분 문제들을 해결한 후에 해당 부분 문제의 결과값을 활용해서 보다 큰 크기의 부분 문제를 해결하고 최종적으로 전체 문제를 해결하는 알고리즘 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 Memoization 기법을 사용함. 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 예로, 피보나치 수열이 있음. 분할 정복 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을..

위상정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 결정해주는 그래프 정렬 알고리즘이다. 위상 정렬의 시간 복잡도는 **O(V + E)**로 문제를 해결할 수 있다. 위상 정렬은 DFS를 사용하여 구현하거나 indegree 배열을 사용하여 해결 가능하다. indegree란? 한 정점에서 자신에게 들어오는 방향인 간선의 수를 의미한다. 위 그래프를 예로 들어보자. 1번 정점 : 2 2번 정점 : 0 3번 정점 : 1 4번 정점 : 1 위상 정렬 알고리즘 간선의 정보를 받아 모든 정점의 indegree의 개수를 저장한다. indegree가 0인 정점을 큐에 삽입한다. 큐에서 원소를 꺼내 해당 원소와 간선을 제거한다. 제거 이후에 해당 indegree가 0이 된 정점을 큐에 삽입한다. 큐가 ..

교집합이 존재하지 않는 둘 이상의 집합을 말하고 데이터 집합을 다룰 때 유용하게 쓰인다. 트리 구조와 차이점 트리 구조는 부모 노드가 자식 노드를 가리키는 형태 분리 집합은 자식 노드가 부모 노드를 가리키는 형태 또한 교집합이 없는 집합이기 때문에 차집합은 의미가 없다. Union-find 알고리즘을 사용 비트 벡터, 배열, 연결 리스트를 이용하여 구현이 가능하나 트리 구조가 가장 효율적 분리 집합의 연산은 다음과 같다. make-set(x) 초기화 작업, x를 유일한 원소로 새로운 집합을 만든다. find(x) x가 속한 최상위 부모 노드(루트 노드)를 반환한다. union(x, y) x가 속한 집합과 y가 속한 집합을 합친다. (합집합) static int[] parent; // 유니온 파인드 루트 ..