기술 면접 - 알고리즘

1. 정렬

---

Bubble Sort

• n개의 원소를 가진 배열을 정렬할 때, 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식
• 가장 큰 값을 배열의 맨 끝에다 이동시키면서 정렬하고자 하는 원소의 개수만큼을 두 번 반복

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 4, 1};

        // 인접한 원소 끼리 비교해서 큰 값을 뒤로 밀어낸다
        // 한 번 반복할 때마다 끝에 수가 하나씩 확정됨
        for(int i = 0; i < arr.length - 1; i++) {
            for(int j = 0; j < arr.length - i - 1; j++) {
                if(arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }

        for(int num : arr)
            System.out.print(num + " ");
    }


    public static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

Selection Sort

• n개의 원소를 가진 배열을 정렬할 때, 계속해서 바꾸는 것이 아닌 비교하고 있는 값의 index를 저장해둠.
• 최종적으로 한번만 바꾼다 ( 버블 소트랑 다를건 없는 듯 )

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 4, 1};

          // 최소값의 인덱스를 찾아서 앞으로 넣어준다
        for(int i = 0; i < arr.length - 1; i++) {
            int minIdx = i;
            for(int j = i + 1; j < arr.length; j++) {
                if(arr[minIdx] > arr[j]) {
                    minIdx = j;
                }
            }
            swap(arr, i, minIdx);
        }

        for(int num : arr)
            System.out.print(num + " ");
    }

    public static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

Insertion Sort

• n 개의 원소를 가진 배열을 정렬할 때, i 번째를 정렬할 순서라고 가정하면, 0 부터 i-1 까지의 원소들은 정렬되어있다는 가정하에, i 번째 원소와 i-1 번째 원소부터 0 번째 원소까지 비교하면서 i 번째 원소가 비교하는 원소보다 클 경우 서로의 위치를 바꾸고, 작을 경우 위치를 바꾸지 않고 다음 순서의 원소와 비교하면서 정렬해준다. 이 과정을 정렬하려는 배열의 마지막 원소까지 반복해준다.

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 4, 1};
        int i, j;

        // 0 ~ i - 1까지는 정렬이 되어있음
        // i번째 원소를 정렬되어 있는 영역에 삽입한다
        for(i = 1; i < arr.length; i++) {
            int tmp = arr[i];

            for(j = i - 1; j >= 0; j--) {
                if(tmp > arr[j])
                    break;
                else
                    arr[j + 1] = arr[j];
            }
            arr[j + 1] = tmp;
        }

        for(int num : arr)
            System.out.print(num + " ");
    }


    public static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

Quick Sort

• 분할 정복을 이용한 빠른 정렬
• Divide 과정에서 pivot이라는 개념을 사용
• 입력된 배열에 대해 오름차순으로 정렬한다고 하면 이 pivot 을 기준으로 좌측은 pivot 으로 설정된 값보다 작은 값이 위치하고, 우측은 큰 값이 위치하도록 partition된다.

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 4, 1};

        myQuickSort(arr, 0, arr.length - 1);

        for(int num : arr)
            System.out.print(num + " ");
    }


    public static void myQuickSort(int[] arr, int left, int right) {
        if(left >= right)
            return;

        int pivot = partition(arr, left, right);

          // pivot 왼쪽에는 pivot보다 작은 수들만 있음, 걔들끼리 다시 정렬
        myQuickSort(arr, left, pivot - 1);
          // pivot 오른쪽에는 pivot보다 큰 수들만 있음, 걔들끼리 다시 정렬
        myQuickSort(arr, pivot + 1, right);
    }


    public static int partition(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
        swap(arr, left, mid);

        int pivot = arr[left];
        int i = left, j = right;

        while(i < j) {
            while(pivot <= arr[j])
                j--;
            while(i < j && pivot >= arr[i])
                i++;
            swap(arr, i, j);
        }

        arr[left] = arr[i];
        arr[i] = pivot;

        return i;
    }


    public static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

Merge Sort

• Merge Sort는 더이상 나누어지지 않을 때 까지 반 씩 분할하다가 더 이상 나누어지지 않은 경우(원소가 하나인 배열일 때)에는 자기 자신, 즉 원소 하나를 반환한다. 원소가 하나인 경우에는 정렬할 필요가 없기 때문이다. 이 때 반환한 값끼리 combine될 때, 비교가 이뤄지며, 비교 결과를 기반으로 정렬되어 임시 배열에 저장된다. 그리고 이 임시 배열에 저장된 순서를 합쳐진 값으로 반환한다. 실제 정렬은 나눈 것을 병합하는 과정에서 이뤄지는 것이다.

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 4, 1};

        myMergeSort(arr, 0, arr.length - 1);

        for(int num : arr)
            System.out.print(num + " ");
    }


    public static void myMergeSort(int[] arr, int left, int right) {
        if(left < right) {
            int mid = (left + right) / 2;

              // 왼쪽, 오른쪽으로 분할
            myMergeSort(arr, left, mid);
            myMergeSort(arr, mid + 1, right);

              // 병합을 진행하며 정렬시킨다
            merge(arr, left, mid, right);
        }
    }


    public static void merge(int[] arr, int left, int mid, int right) {
        int idx = left;
        int i = left, j = mid + 1;
        int[] tmp = new int[arr.length];

          // 왼쪽 배열과, 오른쪽 배열을 비교하며 임시배열에 작은 순서대로 넣는다
        while(i <= mid || j <= right) {
            if(j > right || (i <= mid && arr[i] < arr[j])) {
                tmp[idx++] = arr[i++];
            } else {
                tmp[idx++] = arr[j++];
            }
        }

        for(int s = left; s <= right; s++)
            arr[s] = tmp[s];
    }



    public static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

Sorting Algorithm's Complexity 정리

stable sort

• 정렬 알고리즘이 안전하다는 뜻은, 같은 값들을 정렬할 때 입력한 순서대로 출력된다는 것을 보장하는 것이다
• Heap Sort, Quick Sort는 빠르지만 안전하지 못하다
• 팀소트가 nlgn에 안전한 정렬이지만, 여기까지는 생략하겠음

2. 재귀

---

• 함수 내부에서 함수가 자기 자신을 호출하여 문제를 해결하는 알고리즘
• 계속해서 자신을 호출하는 구조이므로 함수를 끝내는 조건이 반드시 필요하다

public class Factorial {
    static int[] cache = new int[10];
    public static void main(String[] args) {
        System.out.println(loopFactorial(5));
        System.out.println(recurFactorial(5));
        System.out.println(dpFactorial(5));
    }

      // 반복문으로 풀이
    public static int loopFactorial(int n) {
        int ret = 1;
        for(int i = 1; i <= n; i++) {
            ret *= i;
        }

        return ret;
    }

      // 재귀함수로 풀이
    public static int recurFactorial(int n) {
        if(n == 1)
            return 1;

        return n * recurFactorial(n - 1);
    }


      // 재귀함수 + 메모이제이션 풀이
    public static int dpFactorial(int n) {
        if(n == 1)
            return 1;

        int ret = cache[n];
        if(ret != 0)
            return ret;

        return cache[n] = n * dpFactorial(n - 1);
    }
}

3. 수학

---

최대공약수, 최소공배수

// 유클리드 호제법
// 최소공배수 = (n1 * n2) / (n1과 n2의 최대공약수)

public class GCD_LCM {
    public static void main(String[] args) {
        System.out.println(gcd(8, 12));

        int LCM = (8 * 12) / gcd(8, 12);
        System.out.println(LCM);
    }


    public static int gcd(int a, int b) {
        if(b == 0) return a;
        return gcd(b, a % b);
    }
}

에라토스테네스의 체(소수 판별)

public class Eratosthenes {
    public static void main(String[] args) {
        int size = 1000;

          // prime[n] = false -> n은 소수가 아니다
        boolean[] prime = new boolean[size + 1];
        Arrays.fill(prime, true);

          // 1은 소수가 아니므로 미리 처리
        prime[1] = false;
        for(int i = 2; i <= size; i++) {
            if(prime[i]) {
                  // 2의 배수들, 3의 배수들.... i의 배수들까지 소수가 아니다!
                for(int j = i + i; j <= size; j += i)
                    prime[j] = false;
            }
        }

    }
}

4. 그래프 탐색

---

DFS

• 현 경로상의 노드들만 기억하면 되기 때문에 그래프의 높이 만큼의 공간만을 요구함, 최대 저장공간의 수요가 적다
• 해가 없는 경로에 빠질 가능성이 있고, 최단 경로가 된다는 보장이 없다
• 보통 그래프의 상태를 확인하기 위해 사용한다

public class Dfs {
    static ArrayList<ArrayList<Integer>> adj;
    static boolean[] visited;


    static void dfs(int cur) {
        visited[cur] = true;

        for(int next : adj.get(cur)) {
            if(!visited[next])
                dfs(next);
        }

    }

  // 모든 노드들을 탐색하기 위함
    static void dfsAll() {
        Arrays.fill(visited, false);
        for(int i = 0; i < adj.size(); i++)
            if(!visited[i])
                dfs(i);
    }
}

BFS

• 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장함
• 목표 노드가 깊은 단계에 있을 경우 오랜 시간이 소요되고, 공간 복잡도가 크다

public class Bfs {
    static ArrayList<ArrayList<Integer>> adj;
    static boolean[] discovered;


    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<Integer>()
        q.add(start);

        while(!q.isEmpty()) {
            int cur = q.poll();
            discovered[cur] = true;
            for(int next : adj.get(cur)) {
                if(!discovered[next]) {
                    q.add(next);
                    discovered[next] = true;
                }
            }
        }

    }
}

5. 이분 탐색

---

• 미리 배열을 정렬을 해야 사용할 수 있음
• binarySearch
  • 숫자가 중복되지 않는 배열에서 목표 숫자의 인덱스를 찾는다
  • O(lgN)
• upperBound
  • 숫자가 중복된 배열에서, 목표 숫자보다 큰 첫번째 인덱스를 찾는다
• lowerBound
  • 숫자가 중복된 배열에서, 목표 숫자의 첫번째 인덱스를 찾는다

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 3, 4, 4, 5, 6, 7};
        System.out.println(binarySearch(arr, 4));
        System.out.println(upperBound(arr, 4));
        System.out.println(lowerBound(arr, 4));
    }


    public static int binarySearch(int[] arr, int target) {
        int lo = 0, hi = arr.length;

        while(lo <= hi) {
            int mid = (lo + hi) / 2;

            if(arr[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return hi;
    }


    public static int upperBound(int[] arr, int target) {
        int lo = 0, hi = arr.length;

        while(lo < hi) {
            int mid = (lo + hi) / 2;

            if(arr[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }

        return hi;
    }


    public static int lowerBound(int[] arr, int target) {
        int lo = 0, hi = arr.length;

        while(lo < hi) {
            int mid = (lo + hi) / 2;

            if(arr[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }

        return hi;
    }
}

6. 허프만 코딩

---

• 입력 파일의 문자 빈도 수를 가지고 최소힙을 이용하여 파일을 압축하는 과정

고정 길이 코드(fixed length code) vs 접두어 코드(prefix code)

고정 길이 코드는 대표적으로 아스키 코드가 있다. 아스키 코드는 항상 8bit의 길이를 가지고있다. 다루기에는 간단하지만, 저장 공간 활용에 있어서 제한이 있다. 이를 해결하기 위해서 가변 길이 코드(variable length code)가 존재한다.

가변 길이 코드 중에서도 접두어 코드는, 앞서 나온 문자가 다음에 나올 문자의 접두어가 되면 안되는 특징을 가진 코드다. 예를 들면 다음은 접두어 코드가 아닌 예다.

a : 01
b : 101
c : 010

위 코드에서 01은 010의 접두어이기 때문에 접두어 코드가 아니다. 반면 다음은 접두어 코드의 예다.

a : 01
b : 10
c : 111

• abc -> 고정 길이 코드였다면 24비트, 접두어 코드 0110111, 7비트 굉장한 압축!

빈도 수가 높은 문자에는 짧은 이진코드(허프만 코드)를 부여하고, 빈도 수가 낮은 문자에는 긴 이진코드를 부여하여 압축 효율을 높인다.