알고리즘 문제 해결 전략 : (2) 알고리즘 분석 - 시간 복잡도-2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 선택 정렬 -> 앞에서 하나씩 비교해 가면서 작으면 바꾼다.
 *  (N)(N-1)/2 = O(N^2)
 * @param li
 */
public void selectioonSort(ArrayList<Integer> li){
    for(int i = 0 ; i < li.size() ; i++){
        int minIndex = i;

        for(int j = i+1 ; j < li.size() ;j++){  //이번 루프중에서 가장 작은 수의 idx 찾기
            if(li.get(minIndex) > li.get(j)) {
                minIndex = j;
            }
        }
        swap(li, minIndex,i);
    }
}

/**
 * 삽입 정렬
 * 최선 : O(N) , 최악 : O(N^2)
 * 즉 거의 대부분의 경우 : 삽입정렬 > 선택정렬 (O(N^2) 정렬 중 가장 빠른 알고리즘)
 * @param li
 */
public void insertionSort(ArrayList<Integer> li){
    for(int i =0; i<li.size() ; i++){
        int j = i;
        while(j > 0 && li.get(j-1)>li.get(j)){
            swap(li, j-1,j);
            --j;    //이전에 있는 것들이랑 비교
        }
    }
}
/**
 * 어쩔수가 없이 ArrayList를 같이 줘야함 -> C 처럼 Call by Ref가 안된다..
 * 이럴땐 C가 그립다..
 * @param li
 * @param i
 * @param j
 */
private void swap(ArrayList<Integer> li ,int i, int j){
    int temp =0;
    temp = li.get(i);
    li.set(i,li.get(j));
    li.set(j, temp);

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int MIN =  Integer.MIN_VALUE;
/**
 * ** 최악 **
 * 묶어서 합한값의 MAX
 * O(N^3)
 * @param li
 * @return
 */
public int inefficientMaxSum(ArrayList<Integer> li){
    int N = li.size();
    int ret = MIN;
    for(int i=0; i<N; i++){
        for(int j=i; j<N;j++){
            int sum =0;
            for(int k = i; k<=j ;k++){
                sum += li.get(k);
            }
//                if(sum>ret) ret= sum;
            ret = Math.max(ret,sum);
        }
    }
    return ret;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int MIN =  Integer.MIN_VALUE;
/**
 * **좀더 좋음**
 * 묶어서 합한값의 MAX
 * O(N^2)
 * @param li
 * @return
 */
public int bettertMaxSum(ArrayList<Integer> li){
    int N = li.size();
    int ret = MIN;
    for(int i=0; i<N; i++){
        int sum =0;
        for(int j=i; j<N;j++){
            sum += li.get(j);
//                if(sum>ret) ret= sum;
            ret = Math.max(ret,sum);
        }
    }
    return ret;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * recursive, greedy 기법 사용
 * 반으로 나누고 좌,우,겹친 상황 을 비교함
 * O(NlogN) -> 반씩 나누면서 생각 log, 재귀 함수 불릴때마다(loop마다) N
 * @param li
 * @param lo 시작하는 idx
 * @param hi 마지막 idx
 * @return
 */
public int fastMaxSum(ArrayList<Integer> li, int lo, int hi){
    if(lo==hi) return li.get(lo);
    int mid = (lo+hi)/2; //중간값
    //왼쪽의 중 가장 큰 값
    int sum =0, left=0,right=0;
    for (int i =mid ; i>=lo;i--){
        sum += li.get(i);
        left = Math.max(sum,left);
    }
    sum=0; //init
    //오른쪽 가장 큰값
    for(int i=mid+1;i<=hi ;i++){
        sum += li.get(i);
        right = Math.max(right,sum);
    }
    //왼쪽 혹은 오른쪽 끼리 따로 계산 했을때 더큰 상황 -> 겹처지는 상황보다 독단적으로 계산할때 더 큰상황
    int single = Math.max(fastMaxSum(li, lo,mid), fastMaxSum(li, mid+1, hi));
    return Math.max(single, left+right);//left+right은 좌우 겹처서 계산할때 상황
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 점화식 생각 -> maxAt(i) = max(0, maxAt(i-1)) + A[i] (maxAt(li[i])은 0부터 i까지 중 최대합
 * 문제의 특성을 생각 : 이전까지 더한것이 음수면 버리고, 양수면 가져다가 쓴다, 결국 ret 값은 합한 비교해서 큰
 * O(N)
 * @param li
 * @return
 */
int fastestMaxSum(ArrayList<Integer> li){
    int N = li.size();
    int ret=0,presum = 0;

    for(int i =0; i<N; i++){
        presum = Math.max(presum,0) + li.get(i); //max(0,maxAt(i-1)) +A[i]
        ret = Math.max(presum,ret); //결과 : 이전값과 현재값 어떤게 더 큰지
    }
    return ret;
}