TIL 2022-12-06 (화)

최근에 TIL을 안썼는데 좀 몰아서 써야겠다. 공부는 하고 있지만 글을 남기는 것이 좀... 게을러서 힘들다. 저번에 간단한 정렬에 대해서 작성을 했었는데 이어서 작성하도록 하겠다.

재귀 용법

함수 안에서 동일한 함수를 다시 호출하는 방법이다.

//팩토리얼 함수
public class Factorial {
    public int factorialFunc(int n) {
        if (n > 1) {
            return n * this.factorialFunc(n - 1);
        } else {
            return 1;
        }
    }
}

재귀 용법에 대해서 말하면 항상 빠지지않고 등장하는 팩토리얼 함수이다.

동적 계획법

재귀 용법과는 달리 이미 계산한 결과는 저장을 해서 다시 계산하지 않도록 하는 방법이다.

public class Dynamic {
    public int dynamicFunc(int data){
        Integer[] cache = new Integer[data + 1];
        cache[0] = 0;
        cache[1] = 1;
        for(int index = 2; index < data +1; index++){
            cache[index] = cache[index -1] + cache[index -2];
        } 
        return cache[data];
    }
}

피보나치 함수를 구하는 예시를 가장많이 사용한다.

병합 정렬

재귀 용법을 이용한 정렬이다. 리스트를 이용해 두 부분 으로 나누고 정렬을 한다. 나뉜 리스트를 다시 재귀해서 또다시 나누고 정렬을 한다. 더 이상 나눌 수 없으면 다시 하나의 정렬된 리스트로 병합하는 방법이다.

public class MergeSort {
    public ArrayList<Integer> mergeFunc(ArrayList<Integer> leftList, ArrayList<Integer> rightList) {
        ArrayList<Integer> mergedList = new ArrayList<Integer>();
        int leftPoint = 0;
        int rightPoint = 0;

         // CASE1: left/right 둘 다 있을 때
        while (leftList.size() > leftPoint && rightList.size() > rightPoint) {
            if (leftList.get(leftPoint) > rightList.get(rightPoint)) {
                mergedList.add(rightList.get(rightPoint));
                rightPoint += 1;
            } else {
                mergedList.add(leftList.get(leftPoint));
                leftPoint += 1;
            }
        }

        // CASE2: right 데이터가 없을 때
        while (leftList.size() > leftPoint) {
            mergedList.add(leftList.get(leftPoint));
            leftPoint += 1;
        }

        // CASE3: left 데이터가 없을 때
        while (rightList.size() > rightPoint) {
            mergedList.add(rightList.get(rightPoint));
            rightPoint += 1;
        }

        return mergedList;
    }
    
    public ArrayList<Integer> mergeSplitFunc(ArrayList<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }
        int medium = dataList.size() / 2;  

        ArrayList<Integer> leftArr = new ArrayList<Integer>();
        ArrayList<Integer> rightArr = new ArrayList<Integer>();

        leftArr = this.mergeSplitFunc(new ArrayList<Integer>(dataList.subList(0, medium))); 
        rightArr = this.mergeSplitFunc(new ArrayList<Integer>(dataList.subList(medium, dataList.size()))); 

        return this.mergeFunc(leftArr, rightArr);
    }
    
}

퀵 정렬

기준점을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 정렬하는 방법
병합 정렬과 마찬가지로 재귀 용법을 사용해서 반복해서 작업을 시행하도록 한다.

// 기준점을 기준으로 큰 데이터와 작은 데이터를 나누는 함수
public class Split{
    public void splitFunc(ArrayList<Integer> dataList){
        if(dataList.size() < 1){
            return ;
        }
        int pivot = dataList.get(0);
        
        ArrayList<Integer> leftdata = new ArrayList<Integer>();
        ArrayList<Integer> rightdata = new ArrayList<Integer>();
        
        for (int index = 1 ; index < dataList.size() ; index++){
            if(dataList.get(index) < pivot){
                leftdata.add(dataList.get(index));
            } else {
                rightdata.add(dataList.get(index));
            }
        }
        
        ArrayList<Integer> mergedArr = new ArrayList<Integer>();
        
        mergedArr.addAll(leftdata);
        mergedArr.addAll(Arrays.asList(pivot));
        mergedArr.addAll(rightdata);
        
        System.out.println(mergedArr);
        
    }
}
// 퀵 정렬 알고리즘
public class QuickSort {
    public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }
        int pivot = dataList.get(0);
        
        ArrayList<Integer> leftArr = new ArrayList<Integer>();
        ArrayList<Integer> rightArr = new ArrayList<Integer>();        
        
        for (int index = 1; index < dataList.size(); index++) {
            if (dataList.get(index) > pivot) {
                rightArr.add(dataList.get(index));
            } else {
                leftArr.add(dataList.get(index));
            }
        }
        
        ArrayList<Integer> mergedArr = new ArrayList<Integer>();
        mergedArr.addAll(this.sort(leftArr));
        mergedArr.addAll(Arrays.asList(pivot));
        mergedArr.addAll(this.sort(rightArr));
        
        return mergedArr;        
    }
}

이전에 했던 정렬 방법보다는 상당히 복잡해지고 어려워졌다. 반복 학습을 통해서 더욱 더 연습해보는 것이 필요하다고 생각이 든다.