공부하는 개발자의 스토리

https://leetcode.com/problems/maximum-subarray/ 위의 문제는 전체 배열에서의 최대 부분합을 구하는 문제이다. Brute Force 방식으로 문제를 어렵지 않게 해결할 수 있지만, 카데인 알고리즘을 이용하면 O(N)으로 문제를 해결할 수 있다. 문제 예시 주어진 배열 A를 [1,-2,3,5,-4,2,5] 라고 했을 때,Maximum Subarray는 [3,5,-4,2,5] 이며, 결과값은 부분 배열의 합인 11 이다. Brute Force : O(N²) Brute Force 방식은 가능한 모든 부분 배열의 합을 구하고 이에 대한 최대값을 구하는 것이다. A[0]부터 시작해서 A[0]에서 가질 수 있는 모든 부분합을 구한다. 이 과정을 A[1], A[2], A[3] …...

Union-Find 알고리즘이란? Union-Find 알고리즘은 그래프 알고리즘 중 하나로 서로소 집합, 상호배타적 집합(Disjoint-Set)알고리즘이라고도 불린다. 여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. Union-Find 과정 1) Init for(int i = 0; i < parent.length; i++) parent[i] = i; 초기화. 최초 노드는 자기자신을 루트노드로 가진다. 1) Find(x) // x가 속한 그래프의 루트 노드를 반환 static int find(int x) { // x의 루트노드가 x일 경우. 즉, x와 연결된 노드가 없을 경우. if(x == parent[x]) return x; // 재귀를 이용해 부모노드 ..