사전캠프 12일차

2.정렬

 

정렬은 비록 단일 문제로 코딩테스트에는 잘 나오는 편이 아니지만 연계로 나오는편이 많고 면접에도 가끔 나오니 각각 장단점 및 시간 복잡도에 대해만 알아두자! + 자바에서 Comparator를 이용하여 Arrays.sort를 커스터마이징 할 수 있는데 이것에 대해도 정리해두자!

 

정렬시 고려사항

• 시간 복잡도
• 공간 복잡도
• 같은 값의 데이터가 존재 할 시 순서가 바뀌는지 여부 (안정성)

시간 복잡도

알고리즘 종류	평균 시간 복잡도	최악 시간 복잡도
퀵 정렬 (Quick Sort)	O(nlogn)	O(n^2)
버블 정렬 (Bubble Sort)	O(n^2)	O(n^2)
선택 정렬 (Selection Sort)	O(n^2)	O(n^2)
삽입 정렬 (Insertion Sort)	O(n^2)	O(n^2)
병합 정렬 (Merge Sort)	O(nlogn)	O(nlogn)
기수 정렬 (Radix Sort)	O(d(n + k))	O(d(n + k))
계수 정렬 (Counting Sort)	O(n)	O(n+k)

 

2-1 퀵 정렬

자바에서 기본적으로 내장되어 제공하는 정렬 알고리즘으로 분할 정복 방법으로 구현된 정렬 알고리즘 입니다.

 

분할 정복 (Divide and Conquer)

• 큰 문제를 작은 문제로 나누어서 해결하는 알고리즘
• 분할 -> 정복  단계를 반복하여 최종적으로 더 이상 분해가 되지 않으면 결합

1. 피벗이라는 하나의 요소를 기준으로 값이 작다면 왼쪽 값이 크다면 오른쪽으로 분할

2. 분할된 2개의 배열에 대해 1번 행위 반복

3. 모든 하위 배열의 크기가 1 또는 0 일 경우 분할을 멈추고 전부 결합

 

 자바에서 쓰이는 Arrays.sort() , Collections.sort가 이러한 방식

 

2-2 버블 정렬

 

• 인접한 두 원소를 비교하여 위치를 교환하여 배열을 정렬하는 방식 안정성은 보장
• 상당히 느리고 비효율적이여서 실제로 사용되는 경우가 드문 정렬 알고리즘 

 

2-3 선택 정렬

• 선택된 값과 나머지 데이터를 비교하여 알맞은 자리를 찾는 알고리즘 안정성 보장x
• 주어진 배열에서 가장 작은 값을 찾아서 맨앞과 자리를 바꾸고 그다음으로 작은 값을 찾아서 두 번째 원소와 자리를 바꾸는 식으로 정렬하는 알고리즘
• 버블 정렬과 마찬가지로 느리고 비효율적이여서 실제로 사용하지 않는 알고리즘

 

2-4 삽입 정렬

• 데이터 집합을 순회하면서 정렬되지 않은 부분에서 값을 선택하고 그 값을 이미 정렬된 부분의 올바른 위치에 삽입하는 과정을 수행하는 알고리즘
• 성능은 버블정렬보다는 좋음

 

2-5 병합 정렬

• 배열을 반으로 나누어 각각을 정렬한 후, 병합하는 과정을 통해 전체 배열을 정렬
• 데이터 집합이 메모리에 한번에 올리기에 너무 클 때 쓰기 좋은 방법
• 분할 정복을 이용하는 것은 퀵 정렬과 동일하다!
• 피벗을 이용하느냐 데이터 중간을 이용하느냐 퀵정렬과의 차이점!

 

2-6 기수 정렬 

• 비교 연산을 사용하지 않고 자릿수 별로 정렬을 수행하는 알고리즘
• 또 다른 메모리 공간을 필요로 하는게 단점
• 낮은 자릿수부터 정렬을 진행

 

2-7 카운팅 정렬

• 카운팅 정렬 역시 기수 정렬과 동일하게 비교 연산을 사용하지 않기 때문에 빠르다
• 하지만 counting 배열이라는 새로운 배열을 선언해야하는데 메모리 공간이 낭비가 된다.
• 정렬 문제를 사용할 때 시간 복잡도가 매우 중요할 경우 카운팅 정렬을 사용하는 것이 좋다!

 

이처럼 정렬의 대표적인 7가지를 알아봤는데 시간면이나 메모리 면에서 뛰어난 퀵정렬을 대부분 사용하며 시간 복잡도면에서 강점을 가지는 카운팅 정렬까지는 알아두자! 

 

---

Comparator를 활용한 커스터마이징

 

Arrays.sort()를 활용할 시 기본적으로 오름차순 정렬을 해준다. 하지만 내림차순으로 정렬을 하기 위해선 

Collentions을 활용하거나 Comparator를 활용하여 값을 바꿔줘야 하는데

Integer[] intArr = new Integer[] {1,3,2,5,4};
Arrays.sort(intArr,new Comparator<Integer>() {
	@Override
	public int compare(Integer a, Integer b) { // a는 앞의 수 b는 뒤의 수
		System.out.println(a.compareTo(b));
        return a.compareTo(b); // 오름차순
        // return a - b; // 오름차순
        //return b.compareTo(a); // 내림차순
    }
});

 

이런식으로 compare를 사용하여 사용자가 직접 정렬 기준을 정의 할 수 있으며  return 값이 음수라면 값을 바꾸고 양수라면 값을 바꾸지 않는다. 이것을 이용하여 오름차순, 내림차순을 해줄 수 있으며 이차원 배열의 경우에도 정렬해 줄 수 있다. 또한 람다식을 이용하여 더욱 간단하게 나타낼 수 있으나 람다식 보단 comparator 전체를 외워두자!

Integer[] intArr = new Integer[] {1,3,2,5,4};
// 오름차순 정렬
Arrays.sort(intArr, (a, b) ->
	a - b
);
// 내림차순 정렬
Arrays.sort(intArr, (a, b) ->
	b - a
);

 

 

---

오늘은 백트래킹 문제를 풀어보려고 한다!

어제 마지막으로 풀었던 문제가 백트래킹 문제였는데 아직 정확하게 백트래킹에 대해 파악하지 못한거 같아 공부할 겸 연습하려고한다!

 

백트래킹

• 어떤 문제를 풀 때에 모든 경우의 수를 체크하며 답이 아닌 경우 그 이전 상태로 되돌아가서 다른 케이스를 체크하는 알고리즘
• DFS와 유사하게 재귀적으로 깊숙하게 확장해나가며 답을 찾는다.
• 하지만 해당 경로가 틀리다면 이전 상태로 돌아간다

 

백준 15649번 N과 M (1)

 

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [] arr;
	public static boolean visited[];
	public static int r;
	public static int c;
	public static int max_len = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		arr = new int[m];
		visited = new boolean[n+1];
		dfs(n,m,0);
		System.out.println(sb);
	}
	public static void dfs(int n, int m, int dep) {
		if(dep==m) {
			for(int i : arr) {
				sb.append(i+" ");
			}
			sb.append("\n");
			return;
		}
		for(int i =1;i<=n;i++) {
			if(!visited[i]) {
				arr[dep] = i;
				visited[i] = true;
				dfs(n,m,dep+1);
				visited[i] = false;
			}
		}
	}
}

 

백준 15650번 N과 M (2)

 

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [] arr;
	public static boolean visited[];
	public static int r;
	public static int c;
	public static int max_len = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		arr = new int[m];
		visited = new boolean[n+1];
		dfs(n,m,0,1);
		System.out.println(sb);
	}
	public static void dfs(int n, int m, int dep, int start) {
		if(dep==m) {
			for(int i : arr) {
				sb.append(i+" ");
			}
			sb.append("\n");
			return;
		}
		for(int i =start;i<=n;i++) {
			if(!visited[i]) {
				arr[dep] = i;
				visited[i] = true;
				dfs(n,m,dep+1,i);
				visited[i] = false;
			}
		}
		
	}
}

 

 

백준 15651번 N과 M (3)

 

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [] arr;
	public static boolean visited[];
	public static int r;
	public static int c;
	public static int max_len = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		arr = new int[m];
		visited = new boolean[n+1];
		dfs(n,m,0);
		System.out.println(sb);
	}
	public static void dfs(int n, int m, int dep) {
		if(dep==m) {
			for(int i : arr) {
				sb.append(i+" ");
			}
			sb.append("\n");
			return;
		}
		for(int i =1;i<=n;i++) {
				arr[dep] = i;
				
				dfs(n,m,dep+1);
				
			
		}
		
	}
}

 

 

백준 15652번 N과 M (4)

 

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [] arr;
	public static boolean visited[];
	public static int r;
	public static int c;
	public static int max_len = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		arr = new int[m];
		visited = new boolean[n+1];
		dfs(n,m,0,1);
		System.out.println(sb);
	}
	public static void dfs(int n, int m, int dep,int start) {
		if(dep==m) {
			for(int i : arr) {
				sb.append(i+" ");
			}
			sb.append("\n");
			return;
		}
		for(int i =start;i<=n;i++) {
				arr[dep] = i;
				
				dfs(n,m,dep+1,i);
				
			
		}
		
	}
}

 

 

 

백준 15654번 N과 M (5)

 

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [] arr;
	public static int [] arr2;
	public static boolean visited[];
	public static int r;
	public static int count = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(bf.readLine());
		arr = new int[m];
		arr2 = new int[n];
		for(int i=0;i<n;i++) {
			arr2[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr2);
		visited = new boolean[10001];
		dfs(n,m,0);
		System.out.println(sb);
	}
	public static void dfs(int n, int m, int dep) {
		if(dep==m) {
			for(int i : arr) {
				sb.append(i+" ");
			}
			sb.append("\n");
			return;
		}
		for(int i : arr2) {
			if(!visited[i]) {
				visited[i] = true;
				arr[dep] = i;
				dfs(n,m,dep+1);
				visited[i] = false;
			}
		}
	}
}

 

백준 15655번 N과 M (6)

 

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [] arr;
	public static int [] arr2;
	public static boolean visited[];
	public static int r;
	public static int count = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(bf.readLine());
		arr = new int[m];
		arr2 = new int[n+1];
		for(int i=0;i<n;i++) {
			arr2[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr2);
		visited = new boolean[10001];
		dfs(n,m,0,1);
		System.out.println(sb);
	}
	public static void dfs(int n, int m, int dep, int start) {
		if(dep==m) {
			for(int i : arr) {
				sb.append(i+" ");
			}
			sb.append("\n");
			return;
		}
		for(int i=start;i<=n;i++) {
			int a = arr2[i];
			if(!visited[a]) {
				visited[a] = true;
				arr[dep] = a;
				dfs(n,m,dep+1,i+1);
				visited[a] = false;
			}
		}
	}
}

 

백준 15656번 N과 M (7)

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [] arr;
	public static int [] arr2;
	public static boolean visited[];
	public static int r;
	public static int count = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(bf.readLine());
		arr = new int[m];
		arr2 = new int[n+1];
		for(int i=0;i<n;i++) {
			arr2[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr2);
		dfs(n,m,0);
		System.out.println(sb);
	}
	public static void dfs(int n, int m, int dep) {
		if(dep==m) {
			for(int i : arr) {
				sb.append(i+" ");
			}
			sb.append("\n");
			return;
		}
		for(int i=1;i<=n;i++) {
			int a = arr2[i];
				arr[dep] = a;
				dfs(n,m,dep+1);
		}
	}
}

 

 

백준 15657번 N과 M (8)

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [] arr;
	public static int [] arr2;
	public static boolean visited[];
	public static int r;
	public static int count = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(bf.readLine());
		arr = new int[m];
		arr2 = new int[n+1];
		for(int i=0;i<n;i++) {
			arr2[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr2);
		dfs(n,m,0,1);
		System.out.println(sb);
	}
	public static void dfs(int n, int m, int dep, int start) {
		if(dep==m) {
			for(int i : arr) {
				sb.append(i+" ");
			}
			sb.append("\n");
			return;
		}
		for(int i=start;i<=n;i++) {
			int a = arr2[i];
				arr[dep] = a;
				dfs(n,m,dep+1,i);
		}
	}
}

 

 

백준 15663번 N과 M (9)

 

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [] arr;
	public static int [] arr2;
	public static boolean visited[];
	public static int r;
	public static int count = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(bf.readLine());
		arr = new int[m];
		arr2 = new int[n];
		for(int i=0;i<n;i++) {
			arr2[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr2);
		visited = new boolean[n];
		dfs(n,m,0);
		System.out.println(sb);
	}
	public static void dfs(int n, int m, int dep) {
		if(dep==m) {
			for(int i : arr) {
				sb.append(i+" ");
			}
			sb.append("\n");
			return;
		}
		int before = 0;
		for(int i=0;i<n;i++) {
			if(!visited[i] && before!= arr2[i]) {
				visited[i] = true;
				arr[dep] = arr2[i];
				before = arr2[i];
				dfs(n,m,dep+1);
				visited[i] = false;
			}
		}
	}
}

 

백준 15664번 N과 M (10)

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [] arr;
	public static int [] arr2;
	public static boolean visited[];
	public static int r;
	public static int count = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(bf.readLine());
		arr = new int[m];
		arr2 = new int[n];
		for(int i=0;i<n;i++) {
			arr2[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr2);
		visited = new boolean[n];
		dfs(n,m,0,0);
		System.out.println(sb);
	}
	public static void dfs(int n, int m, int dep, int start) {
		if(dep==m) {
			for(int i : arr) {
				sb.append(i+" ");
			}
			sb.append("\n");
			return;
		}
		int before = 0;
		for(int i=start;i<n;i++) {
			if(!visited[i] && before!= arr2[i]) {
				visited[i] = true;
				arr[dep] = arr2[i];
				before = arr2[i];
				dfs(n,m,dep+1,i);
				visited[i] = false;
			}
		}
	}
}

 

백준 15665번 N과 M (11)

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [] arr;
	public static int [] arr2;
	public static boolean visited[];
	public static int r;
	public static int count = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(bf.readLine());
		arr = new int[m];
		arr2 = new int[n];
		for(int i=0;i<n;i++) {
			arr2[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr2);
		dfs(n,m,0);
		System.out.println(sb);
	}
	public static void dfs(int n, int m, int dep) {
		if(dep==m) {
			for(int i : arr) {
				sb.append(i+" ");
			}
			sb.append("\n");
			return;
		}
		int before = 0;
		for(int i=0;i<n;i++) {
			if(before!= arr2[i]) {
				arr[dep] = arr2[i];
				before = arr2[i];
				dfs(n,m,dep+1);
			}
		}
	}
}

 

백준 15666번 N과 M (12)

 

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [] arr;
	public static int [] arr2;
	public static boolean visited[];
	public static int r;
	public static int count = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(bf.readLine());
		arr = new int[m];
		arr2 = new int[n];
		for(int i=0;i<n;i++) {
			arr2[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr2);
		dfs(n,m,0,0);
		System.out.println(sb);
	}
	public static void dfs(int n, int m, int dep, int start) {
		if(dep==m) {
			for(int i : arr) {
				sb.append(i+" ");
			}
			sb.append("\n");
			return;
		}
		int before = 0;
		for(int i=start;i<n;i++) {
			if(before!= arr2[i]) {
				arr[dep] = arr2[i];
				before = arr2[i];
				dfs(n,m,dep+1,i);
			}
		}
	}
}