백준에 있는 문제 중 1182번을 풀면서 부분집합에 대한 내용이 나와서 간단하게 정리하려고 한다.

예를 들어 배열 [1,2,3]이 있다고 가정하자. 그러면 부분집합은 아래와 같다.

[1]
[2]
[3]
[1,2]
[1,3]
[2,3]
[1,2,3]

부분 집합을 구할 수 있는 방법은 조합을 이용한 방법이 있고 재귀를 이용한 방법이 있다. 이번에는 후자인 재귀에 대해서만 알아보도록 하겠다.

두 가지 경우를 생각해보면 된다.

  1. 현재 인덱스를 포함하는 경우
  2. 현재 인덱스를 포함하지 않는 경우

위의 두 가지 경우를 visited 배열에 방문했는지 체크함으로써 분기시킬 수 있다. 두 가지 경우에 대해서 모두 확인한 후에 현재 인덱스가 n이 되면 출력한다.

출력할 때는 visited 배열의 값이 true인 원소들만 출력한다.
코드는 아래와 같다.

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
public class Main {
private static int n = 3;
private static boolean[] visited = new boolean[n];

public static void main(String[] args) {
int[] arr = {1, 2, 3};
getSet(arr, 0);
}

private static void getSet(int[] arr, int index) {
if (index == n) {
print(arr);
return;
}

visited[index] = false;
getSet(arr, index + 1);

visited[index] = true;
getSet(arr, index + 1);

}

private static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
if(visited[i]){
System.out.print(arr[i]+" ");
}
}
System.out.println();
}
}
// 결과
3
2
2 3
1
1 3
1 2
1 2 3

참고

Comment and share

# Anagram이란?

동일한 알파벳을 재배열하여 만들 수 있는 문장이나 단어를 말한다.
예를 들면, listen silent 두 단어는 애너그램이다.

개념은 간단하다. 사실 풀이도 간단하게 풀 수 있다.

중요한 점
알파벳의 위치만 바꿔서 단어를 만들기 때문에 두 단어 사이에는 결국 같은 알파벳이 존재하게 된다. 이 점을 활용하여 두 단어를 알파벳 순으로 정렬해서 같은지 아닌지 비교하여 문제를 풀 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static boolean isAnagram(String a, String b) {
// 대소문자를 구분하지 않기 때문에 문자열의 문자를 모두 대문자로 바꾼다.
// 그리고 String을 char 배열로 변환한다.
char[] char_a = a.toUpperCase().toCharArray();
char[] char_b = b.toUpperCase().toCharArray();

// 알파벳 순으로 정렬한다.
Arrays.sort(char_a);
Arrays.sort(char_b);

// 다시 문자열에 할당한다.
String str_a = new String(char_a);
String str_b = new String(char_b);

// 그러면 정렬도 했으니 같은 문자열이 담겨 있게 된다.
// 같은 문자열일 경우 애너그램이라고 할 수 있으므로 true를 리턴한다.
if (str_a.equals(str_b)) {
return true;
}

return false;
}

참고

Comment and share

# 그래프 탐색이란

그래프 탐색에 대해서는 DFS 글에서도 확인할 수 있다.

# 너비 우선 탐색

너비 우선 탐색(Breadth-First Search)은 BFS라고 부른다. (이하 BFS라고 하겠다.)

루트 노드(혹은 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법.

  • 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
  • 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
  • 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
    • Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
    • 깊이 우선 탐색의 경우 : 모든 친구 관계를 다 살펴봐야 할지도 모른다.
    • 너비 우선 탐색의 경우 : Ash와 가까운 관계부터 탐색.
  • BFS가 DFS보다 좀 더 복잡하다.

BFS의 특징

  • 직관적이지 않은 면이 있다.
    • BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
  • BFS는 재귀적으로 동작하지 않는다.
  • 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다.
    • 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.
  • BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
    • 즉, 선입선출 원칙으로 탐색
    • 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

BFS의 탐색 과정

  1. a 노드(시작 노드)를 방문한다.(방문한 노드 체크)
    • 큐에 방문된 노드를 삽입한다.(enqueue)
    • 초기 상태의 큐에는 시작 노드만 저장
      • 즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.
  2. 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문한다.
    • 큐에서 꺼낸 노드를 방문한다.
    • 큐에서 꺼낸 노드와 인접한 노드들을 모두 방문한다.
      • 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다.(dequeue)
    • 큐에 방문된 노드를 삽입한다.(enqueue)
  3. 큐가 소진될 때까지 계속한다.

BFS의 구현

  • 구현 방법
    • 자료 구조인 큐(Queue)를 사용.
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.io.*;
import java.util.*;

/**
* created by victory_woo on 02/04/2019
* DFS와 BFS 복습
*/
public class BOJ1260_RE {
private static final String SPACE = " ";
private static ArrayList<Integer>[] a;
private static boolean[] visit;

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String[] input = br.readLine().split(SPACE);
int n = convert(input[0]); // 정점의 개수
int m = convert(input[1]); // 간선의 개수
int start = convert(input[2]); // 시작할 정점 번호

// 배열 초기화.
a = new ArrayList[n + 1];

for (int i = 1; i <= n; i++) {
a[i] = new ArrayList<>();
}

for (int j = 0; j < m; j++) {
String[] inputs = br.readLine().split(SPACE);
int u = convert(inputs[0]);
int v = convert(inputs[1]);

// 양방향 그래프일 경우 양쪽 다 추가해준다.
a[u].add(v);
a[v].add(u);
}

// 방문할 정점이 여러 개인 경우 정점 번호가 가장 작은 것부터 탐색하기 위해서 정렬한다.
for (int i = 1; i <= n; i++) {
Collections.sort(a[i]);
}

visit = new boolean[n + 1];
bfs(start);
System.out.println();
}

private static int convert(String command) {
return Integer.parseInt(command);
}

private static void bfs(int start) {
LinkedList<Integer> queue = new LinkedList<>();

visit[start] = true;
queue.add(start);

while (!queue.isEmpty()) {
int x = queue.remove(); // 큐에서 정점을 뺀다.

System.out.print(x + SPACE);

for (int y : a[x]) {
// 방문한 적이 있는지 체크한다.
if (!visit[y]) {
// 해당 정점을 방문한 적이 없다면 방문했다고 true 로 체크한다.
// 그리고 해당 정점을 큐에 넣는다.
visit[y] = true;
queue.add(y);
}
}
}
}
}
// 입력
5 5 3
5 4
5 2
1 2
3 4
3 1
// 출력 결과
3 1 4 2 5

BFS의 시간 복잡도

  • N : 정점의 개수, E : 간선의 개수
  • 인접 리스트로 표현된 그래프 : O(N+E)
  • 인접 행렬로 표현된 그래프 : O(N^2)
  • DFS와 마찬가지로 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

참고

Comment and share

목차

# 그래프 탐색이란

  • 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
  • Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 등등

# 깊이 우선 탐색

깊이 우선 탐색(Depth-First Search)은 DFS라고도 부른다.(이하 DFS라고 하겠다.)

루트 노트(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

  • 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
  • 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
  • 사용하는 경우 : 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
  • DFS가 BFS보다 좀 더 간단하다.
  • 단순 검색 속도 자체는 BFS에 비해서 느리다.

DFS의 특징

  • 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
  • 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
  • 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다.
    • 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.

DFS 탐색 과정

  1. a 노드(시작 노드)를 방문한다.
    • 방문한 노드는 방문했다고 표시한다.
  2. a와 인접한 노드들을 차례로 순회한다.
    • a와 인접한 노드가 없다면 종료한다.
  3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
    • b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
  4. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안된 정점을 찾는다.
    • 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
    • 정점을 모두 방문했으면 종료한다.
    • 아직 방문이 안된 정점이 있으면 그 정점을 시작 정점으로 DFS를 시작한다.

DFS의 구현

  • 구현 방법은 2가지가 있다.
    1. 순환 호출 이용 즉, 재귀 함수 호출.
    2. 명시적인 스택 사용
      • 명시적인 스택을 사용하여 방문한 정점들을 스택에 저장하였다가 다시 꺼내어 작업한다.

만약 어떤 정점에서 더 방문할 노드가 없다면 자신을 불렀던 정점으로 돌아간다.
이 과정을 구현하기 위해 스택(Stack)을 사용한다.

방문하는 순서대로 정점을 스택에 쌓고, 방문이 끝나면 스택에서 pop하는 형태로 구현이 가능하다. 재귀 함수 또한 스택 메모리 공간에 쌓아 올려지는 구조를 띄므로 재귀 함수를 사용하여도 이것을 구현할 수 있다.

DFS의 시간 복잡도

  • DFS는 그래프(정점의 수:N, 간선의 수:E)의 모든 간선을 조회한다.
    • 인접 행렬로 표현된 그래프 : O(N^2)
      • 없는 간선도 저장한다.
    • 인접 리스트로 표현된 그래프 : O(N+E)
  • 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.
  • 보통은 E << N^2 이기 때문에 인접 리스트를 사용한다.

DFS 구현

  • 인접 리스트를 사용하여 구현한다.
  • 재귀 함수 호출을 사용한다.
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.io.*;
import java.util.*;

/**
* created by victory_woo on 02/04/2019
* DFS와 BFS 복습
*/
public class BOJ1260_RE {
private static final String SPACE = " ";
private static ArrayList<Integer>[] a;
private static boolean[] visit;

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String[] input = br.readLine().split(SPACE);
int n = convert(input[0]); // 정점의 개수
int m = convert(input[1]); // 간선의 개수
int start = convert(input[2]); // 시작할 정점 번호

// 배열 초기화.
a = new ArrayList[n + 1];
visit = new boolean[n + 1];

for (int i = 1; i <= n; i++) {
a[i] = new ArrayList<>();
}

for (int j = 0; j < m; j++) {
String[] inputs = br.readLine().split(SPACE);
int u = convert(inputs[0]);
int v = convert(inputs[1]);

// 양방향 그래프일 경우 양쪽 다 추가해준다.
a[u].add(v);
a[v].add(u);
}

// 방문할 정점이 여러 개인 경우 정점 번호가 가장 작은 것부터 탐색하기 위해서 정렬한다.
for (int i = 1; i <= n; i++) {
Collections.sort(a[i]);
}
dfs(start);
}

private static int convert(String command) {
return Integer.parseInt(command);
}

private static void dfs(int x) {
// 방문한 적이 있다면 종료한다.
if (visit[x]) {
return;
}

visit[x] = true;
// 방문한 순서 출력
System.out.print(x+" ");

for (int y : a[x]) {
if (!visit[y]) {
dfs(y);
}
}

}
}
입력
5 4 5
5 4
4 3
4 2
1 5
출력 결과
5 1 4 2 3

참고

Comment and share

# 그래프 탐색

그래프를 탐색하는 방법에는 널리 사용되는 두 가지 방식이 있다.

  • DFS는 깊이 우선 탐색(Depth-First Search)이다.
  • BFS는 너비 우선 탐색(Breadth-First Search)이다.
  • 먼저 그래프라는 자료구조에 대한 지식이 있어야 한다.

그래프

자료 구조의 일종이다.
그래프는 정점과 간선의 집합이다.

용어

  • 정점(Vertex) : 노드라고도 부른다.
  • 간선(Edge) : 정점 간의 관계를 나타낸다.
    • 두 정점을 이어준다.
    • 자기 자신을 이을 수도 있다.(루프)
    • 간선에 방향이 있기도 하고 없기도 하다.
    • 가중치가 있기도 하고 없기도 하다.
  • 경로(Path) : 정점 A에서 B로 가는 경로
  • 사이클 : 정점 A에서 다시 A로 돌아오는 경로
  • 단순 경로 / 단순 사이클 : 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클을 의미한다.
    • 특별한 말이 없으면 일반적으로 사용하는 경로와 사이클은 단순 경로/사이클을 말한다.
  • 방향 있는 그래프 : 간선에 방향이 존재한다. A -> C는 있지만 C -> A는 없다.
  • 방향 없는 그래프 : A - C와 같이 간선에 방향이 없다. 이는 A -> C와 C -> A를 나타낸다. 양방향 그래프라고도 한다.
  • 간선 여러개 : 두 정점 사이에 간선이 여러 개일 수도 있다.
    • 두 간선은 서로 다른 간선이다.
    • 최소 비용을 구할 때는 가중치가 적은 것을 선택하면 된다.
  • 루프 : 간선의 양 끝 점이 같은 경우다. A -> A
  • 가중치(Weight) : 간선에 가중치가 있는 경우를 말한다.
    • A에서 B로 이동하는 거리, 이동하는데 필요한 시간, 이동하는데 필요한 비용 등등.
    • 가중치가 없는 경우에는 1이라고 생각하면 된다.
  • 차수(Degree) : 정점과 연결되어 있는 간선의 개수를 말한다.

그래프의 표현

  • 정점 : 변수 하나로 개수를 표현하면 된다.
  • 간선 : 무엇과 무엇이 연결되어 있는지를 저장해야 한다. (그래프를 저장하는 방식.)

그래프를 구현하는데 있어서 다음과 같은 두 가지 방식을 사용할 수 있다. 참고로 무방향 그래프를 기준으로 설명하겠다.

  • 그래프를 저장하는 방식
    1. 인접 행렬
    2. 인접 리스트

먼저, 인접 행렬은 정점(V)이 N개 일때, NxN의 2차원 배열로 나타낼 수 있다.

인접 행렬을 일반적으로 a라고 이름을 짓는다.
a[1][5] = 1의 의미는 정점 1과 정점 5의 간선이 연결되어 있다는 뜻이다.
무방향이기 때문에 a[5][1] 또한 1이다. 빨간색 줄을 통해서 확인할 수 있다.
인접 행렬의 값이 1이라면, 정점 간의 간선이 존재한다는 것이고, 0이라면 존재하지 않는다는 것이다.
(현재 위의 예에서는 가중치가 없지만, 가중치를 넣을 때는 1 대신 가중치를 넣으면 된다.)

1
2
3
4
5
6
7
8
9
int[][] a = new int[N+1][N+1];

for(int i=0;i<m;i++){
int v1 = sc.nextInt();
int v2 = sc.nextInt();

a[v1][v2] = 1;
a[v2][v1] = 1;
}

이번에는 인접 리스트를 확인해보자.

인접행렬은 2차원 배열의 행과 열을 통해 정점 간의 간선을 표현했는데, 인접 리스트는 이와 다르다. 1에 연결되어 있는 간선들을 A[1]에 저장하고, A[2]에는 2에 연결되어 있는 간선을 저장한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[N+1];

for(int i=0;i<=N;i++){
a[i] = new ArrayList<>();
}

for(int i=0;i<M;i++){
int v1 = sc.nextInt();
int v2 = sc.nextInt();

a[v1].add(v2);
a[v2].add(v1);
}

같은 목적이지만 배열과 리스트를 통해 다르게 저장함으로써 큰 차이를 볼 수 있다.
인접 행렬은 크기가 정점과 간선의 개수와 상관없이 정점 갯수 x 정점 갯수이기 때문에 공간 복잡도가 O(V^2)이다.
하지만, 인접 리스트는 필요한 공간만 쓰기 때문에 O(V+E)가 된다.
인접 행렬보다는 인접 리스트를 사용하는게 훨씬 효율적이다.

# DFS

한 우물만 깊게 파다가 막히면 그제서야 돌아가서 다른 우물을 파는 성향이 있다고 할 수 있다.
모든 정점을 1번씩 방문한다.

  • 먼저 정점 하나를 선택한다.
  • 그리고 그 정점의 아직 방문하지 않은 인접한 정점 중 하나를 선택해 방문한다.
  • 0이 인접한 1을 방문하면 그 다음번에는 0에 인접한 다른 정점들보다 1에 인접한 정점들이 우선적으로 방문된다.
  • 0번 정점에서 시작한다. 인접한 정점이 여러 개라면 그 중 번호가 제일 작은 것부터 방문한다.
  • 빨간색이 지금 막 방문한 노드이고 녹색은 이전에 방문한 노드, 파란색은 아직 방문하지 않은 노드이다.
  • 일단 처음 방문한 0번 노드와 인접한 노드는 1,2번이다.
  • 이 중에서 더 작은 번호의 1번 노드를 방문한다.
  • 그 다음에 2번 노드를 방문하는게 아니라 주체가 바뀌어서 1번 노드의 인접한 0,3,5번 노드 중 하나를 방문할 계획이다.
  • 0번은 이미 방문했으니 3,5번 중 하나를 다음에 방문한다. 번호가 더 작은 3번 노드를 방문한다.
  • 위의 그림처럼 더 작은 번호의 3번 노드를 방문한다. 다음에는 선택지가 하나밖에 없다. -> 4번 노드
  • 역시 선택지는 5번 노드밖에 없다.
  • 5번 노드에서 더 이상 방문할 인접 노드가 없다. 모두 방문했기 때문.
  • 이때는 5번 노드에서 추가로 다른 노드를 방문하지 않고, 자기를 불렀던 4번 노드로 돌아가서 4번 노드의 인접한 노드들 중 아직 방문하지 않은 정점을 찾아 방문해야 한다.
  • 4번에서도 그게 없다면, 4번을 불렀던 3번으로 돌아가고 이와 같은 과정을 반복해서 0번 노드까지 돌아가게 된다.
  • 0번 노드의 인접한 정점 중 아직 방문하지 않은 나머지 정점 2번 노드를 방문한다.
  • 2번 노드는 마찬가지로 6번 노드를 방문한다.
  • 6번 노드는 7번 노드를 이어서 방문한다.
  • 여기서 또 7번 노드는 더 이상 방문할 곳이 없다.
  • 이제 6번 노드로 돌아가서 6번 노드의 인접한 다른 정점인 8번 노드를 방문한다.
  • 8번 노드를 방문하고 나면 아무리 돌아가도 더 이상 남아 있는 노드 중 방문할 정점이 없다.
  • 이러면 탐색이 종료된 것이고, 시작점인 0번 노드와 직/간접적으로 연결되어 있는 모든 노드를 탐색한 것이다.

이 과정에서 만약 어떤 정점에서 더 방문할 노드가 없다면 자신을 불렀던 정점으로 돌아간다.
이걸 구현하기 위해서 스택(Stack)을 사용한다.

방문하는 순서대로 정점을 스택에 쌓고, 방문이 끝나면 스택에서 pop하는 형태로 구현이 가능하다. 재귀 함수 또한 스택 메모리 공간에 쌓아 올려지는 구조를 띄므로 재귀 함수를 사용하여도 이것을 구현할 수 있다.

시간 복잡도

인접 행렬을 사용하는 경우 : O(V^2)
인접 리스트를 사용하는 경우 : O(V+E) - 정점과 간선의 개수 합이다.

# BFS

역시 모든 정점을 한 번씩 순회한다.
DFS와 대립되는 성질을 갖고 있으며, 사용되는 곳도 매우 다르다.
BFS 역시 컴포넌트의 개수를 세거나 각 컴포넌트의 크기를 구하는데는 사용 가능하다.

DFS가 한 우물만 계속 파다가 끝을 보고 나서야 다른 곳으로 옮기는 데 반해, BFS는 모든 곳을 똑같이 조금씩 조금씩 판다.

  • dfs와 동일한 그래프를 사용한다.
  • 맨 처음에 0번 정점부터 방문을 시작한다.
  • DFS와 다르게 0번 정점과 인접한 정점들부터 무조건 먼저 다 방문된다.
  • 그 다음은 바로 전 단계에서 방문한 1,2번 정점들로부터 인접한 3,5,6,8번 정점들이 반드시 먼저 방문된다.
  • 마지막으로 4,7번 정점이 방문된다.
  • 각 단계의 정점들은 그 안에서 방문 순서가 바뀔 수는 있지만, 다른 단계와는 방문 순서가 절대 뒤섞이지 않는다.
  • 0번 노드, 즉 시작점을 방문한 것을 0단계라 하고 그 다음부터 1,2,3 단계라고 부를 때, K단계에 방문하는 정점들은 시작점으로부터 최단거리가 k이다.
  • 최단 거리 : 여기서는 가중치가 없으니까 A와 B의 최단거리는 A에서 B로 이동하는데 필요한 최소 개수의 간선이라고 보면 된다.

DFS에 스택이 필요했던 것과 대조적으로 BFS는 큐가 필요하다.
BFS는 먼저 방문한 노드들부터 본다.

먼저 시작점을 큐에 넣고 방문했다고 표시한다.
그리고 큐가 비어있지 않을 때까지 방문을 시도한다.
큐에서 지금 나온 정점의 인접한 노드들 중 아직 방문하지 않은 애들을 다시 큐에다 넣어준다.
이런 식으로 먼저 방문한 노드들부터 차례대로 방문해 나간다.

  • 모든 가중치가 1인 경우에 최단 거리를 찾는 알고리즘이 된다.
    최단 거리를 찾는 문제일 때, 모든 가중치가 1이라면 BFS를 사용한다.

마치며…

음, 아직 뭔가 감이 잡히진 않는다.
그래프를 탐색할 때 DFS와 BFS의 차이점은 알겠고 개념도 알겠는데 문제를 풀 때 어떻게 구현해야 하는지 잘 모르겠다.
다음 포스팅에서 직접 구현해보면서 정리해보도록 하겠다.

참고

Comment and share

소수를 구하는 방법은 여러가지가 있다. 하지만 시간이 덜 거리고 빠르게 찾을 수 있는 방법이 있다면 사람들은 그 방법을 사용하지 않을까? 맞다. 사람들은 짧은 시간이 걸리는 것을 선호한다. 세상의 공짜란 없듯이 짧은 시간이 걸리는 방법은 구현 방법이 기존보다는 조금 어렵다. 그렇다면 어떤 방법인지 알아보자.

소수란?

1과 자기 자신으로만 나누어 떨어지는 수를 소수라고 한다. 즉, 자기 자신보다 작은 수들로 나누어봐서 하나라도 나누어 떨어지는 수가 존재하면 소수가 아니라는 뜻이다.

에라토스테네스의 체

소수의 개념을 간단하게 알아봤으니 에라토스테네스의 체 방법을 알아보자.

  • 120까지의 모든 소수를 구한다고 가정해보자.
  • 2부터 120까지 수를 배열에 모두 넣는다.
  • 소수가 아닌 수들을 모두 체크해버린다.

2를 제외한 모든 2의 배수를 체크한다.
3을 제외한 모든 3의 배수를 체크한다.
4를 제외한 모든 4의 배수를 체크한다.

이와 같은 방식으로 소수가 아닌 수들을 체크한다. 그러면 배열에서 체크되지 않은 수들은 소수만 남게 된다. 생각보다 그렇게 어렵지 않고 간단하게 이해하고 구현할 수 있다.

# 첫 번째 방법

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
public class Main {
private static final String NEW_LINE = "\n";
private static final String SPACE = " ";

public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

String[] input = br.readLine().split(SPACE);
int m = Integer.parseInt(input[0]);
int n = Integer.parseInt(input[1]);

int[] arr = new int[n + 1];

for (int i = 2; i <= n; i++) {
for (int j = 2; j <= n; j ++) {
// 자신과 같지 않고 0으로 나누어 떨어지면 소수가 아니다.
if(arr[j] !=i && arr[j] % i == 0){
arr[j] = 0; // 소수가 아닌 경우 0을 넣는다.
}
}
}

for (int i = m; i <= n; i++) {
if (arr[i] != 0) {
bw.write(i + NEW_LINE);
}
}

bw.flush();
bw.close();
br.close();
}
}

위의 방식으로 구하면 에라토스테네스의 체 방식을 이용하지 않는 방식보다 시간이 오래 걸린다. 그러면 우리가 이 방식을 사용하는 의미가 없지 않는가?? 이제 에라토스테네스의 체를 이용해 최상의 소수 구하기 프로그램을 만들어보자.

# 두 번째 방법

체크할 때 모든 수를 다 돌면서 체크할 필요 없이 체크할 배수만큼만 반복문을 돌게 하는 것이다. 그리고 이미 0으로 체크되어버린 수의 배수는 확인하지 않는다. 왜냐하면 어떤 수가 소수가 아니라면 그 수의 배수도 소수가 아니기 때문이다.

ex)
2를 제외한 2의 배수를 체크한다.
2,4,6,8,10,12,14 …

4를 제외한 4의 배수를 체크한다.
4,6,8,12,16,…
이미 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
public class Main {
private static final String NEW_LINE = "\n";
private static final String SPACE = " ";

public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

String[] input = br.readLine().split(SPACE);
int m = Integer.parseInt(input[0]);
int n = Integer.parseInt(input[1]);

boolean[] check = new boolean[n + 1];
// 에라토스테네스의 체에서 0과 1은 제외하고 시작하기 때문에 체크한다.
check[0] = check[1] = true;

for (int i = 2; i <= n; i++) {
// 체크되어 있으면 건너뛴다.
// 체크가 되어 있다는 뜻은 소수가 아니라는 뜻이다.
if (check[i]) {
continue;
}

// 해당 수의 배수만큼 반복문을 돌면서 체크한다.
for (int j = i + i; j <= n; j += i) {
// 소수가 아닌 것들을 true로 체크한다.
check[j] = true;
}
}

for (int i = m; i <= n; i++) {
if (!check[i]) {
bw.write(i + NEW_LINE);
}
}

bw.flush();
bw.close();
br.close();
}
}

이 경우 결과는 매우 짧은 시간이 나오는 것을 확인할 수 있었다. 앞으로 소수를 구할 때는 에라토스테네스의 체 방식을 이용하자.

참고

Comment and share

저번에 살펴봤던 기본적인 정렬 알고리즘에 이어 이번에는 조금 어려운 정렬 알고리즘을 살펴보자. 물론 이번 것도 어려운 것은 아니지만 상대적으로 비교해봤을 때 저번 정렬 알고리즘들보다 어렵다!

# 쉘 정렬

  • 삽입 정렬을 보완한 알고리즘이다.
  • 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠르다는 것에 착안한 것이다.
    • 삽입 정렬의 최대 문제점 : 요소들이 삽입될 때, 이웃한 위치로만 이동한다.
    • 다시 말해서 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야 제자리로 갈 수 있다.
    • 삽입 정렬과 다르게 쉘 정렬은 전체의 리스트를 한 번에 정렬하지 않는다. 그래서 요소들이 멀리 떨어진 위치로 이동할 수 있다.

기본 로직은 아래와 같다.

  1. 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류한다.
  2. 연속적이지 않은 여러 개의 부분 리스트를 생성한다.
    (실제로 여러 개의 부분 리스트가 생기고 이것들을 병합하는 것이 아니라, 단순히 gap 값으로 간격을 주어 부분 리스트가 만들어진 것처럼 구현한다. )
  3. 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.
  4. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 반복한다.
  5. 위의 1~4번까지의 과정을 리스트의 개수가 1이 될 때까지 반복한다.

기본 로직은 이렇지만 사실 잘 와닿지 않는다. 한 번 더 살펴보자.

  • 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다. 이때, k를 간격(gap)이라고 한다.
    • 간격(gap) 즉 k의 초기값 : (정렬할 값의 개수) / 2
    • 생성된 부분 리스트의 개수는 gap과 같다.
  • 각 회전마다 간격 k를 절반으로 줄인다. 즉, 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 증가한다.
    • 간격은 홀수로 하는 것이 좋다. (간격을 정하는 방법은 여러가지다.)
    • 간격을 절반으로 줄일 때 짝수가 나오면 +1을 해서 홀수로 만든다.
  • 간격 k(gap)가 1이 될 때까지 반복한다.

장점

  • 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 따라서 교환되는 요소들이 삽입 정렬보다는 최종 위치에 있을 가능성이 높아진다.
  • 부분 리스트는 어느 정도 정렬된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면 쉘 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 정렬된 상태이므로 삽입 정렬보다 더욱 빠르게 수행된다.
  • 알고리즘이 간단해서 쉽게 구현이 가능하다.

시간 복잡도

  • 평균 : O(N^1.5)
  • 최악의 경우 : O(N^2)

장점

  • 연속적이지 않은 부분 리스트에서 자료의 교환을 진행하여 더 큰 거리를 이동한다. 기존의 삽입 정렬에서는 한 칸씩 이동하며 비교를 하여 key 값의 자리를 찾았기 때문에 먼 거리를 이동할 경우 그만큼 반복 비교 연산이 많이 일어나는 단점이 있었다. 더 큰 거리를 이동함으로써 교환되는 요소들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.
  • 최종 자리를 더 빨리 찾아감으로써 연산의 횟수를 줄이는데 기여할 수 있다.
  • 삽입 정렬은 어느 정도 정렬이 된 배열에서 더 빠르게 동작한다는 것을 앞의 포스팅에서 살펴봤다. 이 점을 토대로 한 번에 정렬을 끝내는 것이 아니라 부분 리스트를 구성해 조금씩 정렬된 상태를 만들어가는 것이므로 삽입 정렬에 비해 속도가 점점 더 빠르게 수행된다.

# 합병 정렬

  • 존 폰 노이만 선생님이 제안한 방법.
  • 일반적인 방법으로 구현했을 때 이 정렬은 안정 (stable) 정렬에 속하며, 분할 정복 알고리즘의 하나이다.
  • 분할 정복(divide and conquer) 방법
    • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략.
    • 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
  • 오름 차순을 기준으로 정렬한다.

기본 로직은 다음과 같다.

  1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.(리스트의 길이가 1이 될때까지 반으로 잘게 나눈다.) 그렇지 않은 경우에는
  2. 정렬되지 않은 리스트를 절반으로 나눠 비슷한 크기의 두 부분 리스트로 나눈다.
  3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

구체적으로 다시 설명해보면 다음과 같다.

  • 최종 목표는 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 것이다.
  • 합병 정렬은 다음의 단계들로 이루어진다.
    • 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
    • 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출(재귀 호출)을 이용하여 다시 분할 정복 방법을 적용한다.
    • 결합(Combine) : 정렬된 부분 배열을 하나의 배열에 합병한다.
  • 합병 정렬의 과정
    • 추가적인 리스트가 필요하다.
    • 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.(재귀 호출)
    • 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(Merge)하는 단계이다.

장점

  • 안정적인 정렬 방법이다. stable하다.
  • 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. -> O(n logn)으로 동일.
  • 만약 레코드를 연결 리스트(LinkedList)로 구성하면 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
    • 제자리 정렬(in-place sorting)을 구현할 수 있다.
  • 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적이다.

단점

  • 만약 레코드를 배열로 구성하면, 임시 배열이 필요하다.
    • 메모리 낭비를 초래할 수 있다.
    • 제자리 정렬(in-place sorting)이 아니다.
  • 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

시간 복잡도
크기가 N인 배열을 반으로 쪼개면서 분할한다.
한 번 분할하면 N/2, N/2 -> 2개가 생기고,
그 다음 분할하면 N/4, N/4, N/4, N/4 ->4개

이처럼 분할 과정은 매번 반씩 감소하므로 밑이 2인 log N만큼 반복해야 크기가 1인 배열로 분할 할 수 있다.

각 분할별로 합병을 진행하므로 합병 정렬의 시간 복잡도는 O(NlogN)이다.

  • 평균 : NlogN
  • 최악 : NlogN
  • 최상 : NlogN

다음의 글을 참고하자. -> 병합 정렬의 시간복잡도

# 퀵 정렬

  • 오름차순을 기준으로 정렬한다.
  • '찰스 앤터니 리처드 호어’가 개발한 정렬 알고리즘이다.
  • 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
  • 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 갖는다.
    • Merge Sort와 달리 퀵 정렬은 리스트를 비균등하게 나눈다.
  • 분할 정복 방법(Divide and Conquer)
    • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략.
    • 분할 정복 방법은 순환 호출(재귀 호출)을 이용하여 구현한다.

기본 로직은 다음과 같다.

  1. 리스트 안에서 하나의 원소를 선택한다. 이 원소를 피봇이라고 한다.
  2. 피봇을 기준으로 왼쪽에는 피봇보다 작은 원소들을 옮기고 오른쪽에는 피봇보다 큰 원소들을 옮긴다.
  3. 피봇을 제외한 왼쪽 부분 집합과 오른쪽 부분 집합을 다시 정렬한다.
    • 분할된 부분 집합에 대해 순환 호출을 이용하여 정렬을 반복한다.
    • 부분 집합에 대해서도 다시 피봇을 정하고 피봇 기준으로 2개의 부분 집합으로 나누는 과정을 반복한다.
  4. 부분 집합이 더 이상 분할이 불가능할 때까지 반복한다.
    • 리스트의 크기가 0이나 1이 될 때까지 반복한다.

퀵 정렬에서 알아야 할 개념

  • 분할(Divide) : 정렬할 자료들을 피봇을 중심으로 좌, 우 2개의 부분집합으로 나누는 것을 말한다.
  • 정복(Conquer) : 부분집합의 원소들 중에서 피봇보다 작은 원소들은 왼쪽, 큰 원소들을 오른쪽 부분집합으로 정렬하는 과정이다.
  • 부분 집합의 크기가 더 이상 나눌 수 없을 때까지(부분 집합의 원소가 1개 이하) 분할, 정복 과정이 반복된다.
  • 피봇 : 기준 값(일반적으로 전체 원소 중 가운데에 위치한 원소)
  • L : 왼쪽에서 오른쪽으로 움직이며 피봇보다 큰 원소를 찾아 L로 지정.
  • R : 오른쪽에서 왼쪽으로 움직이며 피봇보다 작은 원소를 찾아 R로 지정.

장점

  • 속도가 빠르다.
    • 시간 복잡도가 O(NlogN)을 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
  • 추가 메모리 공간을 필요로 하지 않는다.
    • 퀵 정렬은 O(NlogN) 만큼의 메모리를 필요로 한다.

단점

  • 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
    • 퀵 정렬의 불균형 분할을 방지하기 위해 피봇을 선택할 때 리스트를 더욱 균등하게 분할할 수 있는 데이터를 선택한다.
    • Ex) 리스트 내의 몇 개의 데이터 중에서 크기순으로 중간 값을 피봇으로 선택한다.

시간 복잡도

  • 평균, 최선 : O(NlogN)
  • 최악 : O(N^2)

일반적으로는 O(NlogN)의 성능을 나타내지만,
피봇이 항상 최솟값이나 최댓값으로 잡힙다면 최악의 성능인 O(N^2) 나온다.
이미 정렬된 리스트에 대해서 첫 번째 원소 혹은 마지막 원소를 피봇으로 선택할 경우 최악의 성능을 맛 볼 수 있다.

그래서 중간 값을 피봇으로 선택하는 것이 시간 복잡도가 최악의 경우인 O(N^2)을 피할 수 있는 방법이기도 하다.

느낀 점

정렬 알고리즘은 크게 보면 두 가지 분류로 나눌 수 있을 것 같다.

  • 단순(구현이 간단)하지만 비효율적인 방법
    • 삽입 정렬, 선택 정렬, 버블 정렬
  • 복잡하지만 효율적인 방법
    • 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

이 중에서 퀵 정렬이 가장 어려웠다. 개념을 이해하고 코드를 보는데 이해가 되지 않았다. 여러 사람들이 정리한 블로그를 참고해서 코드를 보니까 조금씩 구현이 달라서 방향을 잡지 못했다.

그래서 2개의 블로그를 참고해서 코드를 돌려보면서 실제로 디버깅을 해보니까 이해가 확실히 갔다. 생각보다 정렬 알고리즘이 재미있었다. 기억력이 오래 갔으면 좋겠지만 아닐 수도 있으니 빠른 시일 내에 복습을 해야겠다.

참고

Comment and share

정렬 알고리즘은 개발자 면접을 보기 위해서 꼭 필요한 내용이다.
하나씩 정리해보고 숙지해보자.
정렬 알고리즘은 다음과 같이 간단하게 나눠볼 수 있다.

  • 단순하지만 비효율적인 방법
    • 선택 정렬, 삽입 정렬, 버블 정렬
  • 복잡하지만 조금 더 효율적인 방법
    • 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

Q. 정렬은 왜 사용할까?
탐색을 빠르게 하기 위해서 정렬을 한다.
하지만 정렬 방법은 많고 이 중에서 제일 빠른 걸 사용해야 한다.
같은 시간 복잡도를 갖더라도 요소에 따라 달라질 수 있으니 알아보자.

# 선택 정렬

기본이 되는 정렬 중 하나이다. 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 현재 위치에 저장될 값의 크기가 작냐, 크냐에 따라서 최소 선택 정렬(오름차순으로 정렬)과 최대 선택 정렬(내림차순으로 정렬)이 있다.

기본로직은 아래와 같다.

  1. 정렬되지 않은 인덱스의 맨 앞에서부터 이를 포함한 그 이후 배열의 값 중 가장 작은 값을 찾는다.
  2. 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
  3. 다음 인덱스에서 위의 과정을 반복한다.

쉽게 설명하면 기준이 되는 수와 나머지 수를 비교해서 가장 작은 수를 앞으로 계속 보내는 정렬이다. 간단하지만 매우 비효율적이다.

최악의 경우, 최선의 경우, 평균적인 경우 모두 시간 복잡도 : O(N^2)을 갖는다.

장점

  • 데이터의 양이 적을 때 좋은 성능을 나타냄
  • 적은 값을 선택하기 위해서는 비교는 여러번 수행되지만 교환횟수가 적다.

단점

  • 100개 이상의 자료에 대해서는 속도가 급격히 떨어져 적절히 사용되기 힘들다.

# 버블 정렬

  • 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘을 갖는다.
    • 인접한 2개의 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
  • 선택 정렬과 기본 개념이 유사함.

기본 로직은 아래와 같다.

  1. 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를 … n-1번째 자료와 n번째 자료를 비교하여 교환하면서 자료를 정렬한다.
  2. 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동한다.
  3. 이렇기 때문에 2회전에서는 맨 끝에 있는 자료가 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

쉽게 설명하면 현재 원소와 다음 원소를 비교해서 큰 원소를 뒤로 보내는 정렬이다.

최악의 경우, 최선의 경우, 평균적인 경우 모두 시간 복잡도 : O(N^2)을 갖는다.
이미 정렬된 데이터에 대해서 검사하는데는 O(N)으로 간단하게 할 수 있다.

장점

  • 구현이 쉽다.
  • 이미 정렬된 데이터를 정렬할 때 가장 빠르다.

단점

  • 다른 정렬에 비해 정렬 속도가 느리다.
  • 역순배열을 정렬할 때 가장 느리다.
  • 정말 비효율적이라 거의 쓰이지 않는다.

# 삽입 정렬

삽입 정렬의 기본 개념은 손안의 카드를 정렬하는 방법과 유사하다.

  • 새로운 카드를 기존의 정렬된 카드 사이에 올바른 자리를 찾아 삽입한다.
  • 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.
  • 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘.
  • 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

기본 로직은 아래와 같다.

  • 오름차순을 기준으로 정렬한다.
  1. 기준이 되는 인덱스는 두 번째 자료부터 시작한다. 이 기준이 되는 인덱스를 Key라고 하겠다. Key가 들어갈 자리를 찾는게 핵심이다.
  2. Key는 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료들을 뒤로 옮기고 지정한 자리에 Key 자료를 삽입하여 정렬한다.
  3. 즉, 두 번째 자료는 첫 번째 자료와 비교하고 세 번째 자료는 두 번째와 첫 번째 자료 … 이런 방식으로 비교해서 기준이 되는 자료가 들어갈 위치를 찾는다.
  4. 최종적으로 Key가 들어갈 위치를 찾았다면 자료들을 한칸씩 뒤로 이동시키고 그 자리에 삽입한다.

쉽게 말하면 기준이 되는 인덱스의 앞쪽(왼쪽)을 검사하여 기준이 되는 인덱스가 들어갈 자리를 찾아서 삽입하는 정렬이다.

최악의 경우 : O(N^2) - 자료가 역순으로 정렬되어 있을 경우/작은 값이 뒤에 몰려있을 경우
최선의 경우 : O(N) - 이동없이 1번의 비교만 이루어질 경우
평균적인 경우 : O(N^2)

장점

  • stable한 정렬 방법
  • 적은 수를 정렬할 경우 알고리즘 자체가 간단해서 다른 복잡한 정렬 방법보다 유리할 수 있다.
  • 대부분의 수가 이미 정렬되어 있는 경우에 매우 효율적이다.

단점

  • 비교적 많은 수들의 이동을 포함한다.
  • 비교할 수가 많고 크기가 클 경우에 적합하지 않다.

결론

위에서 살펴본 정렬 알고리즘들은 비교적 구현이 간단하다. 그리고 이해하기도 어렵지 않다. 하지만 속도가 느리다는 단점이 존재한다. 다음에는 이보다 속도가 좋은 정렬 알고리즘을 살펴보도록 하겠다.

stable과 unstable

  • stable : 정렬할 때 같은 값을 가진 수들이 정렬 전과 정렬 후에 순서가 바뀌지 않는 경우
  • unstable : 정렬할 때 같은 값을 가진 수들이 정렬 전과 정렬 후에 순서가 바뀌는 경우

다음의 예를 한 번 생각해보자.
ex) 5, 4, 8, 8, 5, 3, 1, 10, 6
숫자가 있고 순서를 부여해보자.
ex 5(1), 4(2), 8(3), 8(4), 5(5), 3(6), 1(7), 10(8), 6(9)

()안의 숫자는 해당 노드(수)가 들어온 순서를 뜻한다. 만약 정렬할 시에 key 값을 기준으로 정렬을 하되, 같은 key 값을 가진 노드는 들어온 순서에 따라 다시 정렬되어야 한다면 어떻게 할 것인가? 다음 결과와 같이 최종적으로 정렬된 정보가 바로 stable한 것이다. 정렬된 결과는 다음과 같다.

ex) 1(7), 3(6), 4(2), 5(1), 5(5), 6(9), 8(3), 8(4), 10(8)

  • 선택 정렬 : unstable

ex) 5(1), 4(2), 5(3), 2(4), 3(5)
위에서 5(1)과 2(4)를 교환한다.
ex) 2(4), 4(2), 5(3), 5(1), 3(5)
위의 결과가 나온다. 처음의 순서를 유지하지 않게 된다. 이러한 이유로 선택 정렬은 stable한 결과를 보장할 수 없기 때문에 unstable하다고 한다.

  • 버블 정렬 : stable
  • 삽입 정렬 : stable

참고

Comment and share

  • page 1 of 1
Author's picture

VictoryWoo

기록을 통해 사람들과 공유하는 것을 좋아합니다.


Android Developer