알고리즘

알고리즘 학습법

  수학공부하듯이 이해와 암기를 병행해야한다. 어떤 개념의 논리와 증명을 이해했다면 그 개념을 활용하는 규칙을 외우고, 공식을 외운 상태에서 바로 꺼내어 쓸 수 있어야 응용문제를 풀수 있다. 이차방정식 근의 공식을 매번 유도하여 사용하는 것이 아니라 외워서 사용하듯이. 외우는 것이 이해하는 것만큼 중요하다.

 

정렬 Sorting

• Selection Sort
  • repeatedly selecting the smallest (or largest, depending on the sorting order) element from the unsorted portion of the array and moving it to the beginning of the sorted portion. O(n^2)

• Bubble Sort
  • repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. O(n^2)

• Insertion Sort
  • It repeatedly takes an element from the unsorted portion of the array and inserts it into its correct position in the sorted portion of the array. The insertion sort algorithm is similar to how people sort playing cards in their hands.

• Merge Sort
  • a divide-and-conquer sorting algorithm that divides the input array into smaller subarrays, sorts each subarray recursively, and then merges the sorted subarrays to produce the final sorted array. O(nlogn)

 

• Direct Access Array Sort
  
  • if we are not limited to comparison operations, it is possible to beat the Ω(n log n) bound
  • Construct a direct access array with size u and insert each item x into index x.key. Then simply read through the direct access array from left to right returning items as they are found
    
    • Inserting input Θ(n) + scanning the array Θ(u) time. (u is the biggest input possible)
  • For the variation, we have Tuple sort, Radix sort, Counting sort.
• Java의 Sorting method
  • Arrays.sort(T[] a, Comparator<? super T> c), Collections.sort(Object, Comparator<? super T> c)
    
    • 정렬시에는 1. 정렬의 대상(object)와 정렬의 기준(compartor interface)이 필요하다. 정렬기준을 제시하지 않으면 디폴트 정렬기준인 comparable인터페이스의 compareTo 메소드를 기준으로 정렬한다. 반면 Comparator 인터페이스는 개발자가 직접 정의하는 클래스로 compare이라는 추상메소드가 구현되어야한다.
    • Comparator : 인터페이스(추상클래스)로써 compare 메소드를 커스컴 정의하여 Obj1 Obj2 비교하여 -1, 0, 1 을 반환하여 0은 같음, -1은 작음, 1은 큼을 나타냄

List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());

list.sort(new Comparator<Map.Entry<Integer, Integer>>() {
    @Override
    public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
        if (o1.getValue() > o2.getValue()) {
            return -1;
        } else if (o1.getValue() == o2.getValue()) {
            if (o1.getKey() <= o2.getKey()) {
                return -1;
            } else {
                return 1;
            }
        } else {
            return 1;
        }
    }
});

 

• 주로 comparator는 람다식을 활용하여 간단히 클래스를 정의하기도 한다.
• Comparator.naturalOrder, Comparator.natural

이진탐색

• 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법
  1. 왼쪽 bound를 lt, 오른쪽 bound를 rt 데이터 중앙값을 mid로 하고, 찾고자 하는 target값과  mid 값을 비교
  2. target값이 mid 값보다 더 작으면 오른쪽을 날리고 (rt=mid-1) 데이터 왼쪽 부분에서 이진 탐색
  3. target값이 mid 값보다 더 크면  왼쪽을 날리고 (lt=mid+1)데이터 오른쪽 부분에서 이진 탐색
  4. target값과 mid 값이 일치하면 이를 반환함.
  5. 이를 반복하게되면 최종적으로 lt=rt가 되는 한점으로 수렴하게 됨 {while (lt<=rt)이면 lt=rt}

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid;  // Element found
        } else if (arr[mid] < target) {
            left = mid + 1;  // Search right half
        } else {
            right = mid - 1;  // Search left half
        }
    }

    return -1;  // Element not found
}

• LowerBound Search : 이진탐색의 변형으로, 범위 내에서 target값이 존재하지 않을 경우 target 값보다 작지만 가장 근접한 값을 반환. input값에 비례 혹은 반비례하는 판별식을 보유해야함.
  1. 왼쪽 bound를 lt, 오른쪽 bound를 rt 데이터 중앙값을 mid로 하고, 비례 function에 mid값을 넣고 true/false를 확인한다.
  2. 비례 function이 false이면 왼쪽 값을 버림
  3. 비례 function이 true이면 res를 임시 저장하고 최소값을 찾기 위해서 오른쪽을 버림
     • 이는 중요한 것이 lt=rt=mid인 값이라고 꼭 최소값이라는 보장이 없다. 일반 이진탐색과 달리, 최소값 -1에서 수렴할 수 있음. 때문에, res값을 임시저장한다.
  4. while loop가 끝나면 res 값을 반환한다.

while (lt <= rt) {
    int mid = (lt + rt) / 2;
    if (citations[citations.length - mid] >= mid) {
        res = mid;
        lt = mid + 1;
    } else if (citations[citations.length - mid] < mid) {
        rt = mid - 1;
    }

• 결정알고리즘 적용근거
  • 1. 정답의 시작값과 끝값을 알고있음. 어떤 문제에서 답이 확실히 주어진 범위 내에 있겟다는 확신이 든다면, 이진탐색을 시도해봐야함.
  • 2. 답이 특정 parameter을 넣었을때 양의 상관관계이거나 음의 상관관계를 일정하게 유지할 경우 (monotonic property)
    • 부정방정식 형태의 문제가 주어질때, 이진탐색을 사용하면 효율적이다. 타겟값인 f(x)와 x간의 관계가 양의 상관관계인지 양의 상관관계인지 확인후 이진탐색으로 범위를 줄여나가는 방법을 사용하자.

 

점화식과 재귀함수

• 점화식 : 어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식
• 재귀함수 : 함수 내에서 자기자신을 호출하는 함수, 코드 내에 자기자신을 호출하는 점화식 구조를 가지고 있음 (A(n+1) = A(n) + alpha). 
  • PS관점에서는 반복문의 대체재이며, 복잡한 반복문의 코드 유연성과 가독성을 확보할 수 있음. 단, 함수반복의 종료시점에 대해서 정의를 해주어야함.
  • 재귀함수는 스택자료구조를 활용, 코드의 호출 순서대로 call 된 코드가 쌓이며 차례대로 연산되는 구조.
  • 1부터 N까지 출력하는 함수
    • def f(n) : if n >0 / print(n) / f(n-1)
  •  피보나치 재귀함수 구현
    • def fib(n): if n==1 or n==2: / return 1 /else: /return fib(n-1) + fib(n-2)
  •  피보나치 반복문 구현
    • def fib(n): a,b = 1,1 / if n==1 or n==2: / return 1 / for i in range(1,n):/ a,b = b, a+b / return a

 

Dynamic Programming

• 동적 계획법은  최적 부분 구조(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제해결방식
  • 하향접근법(메모이제이션과 재귀함수) : 재귀함수를 사용하여 n=15에서 n=1로 내려가는 방식
  • 상향접근법 :  함수의 output을 메모리에 일시 저장하여 다음 함수의 input으로 재활용
• 다이나믹 프로그래밍은 아래의 조건에서 적용가능하다
  • 1. 최적부분구조
    • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 해결할 수 있다
    • 분할정복문제이나 다이나믹프로그래밍은 모두 최적부분를 갖고 있으며 차이점은 부분문제가 중복적으로 나타나면 다이나믹프로그래밍 문제이다.
  • 2. 중복되는 부분문제
    • 동일한 작은문제를 반복적으로 해결해야한다.
• 다이나믹 프로그래밍 판별법
  • 우선, 그리디, 구현, 완전탐색으로 문제를 풀어보고 풀이방법이 마땅하지 않다면 다이나믹 프로그래밍을 적용해본다. 재귀함수로 비효율적인 완전탐색을 구현한 후에 작은문제의 답이 큰문제의 답으로 적용가능한지 확인한다.