📅 2023년 12월 28일

[알고리즘 1일차]

32일차: 주요 알고리즘 (1)

Heap Sort

힙 정렬(heap sort)는 힙(heap)을 사용하여 정렬하는 알고리즘이다.
힙은 "부모의 값이 자식의 값보다 항상 크다 or 작다"라는 조건을 만족하는 완전이진트리.

• 장점
  빠르다.
  추가적인 배열이 필요하지 않다.

• 단점
  퀵이 평균적으로 더 빠르다.
  불안정 정렬이다.

public static void main(String[] args) {
	int[] HeapArr = {7,6,5,8,3,5,9,1,7};
	// 최소 힙구성 : n/2번만큼 heapify 수행
    for(int i = HeapArr.length/2-1; i>=0; i--){
		heapify(HeapArr, i, HeapArr.length);
	}
	System.out.println(Arrays.toString(HeapArr));
	// 최초 힙구성 이후에 root 노드와 마지막 노드와 change
	for(int i =HeapArr.length-1; i>0; i--){
		swap(HeapArr, 0, i);
		heapify(HeapArr, 0, i);
	}
	System.out.println(Arrays.toString(HeapArr));
}

static void heapify( int[] HeapArr, int root, int arr_size){
	int left = 2 * root + 1;
	int right = 2 * root + 2;
	int temp = root;
	if(left<arr_size && HeapArr[left] > HeapArr[temp]){
		temp = left;
	}
	if(right<arr_size && HeapArr[right] > HeapArr[temp]){
		temp = right;
	}
	if(temp != root){
		swap(HeapArr, root, temp);
		heapify(HeapArr, temp, arr_size);
	}
}
static void swap(int[] HeapArr, int x, int y){
	int num = HeapArr[x];
	HeapArr[x] = HeapArr[y];
	HeapArr[y] = num;
}

프로그래머스 문제 : 더 맵게
프로그래머스 문제 : 디스크 컨트롤러
프로그래머스 문제 : 이중 우선순위큐

완전 탐색 : DFS (깊이 우선 탐색)

public class DFS_ListGraph {
    static List<List<Integer>> list = new ArrayList<>();
    static boolean[] visited;
    public static void main(String[] args) {
        int [][] input =  {
                {0,1},
                {0,2},
                {1,3},
                {2,3},
                {2,4},
        };
        visited = new boolean[input.length];
        for(int i = 0; i<input.length; i++){
            list.add(new ArrayList<>());
        }
        for (int[] a : input ){
            addEdge(a[0],a[1]);
        }
        System.out.println(list);
        System.out.println();
        dfs(1);
    }
    static void addEdge(int a , int b){
        list.get(a).add(b);
        list.get(b).add(a);
    }
    static void dfs(int start) {
        System.out.println(start);
        visited[start] = true;
        for (int i = 0; i<list.get(start).size(); i++) {
            if(!visited[list.get(start).get(i)]) {
                dfs(list.get(start).get(i));
            }
        }
    }
}

public class DFS_ArrayGraph {
    static int[][] graph;
    static boolean[] visited;
    public static void main(String[] args) {
        graph = new int[][]{
                {0, 1, 1, 0, 0},
                {1, 0, 0, 1, 0},
                {1, 0, 0, 1, 1},
                {0, 1, 1, 0, 0},
                {0, 0, 1, 0, 0}
        };
        visited = new boolean[graph.length];
        dfs( 0);
    }
    static void dfs(int start) {
        System.out.println(start);
        visited[start] = true;
        for (int i = 0; i<graph[start].length; i++) {
            if(!visited[i] && graph[start][i] == 1) {
                dfs(i);
            }
        }
    }
}

프로그래머스 문제 : 네트워크
프로그래머스 문제 : 타겟 넘버

github java 실습 내용