Algorithm - 1주차

1. 삽입정렬 / 머지정렬 / 퀵정렬을 구현하고, 아래의 데이터를 만들어서 시간 비교를 해주세요
 1. 1~1000만까지 순서대로 숫자가 저장된 배열

public class algorithm1 {
    
    private static void insertion_sort(int[] a, int size) {
		for(int i = 1; i < size; i++) { //i가 1인 이유는 삽입정렬에서 첫번째 타겟은 두번째 원소부터 시작하기 때문
			int target = a[i]; 
			int j = i - 1; 
			while(j >= 0 && target < a[j]) { // 타겟이 이전 원소보다 크기 전 까지 반복
				a[j + 1] = a[j];	// 이전 원소를 한칸씩 뒤로 
				j--; 
			}
            //위 반복문이 끝났을 때 j인덱스보다 타겟이 작다는 의미
            //그러므로 타겟은 j인덱스 뒤에 와야한다. 그러므로 타겟은 j + 1 에 위치
			a[j + 1] = target;	
		}
    }

        public static void main(String[] args) {
        final int max = 10000000;
        int[] data = new int[max];
        for(int i=0;i<max;i++){
            data[i] = max-i;    
        }
        long beforeTime = System.currentTimeMillis();
                
        insertion_sort(data, max);
                
        long afterTime = System.currentTimeMillis(); 
        long secDiffTime = (afterTime - beforeTime)/1000; 
        System.out.println("시간차이(m) : "+secDiffTime);
       


    }
}

 

2. Priority Queue와 Heap정렬에 대해서 조사해 주세요 추가적으로 힙정렬이 다른정렬에 비해 가지는 장점이 있는지도조사해 주세요

우선순위 큐는 일반 큐와 마찬가지로 First In First Out, 즉 선입선출 구조를 가지는데,
허나 일반 큐와 다른점은 우선순위를 먼저 정해두고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.
우선순위는 값을 비교해야하므로 null 값을 허용하지 않으며 내부 구조는 이진트리로 되어있다.
힙이란 최댓값/최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조이다
최대 힙은 부모노드의 값이 자식노드의 값보다 항상 큰 힙이며
최소 힙은 부모노드의 값이 자식노드의 값보다 항상 작은 힙이다

알고리즘 {
1. 부모노드와 자식노드들을 비교하여 만약 자식노드가 부모노드보다
   값이 클 경우 자리를 교환한다.
2. 최종적으로 만들어진 최대 힙을 가지고 정렬작업을 시작한다.
3. 최상단의 값을 아래로 내리고 위로 올라간 값이 최대힙 구조에
맞도록 정리하는 작업을 반복적으로 진행
}

3. 힙정렬 PDF의 4번째 슬라이드의 트리를 최소힙을 기준으로 다시 그려보세요

4. 카운팅 정렬과 기수정렬이 가자 효율적인 경우는 언제일까요? 그리고 제한되는 부분은 어느경우일까요?
   데이터를 예를들어 설명해주시고, 가장 효율적인 경우의 복잡도에 대해 말씀해주세요

카운팅정렬은 각 요소의 배열 등장횟수를 카운트하여 누적합으로 나타내는 배열을 만든 후 요소들의 index를 알아내 작은 순으로 정렬하는 기법이다. 모든 요소를 서로 비교하는 정렬이 아니기 때문에 O(n+k) 시간 복잡도를 가진다. n+k는 n또는k라는 의미

k는 요소의 최댓값인데 k가 작은 수일 경우 O(n)의 시간복잡도를 가진다. 하지만 k가 무한으로 커질때는 O(k무한)이 될 수 있다.

결론적으로 카운팅정렬은 요소의 최댓값에 영향을 받는 알고리즘이며  input요소의 값 k가 작은 수일때 효율적인 경우이다.

 

기수정렬은 0, 10, 100 등 0의 n개 자리수를 기준으로 정렬하는 기법이다.

이또한 O(n) 시간복잡도를 가지는 대신 자료형이 일정해야 하고 양수 음수를 각각 따로 비교해줘야하는 조건이 있어 제약적이다.

또한 제자리 정렬이 아니라 메모리를 따로 할당 받아서 사용하기 때문에 추가적인 메모리 공간이 필요하다.

 

5. 2D Peak Finder를 구현해주세요

public int peakFinding(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }