백준 문제 : (1717) 집합의 표현
알고리즘 : Union-Find

문제 정리

1. 집합 n+1개 ({0},{1},{2},…{n})
2. 첫 줄에 n과 m이 주어짐
3. n은 집합의 개수이며 m은 라인
4. 각 라인은 [0 1(a) 3(b)], [1 7 1]가 같이 3개의 숫자를 전달
5. 맨 앞의 숫자 0은 a와 b를 합치며 1은 두 집합이 같은 집합인지 판단하여 “YES, “NO”를 출력

Maximum Subarray

[Leetcode :: Maximum Subarray]
정수 배열 nums를 지정하면 합계가 가장 큰 연속적인 하위 배열(최소 1개를 포함)을 찾아 합계를 반환하십시오.

접근 방법

Brute Force

주어지는 배열은 A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]로 구성돼 있다.
문제를 보면 하나의 배열안에 하위 배열들의 합을 구하는 것이라 단순하게 생각해도 반복문 2개로 풀 수 있을 것이다. A[0]부터 시작되는 하위 배열들부터 A[1]~A[N-1]로 시작하는 하위 배열들의 합 중에서 제일 큰 걸 고르면 되는데 이렇게 작성을 하면 시간 복잡도는 O(n^2^)으로 너무 느려진다.