Soony's House

💡유니온 파인드(Union-Find)란 여러 개의 원소가 있을 때, 이들이 같은 그룹(집합)에 속해있는지 확인하고, 두 그룹을 합치는 연산을 빠르게 수행할 수 있도록 도와주는 알고리즘이다. 서로소 집합, 상호배타적 집합(Disjoint-Set)알고리즘이라고도 불린다고 한다. 유니온 파인드를한마디로 다시 정리하면여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이라고 할 수 있다. 💡Find( ) 와 Union ( ) 여러 노드가 주어진다고 할 때, 이들이 cycle로 연결되어 있는지 확인하는 기본 코드를 통해 살펴보자. 1. Find ( a ): X 가 속한 집합의 대표(루트 노드)를 찾는다.즉 부모를 찾고, 부모노드의 부모와 곂칠 경우 경로압축을 한다...

슬라이딩 윈도우(Sliding Window)고정된 사이즈의 윈도우(창)이 배열 안을 이동하면서 윈도우 내에 담은 데이터를 이용해 문제를 푸는 알고리즘.차이가 나는 양쪽 끝 원소를 갱신한다.슬라이딩 윈도우는 항상 구간의 너비가 고정되어 주어진다. 만약, 윈도우의 크기가 3일 경우 sw[0] = arr[0] + arr[1] + arr[2]...sw[n] = sw[n-1] - arr[n-1] + arr[n-1+(윈도우크기)] 예제 Q. 연속된 index n개의 합의 최소를 구하시오. 그리고 합이 최소일 때의 인덱스(a,b)를 구하시오.(a 1. sw배열에 모두 담고 최소값 구하는 방식import java.util.Scanner;public class Main { static Scanner sc..

누적합 (Prefix Sum) 누적합이란? 배열의 인덱스가 증가함에 따라 그 누적된 합을 미리 구해 놓는 것, '전처리' 라고도 함.arr배열을 일일히 for문으로 돌면서 합을 구하면 되는것 아닌가란 의문을 던질 수 있다. 하지만 이렇게 하면 시간복잡도 측면에서 성능이 저하된다. (테스트케이스에서 시간초과 문제가 발생하기도 함..) 그러므로 누적합을 미리 구하여 사용한다. 누적합 구현크기가 10인 arr 배열의 누적합을 구해보자 1. 누적합으로 [a] ~ [b] 의 합을 구하기. " acc [ b ] - acc [ a - 1 ] " 2. acc배열을 채우기인덱스 0 일때는 arr[0] 그 자체가 된다.그 이후부터는 acc[i] = acc[i-1] + arr[i] " acc[0]=..

피보나치 수열이란 수열이란 어떠한 공통된 규칙을 가진 숫자들의 열을 말한다.피보나치수열은 위 그림과 같이 n번째 수 = (n-1)번째 수 + (n-2)번째 수  형태의 규칙을 가지는 수열이다.(단, n=1or n=0 일때 1이며 위의 식은 n>=2부터 적용됨.)     그럼 이 수열은 코드로 어떻게 구현할 수 있을까.아래의 문제를 풀어보자. Q. 입력받는 숫자 하나가 수열의 인덱스값을 나타낸다고 가정할때, 해당 인덱스가 가리키는 값을 출력하는 코드를 만드시오. ex)입력: 5출력: 8 입력:1출력:1 입력:234출력:57239589  1. while문을 통한 구현    2. 출력값을 리턴하는 함수 만들어서 구현 (fibo함수 만들기) #include using namespace std;int fibo(i..