CS/알고리즘

[알고리즘/Java] 유니온 파인드(Union-Find)

※ 본문은 혼자 공부한 내용을 기록한 글입니다. 오개념이 있다면 반드시 댓글로 알려주세요! [ 1 ] 유니온 파인드(Union-Find)란? 유니온 파인드는 그래프에서 두 정점이 같은 집합에 속해 있는지 판별하는 알고리즘이다. 서로 연결되어 있지 않은 정점들도 판별할 수 있기에 서로소 집합(Disjoint-set) 이라고도 한다. 알고리즘 이름에 나와있듯이 특정 2개의 정점을 연결해 1개의 집합으로 묶는 union 연산(합집합)과 두 정점이 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있다. DFS로도 각 정점이 연결되어 있는지 확인할 수 있겠지만, 경로가 길거나 확인해야 할 테스트 케이스가 많다면 시간 제한이 걸릴 수 있으므로 긴 경로를 축소할 수 있는 유니온 파인드를 활용해보자. ①..

[알고리즘/Java] 슬라이딩 윈도우(Sliding Window)

[ 1 ] 기본내용 슬라이딩 윈도우는 이전에 포스팅한 투 포인터(Two Pointers) 알고리즘과 원리가 유사한 알고리즘이다. 투 포인터 알고리즘은 2개의 포인터를 활용하여 부분 배열의 길이를 유동적으로 활용하거나 2개의 특정 원소 값에만 접근하는 반면, 슬라이딩 윈도우는 부분 배열의 길이가 고정적이라는 특징이 있다. "한 정수 배열에서 길이가 3인 부분 배열 중 합이 가장 큰 부분 배열은 무엇인가?"라는 문제가 있다고 가정하자. - arr = [3, 5, 2, 1, 7, 4, 10, 6, 8, 9] 위 배열이 주어졌을 때 가장 큰 부분 배열의 합을 구하기 위해서 중첩 반복문을 활용할 수 있을 것이다. 하지만, 중첩 반복문을 활용할 경우 시간 복잡도가 O(N^2)이기 때문에 효율적이지 않다. 이때 슬라..

[알고리즘/Java] 투 포인터(Two Pointers)

[ 1 ] 기본내용 "투 포인터"는 1차원 배열에서 각기 다른 원소를 가리키는 2개의 포인터를 활용하여 원하는 값을 얻는 알고리즘이다. 이때, 포인터는 C/C++에서의 포인터가 아닌 배열에서의 "인덱스"를 의미한다. 2개의 포인터를 적절히 이동시키며 시간 복잡도를 최적화할 수 있는 것이 투 포인터 알고리즘의 핵심이다. 투 포인터가 자주 활용되는 문제로는 (1) target 값을 미리 설정하고, 특정 배열 내에 target 값과 같은 - 유사한 부분 합이 몇 개 존재하는지 계산하는 문제 (2) 배열 내 target = arr[i] + arr[j] 를 만족하는 (i, j) 쌍이 몇 개 존재하는지 계산하는 문제 등이 있다. [ 2 ] 부분 합에서의 투 포인터 해당 내용은 대표 예제인 백준 2003번을 통해 살..

[알고리즘/Java] 구간 합(Prefix Sum)과 관련 예제(BOJ-11659)

[ 1 ] 정수 배열 A에서 특정 구간(i ~ j) 내 모든 원소의 합을 구하라 특정 배열이 주어지고 위와 같은 질문을 받는다면, 우리는 어떻게 특정 구간 내 모든 원소의 합을 구할 수 있을까? 시간 제한이 없고 배열 원소의 수가 적다면 단순히 선형 탐색으로 i ~ j 까지의 특정 구간 내 원소의 합을 구할 수 있을 것이다. 하지만, 배열 내 원소의 수가 매우 많고, 계산해야 할 특정 구간도 많이 주어진다면 위와 같은 선형 탐색은 오랜 시간이 소요될 것이다. [ 2 ] 구간 합(Prefix Sum) [2 - 1] 정의 구간 합 알고리즘을 활용하면 선형 탐색으로 O(n)이 소요되던 시간 복잡도를 O(1)으로 줄일 수 있다. 어떻게 이것이 가능한가? 우선 A라는 정수 배열이 있을 때 S라는 '합 배열'을 정..