BLOG

이어지는 간선들을 하나의 집합으로 분류하고 서로소 집합들을 만드는 알고리즘이다. 

Disjoint Set이라고도 부른다.

핵심 함수

• find 함수 : 노드들의 부모를 찾는 과정, 어떤 집합에 포함되있는지 찾는다.
• union 함수 : 두 노드를 하나의 집합으로 묶는다.

https://www.acmicpc.net/problem/1717

public class Main {
    static int n, m, parent[];
 
    static int find(int x) {
        if (parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
 
    static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        parent[y] = x;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        parent = new int[n + 1];
 
        for (int i = 0; i <= n; i++)
            parent[i] = i;
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0, t, x, y; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            t = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            if (t == 0) {
                union(x, y);
            } else {
                sb.append(find(x) == find(y) ? "YES" : "NO").append("\n");
            }
        }
 
        System.out.println(sb);
 
        br.close();
    }
}

간과했던 부분 ( line : 38 )

두 노드가 같은 집합인지 확인할 때, find 함수를 통해 찾는다면 재귀를 다시 사용해야 했기 떄문에 불필요하다고 생각했고, parent 배열을 확인하여 O(1) 만에 같은 집합인지 알 수 있을 것이라고 생각했다. 

3 3
0 2 3
0 1 2
1 1 3

하지만 이러한 반례의 경우, 3의 부모는 2가 될 것이고, 2의 부모는 1이 될 것이다. 노드 1, 2, 3은 같은 집합이지만 1과 3노드가 같은 집합인지 확인할 경우 parent 배열에 다른 값이 들어 가있는 상태이고, 같은 집합임에 불구하고 NO를 출력했던 것이다. 따라서 같은 집합인지 확인하기 전 find를 호출하여 다시 루트노드까지 가는 과정을 통해 parent 배열을 최신화해주는 것을 통해 해결할 수 있었다.

이진탐색의 응용버전

최적화문제 = 이진탐색 + 결정문제(YES/NO)

설명 : 범위의 중간값을 해(x)로 설정하고 조건을 판별하면서 찾아야할 범위를 반씩 줄여나간다.

시간복잡도 : log N

https://www.acmicpc.net/problem/2110

1. 초기값으로 최소, 최대거리 설정

2. 중간값 (mid) 를 해 (x)로 하여 조건과 부합하는지 판별

3. 

1. 공유기 설치 개수가 목표 C 같거나 크다면 이제 문제에서는 공유기 사이의 거리의 최대값을 요구하기 때문에 목표 거리를 늘려준다.  =>  left = mid+1
2. 공유기 설치 개수가 목표 C보다 작다면 공유기 사이 거리값을 줄여주면 더 많은 공유기를 설치할 수 있기 때문에 거리를 줄여준다. => right = mid-1

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        int[] loc = new int[N];

        for (int i = 0; i < N; i++)
            loc[i] = Integer.parseInt(br.readLine());

        Arrays.sort(loc);

        int left = 1, right = loc[N - 1] - loc[0];
        int ans = 0;

        while (left <= right) {
            int mid = (left + right) / 2; // x
            int cnt = 1;
            int cur = loc[0];
            for (int i = 1; i < N; i++) {
                if (loc[i] - cur >= mid) {
                    cnt++;
                    cur = loc[i];
                }
            }
            if (C <= cnt) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        System.out.println(ans);

        br.close();
    }
}

퀵 정렬과 합병 정렬은 리스트를 분할하고 정복하는 방법으로 정렬한다.

이 두 가지 정렬은 특징은 다음과 같다.

퀵 정렬 : 평균 복잡도는 O(NlogN) 이지만 최악의 복잡도는 O(N^2)이다.

합병 정렬 : 시간 복잡도는 O(NlogN)을 보장한다. 하지만 정렬을 하기 위해서 임시 배열을 사용하기 때문에

추가적인 메모리가 필요하다.

[C++]

#include <iostream>
using namespace std;

// 병합정렬 특 : 추가적인 메모리를 요구함
int size = 8;
int sorted[8]; // 정렬 배열은 무조건 전역 변수로 선언

void merge(int a[], int m, int middle, int n) {
  int i = m;
  int j = middle + 1;
  int k = m;
  // 작은 순서대로 배열에 삽입
  while (i <= middle && j <= n) {
    if (a[i] <= a[j]) {
      sorted[k] = a[i++];
    } else {
      sorted[k] = a[j++];
    }
    k++;
  }
  // 남은 데이터도 삽입
  if (i > middle) { // i가 먼저 끝남
    for (int t = j; t <= n; t++)
      sorted[k++] = a[t];
  } else {
    for (int t = i; t <= middle; t++)
      sorted[k++] = a[t];
  }
  // 정렬된 데이터를 실제 배열로 삽입
  for (int t = m; t <= n; t++)
    a[t] = sorted[t];
}

// IDEA : 일단 정확히 반으로 나누고 나중에 정렬
void mergeSort(int a[], int m, int n) {
  // 크기가 1보다 큰 경우
  if (m < n) {
    int middle = (m + n) / 2;
    mergeSort(a, m, middle);
    mergeSort(a, middle + 1, n);
    merge(a, m, middle, n);
  }
}

int main(void) {
  int arr[size] = {7, 6, 5, 8, 3, 5, 9, 1};
  mergeSort(arr, 0, size - 1);
  for (int i = 0; i < size; i++)
    cout << arr[i] << " ";
  return 0;
}

[JAVA]

package MergeSort;

public class MergeSort {

    static void merge(int[] list, int left, int mid, int right, int size) {
        int[] storage = new int[size];
        int i = left;
        int j = mid + 1;
        int k = left;

        // 분할 정렬된 list 들의 합병
        while (i <= mid && j <= right) {
            if (list[i] <= list[j])
                storage[k] = list[i++];
            else
                storage[k] = list[j++];
            k++;
        }

        // 선택받지 못한 값들을 차례대로 채워 넣는다
        if (i > mid) {
            for (int l = j; l <= right; l++)
                storage[k++] = list[l];
        } else {
            for (int l = i; l <= mid; l++)
                storage[k++] = list[l];
        }

        // 임시 배열에 저장된 값을 원래 배열로 옮김
        for (int l = left; l <= right; l++)
            list[l] = storage[l];
        
    }

    static void merge_sort(int[] list, int left, int right, int size) {
        if (left < right) {
            int mid = (left + right) / 2;
            merge_sort(list, left, mid, size); // 기준 왼쪽 정렬
            merge_sort(list, mid + 1, right, size); // 기준 오른쪽 정렬
            merge(list, left, mid, right, size); // 양쪽 정렬된 리스트를 합친다
        }
    }

    public static void main(String[] args) {
        int[] list = new int[10000];
        int[] clist = new int[10000];
        int size = list.length;
        
        // 역순으로 값을 넣는다.
        for(int i=0;i<size;i++) {
            list[i] = size-i;
            clist[i] = size-i;
        }
        
        // 병합 정렬 속도 측정
        long st = System.currentTimeMillis();
        merge_sort(list, 0, size - 1, size);
        long et = System.currentTimeMillis();
        System.out.println("mergesort time(nlogn) : "+(et-st));
        
        // 버블 정렬  측정
        st = System.currentTimeMillis();
        for(int i=0;i<size-1;i++) {
            for (int j = i+1; j < size; j++) {
                if(clist[i]>clist[j]) {
                    int tmp = clist[j];
                    clist[j] = clist[i];
                    clist[i] = tmp;
                }
            }
        }
        
        et = System.currentTimeMillis();
        System.out.println("bubble sort time(n^2) : "+(et-st));

    }

}

Merge Sort(NlogN)  vs Bubble Sort(N^2)  속도 비교

배열 사이즈를 동적으로 바꿔가면서 배열의 값들을 역순으로 넣고 비교했다.

사이즈가 적을 때는 버블 소트가 속도가 확실히 빠르지만, 충분히 큰 사이즈를 넣어줬을 때 부터는 

병합 정렬이 확실히 빨랐다.

https://www.youtube.com/watch?v=YJ-OUnZu7nQ&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=9

문자열 검색을 하는 가장 기본적인 방법은 pattern(len : M) 문자열을 target(len : N) 문자열 각 인덱스마다 각각 하나씩 확인하는 방법이다. 이 경우 시간복잡도는 N(NM)이 된다.

하지만 KMP 알고리즘을 이용하면 시간 복잡도 O(N+M)으로 엄청나게 효율적으로 문자열을 찾을 수 있다고 한다.

import java.util.Arrays;

class KMP {

    static int[] makeTable(char[] p) {
        int psize = p.length;
        int[] table = new int[psize];
        int j = 0;
        for (int i = 1; i < psize; i++) {
            while (j > 0 && p[i] != p[j]) {
                j = table[j - 1];
            }
            if (p[i] == p[j]) {
                table[i] = ++j;
            }
        }
        return table;
    }

    static void kmp(char[] parent, char[] pattern) {
        int[] table = makeTable(pattern);
        int parentSize = parent.length;
        int patternSize = pattern.length;
        int j = 0;
        for (int i = 0; i < parentSize; i++) {
            while (j > 0 && parent[i] != pattern[j]) {
                j = table[j - 1];
            }
            if (parent[i] == pattern[j]) {
                if (j == patternSize - 1) {
                    System.out.printf("%d. \n", i - patternSize + 1);
                    j = table[j];
                } else {
                    j++;
                }
            }
        }
    }

    public static void main(String[] args) {
        char[] parent = "ababacabacaabacaaba".toCharArray();
        char[] pattern = "abacaaba".toCharArray();
        System.out.println("target : " + Arrays.toString(parent));
        System.out.println("pattern : " + Arrays.toString(pattern));
        kmp(parent, pattern);
    }

}

 

 

https://blog.naver.com/ndb796/221240660061

https://bowbowbow.tistory.com/6

조건 : 탐색 전 배열이 정렬되야한다.

시간 복잡도 = log₂ N

"데이터의 수가 n일 때, 최악의 경우에 발생하는 비교연산의 횟수는?"

데이터의 수 n이 n/2, n/4, n/8 ... 줄어서 1이 될 때까지 비교연산을 한 번씩 진행하고, 마지막으로 n이 1일 때 비교연산을 한 번 더 진행하게 된다. 그리고 그것이 탐색 대상이 존재하지 않는 최악의 경우의 비교연산 횟수이다.

퀵 정렬 알고리즘은 병합 정렬과 마찬가지로 "분할 정복 (divede and conquer)"에 근거하여 만들어진 정렬 방법이다.

실제로 퀵 정렬 역시 정렬대상을 반씩 줄여나가는 과정을 포함한다.

시간복잡도

평균 - O(NlogN)

최악 - O(N^2)

퀵 정렬은 시간 복잡도가 O(NlogN)인 알고리즘이다. 하지만 데이터의 이동이 데이터의 비교에 비해 현저히 적게 일어나고, 별도의 메모리 공간을 요구하지 않으므로 동일한 빅-오를 갖는 다른 정렬 알고리즘 중에서 평균적으로 가장 빠른 정렬속도를 보이는 알고리즘이다.

[C++]

#include <bits/stdc++.h>

// 일반적으로 퀵정렬이 빠르다.
// 평균 복잡도 n log n, 최악 복잡도 n^2
// 언제 최악의 복잡도가 나올까? 정렬된 데이터를 정렬할 때 

// 기준 값  =  pivot
int data[] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
int number = 10;

void quickSort(int *data, int start, int end) {
  if (start >= end) { // 원소가 1개인 경우 (=)
    return;
  }
  int key = start; // 키는 첫번째 원소 , 피벗
  int i = start + 1;
  int j = end;
  int tmp;

  while (i <= j) {                 // 엇갈릴때까지
    while (data[i] <= data[key]) { // 키값보다 큰값을 만날때까지 오른쪽 이동
      i++;
    }
    while (data[j] >= data[key] &&
           j > start) { // 키 값보다 작은 값을 만날때까지
      j--;
    }
    if (i > j) { // 현재 엇갈린 상태면 키 값과 교체
      tmp = data[j];
      data[j] = data[key];
      data[key] = tmp;
    } else {
      tmp = data[j];
      data[j] = data[i];
      data[i] = tmp;
    }
  }

  quickSort(data, start, j - 1);
  quickSort(data, j + 1, end);
}

int main() {
  quickSort(data, 0, number - 1);
  for (int i = 0; i < number; i++) {
    printf("%d ", data[i]);
  }
  return 0;
}

[JAVA]

https://www.acmicpc.net/problem/1253

입력받은 모든 수들 중에서 자신을 제외한 두 수의 합이 자신과 같으면 좋은 수이다.

처음에는 인덱스 0~n-1을 돌면서 이중포문으로 두수의 합이 arr[인덱스]가 맞는지 확인을 했는데,

당연히 O(N^3) 입력값은 최대 2000 이였기 때문에 시간초과가 났다.

투포인터 알고리즘을 활용하여 문제를 풀 수 있었다.

while문을 돌때마다 left와 right 중 하나는 증감이 되기 때문에 최대 N번 수행된다.

시간복잡도는 O(N^2)으로 풀 수 있었다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr); // 정렬

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int left = 0, right = n - 1;
            int target = arr[i];
            while (left < right) {
                int cal = arr[left] + arr[right];
                if (cal < target) {
                    left++;
                } else if (cal > target) {
                    right--;
                } else {
                    if (i != left && i != right) { // 두 수가 자신과 같으면 안되기 때문에
                        cnt++;
                        break;
                    }
                    if (left == i)
                        left++;
                    if (right == i)
                        right--;
                }
            }
        }

        System.out.println(cnt);

        sc.close();
    }
}

https://www.acmicpc.net/problem/2605

학생들은 번호를 뽑고 자기가 선 위치에서 뽑은 번호 숫자만큼 앞으로 새치기?할 수 있다.

뽑은 숫자 n번 만큼 버블정렬하여 풀 수 있다고 생각했지만, 2개의 스택을 사용해서 풀어보았다.

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        Stack left = new Stack();
        Stack right = new Stack();

        for (int i = 1; i <= N; i++) {
            int num = sc.nextInt();

            for (int j = 0; j < num; j++) {
                right.push(left.pop());
            }

            left.push(i);

            while (!right.isEmpty()) {
                left.push(right.pop());
            }
        }

        while (!left.isEmpty()) {
            right.push(left.pop());
        }
        StringBuilder sb = new StringBuilder();
        while (!right.isEmpty()) {
            sb.append(right.pop() + " ");
        }
        
        System.out.println(sb.toString());
        sc.close();
    }
}