학습 목표

  • BFS 알고리즘의 개념 및 동작 과정을 이해한다.   
  • BFS 알고리즘을 구현한다.
  • BFS 알고리즘의 시간 복잡도를 분석한다.

 

너비 우선 탐색(BFS, Breadth First Search)

1. 너비 우선 탐색이란?

 너비 우선 탐색은 깊이 우선 탐색처럼 그래프를 탐색하는 알고리즘입니다. 깊이 우선 탐색과는 다르게 시작 정점에서 가까운 정점부터 탐색해 나가는 방식입니다. 다시 말해, 출발 정점으로부터 탐색을 시작해 먼저 발견된 정점을 탐색한다고 생각하시면 됩니다. 어디서 비슷한 느낌의 자료구조를 보신 적이 있으실 겁니다! 바로 먼저 들어온(First In) 데이터를 먼저 처리(First Out)하는 Queue 입니다. 갑자기 이처럼 Queue를 언급하는 이유는 너비 우선 탐색에서 사용되기 때문입니다. 자세한 내용은 밑에서 설명해드리도록 하고 너비 우선 탐색의 간단한 활용처를 말씀드리겠습니다.

 

 너비 우선 탐색은 위에서 언급했듯이 출발 정점에서 가까운 정점을 우선적으로 탐색한다는 특징을 갖고 있습니다. 이는 다르게 해석하면 출발 정점으로 가까운 거리에 있는 정점을 탐색한다는 말이며, 어떤 조건에서의 최단 거리 혹은 최솟값을 찾는 데 활용됩니다. 나중에 다룰 최단거리 알고리즘인 다익스트라의 기본이 되기도 합니다. 개인적인 경험을 더해 말씀드리자면, 위에서 언급한 개념 및 특징을 기반으로 여러 기업의 코딩테스트에서 자주 출제되는 개념입니다. 그렇기 때문에 이전 포스팅과는 다르게 글 하단에 너비 우선 탐색을 활용해 해결할 수 있는 알고리즘 문제도 링크를 기재했으니 욕심이 있으신 분들은 한번 해결해보시길 추천드립니다. 이제부터 본격적으로 너비 우선 탐색에 대해서 설명해드리도록 하겠습니다.

 

2. 알고리즘 동작 과정

  1. 출발 정점번호에 대한 방문 정보를 갱신하고, Queue 에 Push한다.
  2. Queue 에서 하나의 정점(현재 정점)을 꺼낸다.
  3. 현재 정점과 연결된 다른 정점의 방문 정보를 확인한다.
  4. 연결된 정점이 이미 방문된 상태라면 무시하고, 그렇지 않다면 방문 정보를 갱신 후 Queue에 Push한다.
  5. 2~4 과정을 Queue 에 정점이 들어있지 않을 때 까지 반복한다.

 

* 여기서 왜 방문표시를 먼저하고, Queue 에 push 하는지 궁금하신 분이 있으실 것 같습니다. 그 이유는 너비 우선 탐색은 먼저 방문한 정점을 먼저 탐색한다고 말씀드렸습니다. 그렇기 때문에 한 정점이 먼저 등장했다는 것은 나중에 발견돼도 이미 방문되어 있을 것이라는 의미입니다. 따라서 이미 발견된 정점을 큐에 push 하는 행위는 무의미한 행위입니다. 오히려 쓸모없는 연산이 발생하는 것입니다. 따라서 확인되는 순간  방문 표시를 하는 것입니다. 아직도 헷갈리신다면, "방문 표시"를 발견 여부를 체크했다고 해석하셔도 좋습니다.

 

 

3. 소스코드

- 인접 행렬

#include <iostream>
#include <queue>

using namespace std;

int g[5][5], start; 
bool visited[5];
queue<int> q;
void addEdge(int u, int v){
    g[u][v] = 1;
    g[v][u] = 1;
}
int main(){
    
    //간선 추가
    addEdge(0,1);
    addEdge(2,3);
    addEdge(3,4);
    addEdge(4,1);

    //시작 정점을 큐에 push
    cin >> start;
    visited[start] = true;
    q.push(start);

    while(!q.empty()){
        //정점 방문
        int now = q.front();
        q.pop();
        cout << now << " 방문\n" ;

        //인접 행렬로 구현하여 간선 유무를 직접 조사한다.
        for(int i = 0; i < 5; i++){
            //now 정점과 i 정점 사이의 간선이 존재하고 i 정점을 방문하지 않았을 때
            if(g[now][i] && !visited[i]){
                //방문 표시 후 큐에 입력
                visited[i] = true;
                q.push(i);
            }
        }
    }
    return 0;
}


- 인접 리스트

#include <iostream>
#include <queue>
#include <list>

using namespace std;

int start; 
bool visited[5];
queue<int> q;
list<int> g[5];
void addEdge(int u, int v){
    g[u].push_front(v);
    g[v].push_front(u);
}
int main(){
    
    //간선 추가
    addEdge(0,1);
    addEdge(2,3);
    addEdge(3,4);
    addEdge(4,1);

    //시작 정점을 큐에 push
    cin >> start;
    visited[start] = true;
    q.push(start);

    while(!q.empty()){
        //정점 방문
        int now = q.front();
        q.pop();
        cout << now << " 방문\n" ;

        //인접 행렬로 구현하여 간선 유무를 직접 조사한다.
        for(list<int>::iterator iter = g[now].begin(); iter != g[now].end() ; iter++){
            //iter이 가르키는 정점을 방문하지 않았을 때
            if(!visited[*iter]){
                //방문 표시 후 큐에 입력
                visited[*iter] = true;
                q.push(*iter);
            }
        }
    }
    return 0;
}


4. 시간복잡도

 BFS 의 시간복잡도는 그래프 표현 방법에 따라서 달라집니다. 인접 행렬로 그래프를 표현했다면 한 정점에서 다른 정점간의 간선 유무를 파악하기 위해서는 직접 조사를 해야 합니다. 이 과정에서 유효하지 않은 간선(g[u][v]==0)도 조사해야 하기 때문에 인접 행렬의 경우 행렬 크기인 O(V^2)의 시간 복잡도가 소요됩니다. 인접리스트는 인접 행렬과는 다르게 그래프에 유효한 간선만 리스트 형태로 가지고 있습니다. 그렇기 때문에 각 정점을 도는 데 O(V) 만큼의 시간 복잡도와 유효 간선을 파악하는 데 O(E) 만큼의 소요합니다. 따라서 인접리스트는 O(V+E) 만큼의 시간복잡도를 보입니다.

 

5. 정리

  • 시작 정점에서 가까운 정점부터 탐색해 나가는 방식의 그래프 탐색 알고리즘이다.
  • 알고리즘의 동작 구조상 Queue 를 사용한다.
  • 특정 조건에서의 최단 거리 혹은 최솟값을 찾는 데 활용된다.
  • 인접 행렬로 구현하면 O(V^2) 의 시간복잡도를 갖고, 인접리스트로 구현하면O(E+V)의 시간복잡도를 갖는다. 

6. 관련 문제

★☆단지 번호 붙이기 https://www.acmicpc.net/problem/2667

 https://www.acmicpc.net/problem/5427 

통나무 옮기기 https://www.acmicpc.net/problem/1938

학습 목표

  • DFS 알고리즘이 무엇인지 이해한다.

  • DFS 알고리즘의 동작 과정을 이해한다.

  • DFS 알고리즘을 소스코드로 구현한다.

 

깊이 우선 탐색(DFS, Depth-First Search) 알고리즘이란?

 그래프 탐색 알고리즘입니다. 그래프 탐색 알고리즘은 그래프 내 모든 정점을 방문하는 방법입니다. DFS는 이름에서 알 수 있듯이 깊이를 우선시하는 탐색 알고리즘입니다. 다시 말해, 한 정점에서 연결된 간선을 살펴보면서 방문 가능한 정점이 있다면, 즉시 방문하는 방식으로 동작하는 알고리즘입니다. 

 

 위에서 언급했듯이 방문 가능한 정점이 있으면 바로 방문합니다. 이 동작 방식은 재귀 호출을 사용하여 구현하면 간단하게 구현됩니다. 정점을 방문하는 과정을 함수 호출, 더 이상 방문할 정점이 없을 경우 이전 정점으로 돌아오는 과정을 함수 리턴으로 생각해 구현합니다.

 

탐색 과정

알고리즘의 동작 과정은 다음 세 단계로 이루어집니다.

 

1. 탐색 시작 정점을 방문합니다.

2. 현재 정점(또는 시작 정점)에서 연결된 간선을 순차적으로 탐색합니다.

  • 탐색 중인 정점이 방문한 정점이라면, 다음 정점을 확인합니다.

  • 탐색 중인 정점이 방문하지 않은 정점이라면 이 정점을 방문하여 2번 과정을 진행합니다.(재귀 호출)

3. 더 이상 방문할 정점이 없다면 탐색을 끝냅니다.(함수 리턴)

 

 

 

 

소스 코드(인접 행렬)

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
#include <stdio.h>
#define TRUE 1
#define FALSE 0
bool visited[6];
int g[6][6]; //양방향 그래프
void addEdge(int u, int v) {
    g[u][v] = 1;
    g[v][u] = 1;
}
void dfs(int nowVertex) {
    printf("정점 %d 를 방문했습니다.\n", nowVertex);
    //방문 표시
    visited[nowVertex] = TRUE;
 
    //방문하지 않은 정점 조사
    for (int i = 0; i < 6; i++) {
        //연결되어 있고, 방문하지 않았다면
        if (g[nowVertex][i] == 1 && !visited[i]) {
            dfs(i);
        }
    }
}
int main() {
    addEdge(01);
    addEdge(02);
    addEdge(12);
    addEdge(13);
    addEdge(14);
    addEdge(25);
    for (int i = 0; i < 6; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    return 0;
}
 

시간 복잡도

 시간 복잡도 분석을 위해 두 가지 그래프 형태를 고려하겠습니다. 우선, 주어진 그래프가 인접 리스트일 경우에는 모든 정점을 확인하는 복잡도인 |V|, 각 정점에서 연결된 간선들을 확인하는 과정에서 |E| 만큼 소요됩니다. 따라서 인접 리스트 형태의 그래프를 DFS 방식으로 탐색할 경우 O(|V|+|E|) 만큼의 시간 복잡도를 보입니다.

 

 그래프가 인접 행렬 형태로 주어진다면 각 정점에서 연결된 간선들을 확인하는데 |V| 만큼 시간 복잡도가 필요합니다. 따라서 인접 행렬 형태의 그래프를 DFS 방식으로 탐색할 경우 O(|V|^2) 만큼의 시간 복잡도를 보입니다.

 

정리

  • 그래프 상의 모든 정점을 깊이 우선 방식으로 탐색하는 알고리즘이다.

  • 방문 가능한 정점이 있다면 즉시 방문하는 방식으로 동작한다.

  • 동작 원리를 고려해 재귀 함수로 구현하면 간단하다.

  • 시간 복잡도는 인접 리스트로 구현 시 O(|V|+|E|), 인접 행렬로 구현 시 O(|V|^2)이다.

 

안녕하세요!


그래프 알고리즘을 배우기 전에 반드시 알아야 할 부분이 있습니다!


바로 그래프의 표현 방법입니다.  그래프 관련 문제를 해결하기 위해서는 주어진 그래프를 표현해야 하고,


그 데이터를 바탕으로 그래프 알고리즘을 적용시켜 해결해야 합니다. 


그럼 이제 본격적인 설명에 앞서, 그래프를 표현하는 방법에는 어떤 것들이 있는지 간단한게 알아보고 가도록 하겠습니다.


그래프를 표현하는 방법은 세 가지가 있습니다.


  • 인접 행렬(Adjacency matrix) : 두 노드간의 엣지 상태를 행렬 형태로 표현
  • 인접 리스트(Adjacency list) : 각 노드 별로 연결되어있는 노드들만 표현
  • 간선 리스트(Edge list) : 위의 방법들과 달리 엣지만을 리스트 형태 혹은 배열 형태로 저장하는 방법입니다.

[그래프1 - 방향이 없는 그래프]

[그래프2 - 방향이 있는 그래프]



이제부터 위 그래프를 각 방법으로 표현해 보겠습니다.


인접 행렬(Adjacency matrix)


[그래프1 - 인접 행렬]

[그래프2 - 인접 행렬]



인접 행렬은 노드와 노드 사이의 관계를 행렬 형태로 표현하는 방법입니다.


위 행렬에서 표현된 값이 0이면 노드 자신을 의미, INF면 직접적으로 연결 X, 나머지 값들은 연결된 엣지의 가중치입니다.


그래프 형태에 따라서 간선의 방향이 없으면 대칭행렬 형태로, 방향이 있다면 일반 행렬처럼 표현하면 되는 방식입니다.


이 특성때문에 인접 행렬 방식은 다음과 같은 특징을 같습니다.


1) 두 노드간의 엣지에 직접 접근할 수 있습니다. 예) g[4][2] : 4번노드와 2번노드의 엣지


2) 모든 노드쌍의 관계를 표현해야 하기 때문에 공간복잡도가 O(V^2) 소요됩니다.


따라서 인접 행렬은 밀집 그래프(엣지수가 많은) 형태에서 좋은 성능을 발휘하고 적절한 공간을 소요한다고 여겨지지만,


희소그래프(엣지수가 적은) 형태에서는 공간낭비가 매우 심합니다.(어떤 문제에서는 이 특성때문에 메모리 초과가 발생하기도 합니다)



인접 리스트(Adjacency list)


 

 [그래프1 - 인접 행렬]

 

[그래프2 - 인접 행렬]


이 방법은 인접 행렬에서 INF와 같은 불필요한 데이터를 제거하고, 실제 존재하는 그래프만을 표현하기 위한 방식입니다.


표현하는 방법은 정점을 기준으로 연결되어 있는 간선을 리스트형태 추가시켜 나가면 됩니다. 


방향이 없는 그래프라면 각 두 노드 리스트에 [상대 노드, 가중치] 형태를 갖는 자료구조를 추가해주면 됩니다.


반면에 방향이 있다면, 출발 노드 리스트에 [목적지 노드, 가중치] 형태를 갖는 자료구조를 추가해주면 됩니다.


이런 리스트적 특징 때문에 인접 리스트에서는 다음 특징을 갖습니다.


1) 두 노드간의 엣지가 존재 여부를 조사하기 위해서는 순차 탐색을 해야하기 때문에 O(V) 시간이 소요됩니다.


2) 인접 행렬과는 달리, 존재하는 엣지만을 표현하기 때문에 O(E) 만큼의 공간이 소요됩니다.


위 특징 때문에 모든 엣지 혹은 적은 엣지를 조사해야하는 그래프 알고리즘에서 유용하게 활용됩니다. 


하지만, 밀집 그래프 형태의 문제에서는 1번 특징으로 인해 시간 초과 문제가 발생할 수 있습니다.



간선 리스트(Edge list)


 

 


간선 리스트는 다른 두 방식과는 달리 엣지를 중심으로 표현하는 방법입니다.


즉, 단순하게 [노드1(혹은 출발 노드), 노드2(혹은 도착 노드), 가중치] 형태의 자료구조를 리스트 또는 배열 형태로 저장하는 방식입니다.


따라서 모든 엣지를 살펴보는 알고리즘에서 간편하고 직관적으로 활용할 수 있습니다.




각 방법을 사용해서 주어진 그래프를 표현해 봤습니다.


코드 레벨에서 설명하지는 않았지만, 이는 앞으로 다룰 그래프 관련 알고리즘에서 적어도 한 번씩은 다룹니다.


그때 코드 레벨에서 설명해드리도록 하겠으니 "아! 이런 방식이구나" 정도의 느낌만 알고 가시면 됩니다!

안녕하세요 고급 정렬 알고리즘 두 번째이자 마지막 시간입니다!


힙 정렬이 하나 더 있기는 하지만 별도의 자료구조가 필요하기 때문에 추후에 다루도록 하겠습니다.


그럼 빠르게 본론으로 들어가보겠습니다!


합병 정렬(Merge sort) - 안정 정렬(Stable sort)


합병 정렬은 데이터를 이분할 하는 작업을 반복하여 크기가 1인 데이터까지 분할하고, 


데이터들을 정렬해 나가며 최종적으로 완전 정렬하는 알고리즘입니다.


즉, 분할 정복 기법을 이용한 정렬 방법입니다.


따라서 합병 정렬은 분할, 정복(정렬) 이 두 단계로 이루어져 있습니다.


그림과 함께 조금 더 자세하게 설명해 드리도록 하겠습니다.


- 분할 단계



맨 처음 정렬해야 하는 데이터(7-3-2-1-5-4-6) 가 있습니다.


우선, 주어진 데이터의 인덱스를 0(start)~6(end)번이라고 생각해 보겠습니다.


이를 이분할 하기 위해서 중간점(mid)를 계산해야 하며 mid 는 다음과 같이 계산됩니다.


mid = (start + end) / 2


그렇게 되면 전반부 구간은 start~mid, 후반부 구간은 mid+1~end로 정할 수 있습니다.


이러한 구간 정보를 아래와 같이 분할 함수의 인자로 넘겨주는 작업을 반복(재귀)적으로 수행합니다.


분할(data, start, end){

mid = (start+end) / 2;

분할(data, start, mid);

분할(data, mid+1, end);

}


그렇게 되면 주어진 데이터는 최종적으로 크기가 1인 데이터 까지 분할됩니다.



- 정복(정렬) 단계



정복 단계에서는 분할된 구간을 정렬해 나가면서 부분 문제를 해결합니다.


즉, 분할 이후에 정복 과정을 거치게 되는 것이죠. 간략하게 표현하자면 다음과 같습니다.


분할(data, start, end){

mid = (start+end) / 2;

분할(data, start, mid); //부분 문제 해결로 전반부 정렬 완료

분할(data, mid+1, end); //부분 문제 해결로 후반부 정렬 완료

정복(data, start, mid, end); //전반부와 후반부를 비교하며 정렬

}


이제 정복함수의 간략적인 구성에 대해서 알아보도록 하겠습니다.


정복 함수는 크게 두 단계로 이루어져 있는데, 바로 임시 배열을 채우는 과정원래 배열에 임시 배열 값을 복사하는 과정입니다.


1) 전반부와 후반부 데이터를 비교하며 임시 배열 채우기


오름차순으로 정렬한다면, 전반부와 후반부의 데이터 중 작은 값을 비교해가며 임시 배열을 채웁니다.


이 과정을 전반부 혹은 후반부의 데이터가 빌 때 까지 진행하고, 이후 남은 데이터를 일괄적으로 채워주면 됩니다.


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
#include <cstdio>
int temp[7]; //정렬을 위한 임시 배열
//병합 함수 정의
void merge(int* a, int start,int mid, int end) {
    int firstPart = start;
    int lastPart = mid + 1;
    int savePoint = start;
 
    //전반부와 후반부를 비교하며 임시배열에 복사
    while ((firstPart <= mid) && (lastPart <=end)) {
        if (a[firstPart] <= a[lastPart])
            temp[savePoint++= a[firstPart++];
        else
            temp[savePoint++= a[lastPart++];
    }
 
    //전반부의 값이 남아 있다면
    while (firstPart <= mid)
        temp[savePoint++= a[firstPart++];
 
    //후반부의 값이 남아 있다면
    while (lastPart <= end
        temp[savePoint++= a[lastPart++];
 
    //임시 배열의 값을 원래 배열에 복사
    for (int i = start; i <= end; i++)
        a[i] = temp[i];
}
//분할 함수 정의
void partion(int * a, int start, int end) {
    int mid;
    if (start < end) {
        mid = (start + end/ 2;
        partion(a, start, mid); //전반부 - 분할 과정
        partion(a, mid + 1end); //후반부 - 분할 과정
        merge(a, start, mid, end); //병합 - 정복 과정
    }
}
int main() {
    int a[7= { 7,3,2,1,5,4,6 };
    partion(a,06);
    for (int i = 0; i < 7; i++)
        printf("%d ", a[i]);
    return 0;
}
cs


* 소스코드 라인별 설명은 주석으로 대체하겠습니다! *

시간 복잡도




합병 정렬의 경우에는 퀵 정렬과 달리, 항상  을 보장합니다.


그 이유는 매번 이분할을 하기 때문에 분할된 구간의 크기가 항상 일정하게 형성됩니다.


따라서 위 그림처럼 크기가 N인 데이터를 이분할 했을 경우에는 의 분할이 존재하게 되고,


이 각 분할에 대해서 N번의 비교가 이루어지기 때문에 항상  을 보장합니다.


이러한 특성 때문에 합병 정렬은 안정적인 성능을 보장하는 정렬 방법으로 알려져 있습니다.


다만 합병 정렬의 경우에는 소스 코드에서 볼 수 있듯이, 정렬하기 위한 추가적인 공간이 필요하다는 특징을 가지고 있습니다.




이번 포스팅에서 준비한 내용은 여기까지 입니다!


이제 드디어 정렬이 끝났습니다. 


다음 포스팅 부터는 본격적으로 그래프 관련 알고리즘에 대해서 알아보도록 하겠습니다.


그래프 관련 알고리즘들은 코딩테스트에서도 많이 출제되는 부분이니 더 힘내서 공부해주시기 바라겠습니다!


드디어 고급 정렬에 들어왔습니다.


이번에는 고급 정렬 알고리즘 중 하나인 퀵 정렬에 알아보도록 하겠습니다.


취업을 위해 알고리즘 문제를 풀게 되는데, 정렬은 이러한 문제를 푸는 데 많이 사용됩니다.


저도 문제를 풀다가 정렬을 해야할 경우 퀵 정렬을 많이 사용하곤 합니다. (왜냐하면 이름처럼 빠르기 때문이죠!)


그럼 이제부터 본격적으로 퀵 정렬에 파헤쳐 보도록 하겠씁니다.



퀵 정렬(Quick sort) - 불안정 정렬(Unstable sort)


퀵 정렬은 전체를 분할 중심보다 작은 구간, 큰 구간 으로 나누는 작업을 재귀적으로 수행하여 정렬하는 알고리즘입니다.


즉, 분할 정복 기법을 활용하는 방법입니다.


동작 하는 과정은 다음과 같습니다.




1) 분할 중심(Pivot)값 을 정합니다.

(분할 중심을 정하는 방법은 여러 가지가 있는데, 저는 마지막 원소를 분할 기준으로 정하는 방법을 사용하도록 하겠습니다.)




2) 주어진 데이터 구간을 분할 중심을 기준으로 대소 관계에 따라 두 구간으로 나눕니다.




3) 분할된 구간 중 기준 값보다 큰 구간의 첫 번째 값과 분할 중심 값을 교환합니다.




4) 나누어진 두 구간 각각에 대해서 1~3 번 과정을 반복(혹은 재귀적)으로 수행합니다.



이렇게 나누고 정렬하는 작업을 분할할 공간이 없을 때 까지 진행하면 정렬은 끝입니다!



 

소스 코드


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
#include <cstdio>
#define SWAP(x,y,temp) ((temp)=(x),(x)=(y),(y)=(temp)) 
 
//분할
int partion(int * a, int left, int right) {
    //마지막 값을 분할 기준으로 설정
    int pivotValue = a[right];
    int temp;
    int i = left;
    //주어진 구간을 탐색하며 두 구간으로 분리
    for (int j = left; j < right; j++) {
        if (a[j] < pivotValue) {
            SWAP(a[j], a[i], temp);
            i++;
        }
    }
    //작은 구간과 큰 구간 사이에 분할기준 삽입
    SWAP(a[i], a[right], temp);
    return i;
}
 
//퀵 정렬
void quicksort(int * a, int left, int right) {
    int newPivotIndex;
    if (right > left) {
 
        //분할의 결과로 a배열은 pivot을 기준으로 좌측에는 작은 값 우측에는 큰 값이 위치
        newPivotIndex = partion(a, left, right);
 
        //작은 구간에 대해서 재귀적으로 퀵 정렬 진행
        quicksort(a, left, newPivotIndex - 1);
 
        //큰 구간에 대해서 재귀적으로 퀵 정렬 진행
        quicksort(a, newPivotIndex + 1, right);
    }
}
int main() {
    int a[7= { 7,3,2,1,5,4,6 };
 
    quicksort(a, 06);
 
    for (int i = 0; i < 7; i++)
        printf("%d ", a[i]);
 
    return 0;
}
cs

배열 a : 정렬하고자 하는 데이터 원본 입니다.

Line 11 - 16 : 분할 중심을 기준으로 작은 구간과 큰 구간으로 분리합니다. ( 2) 에 해당하는 과정)

Line 18 : 큰 구간의 첫 번째 값과 분할 중심을 교환합니다. ( 3) 에 해당하는 과정)

Line 19 : 분할 중심의 Index 값을 반환합니다.

Line 28 : 주어진 배열에 대해서 구간을 분리하는 Partion 함수를 호출하고 분할 중심의 Index 값을 구합니다.

Line 31 : 작은 구간에 대해서 재귀적으로 수행합니다.

Line 34 : 큰 구간에 대해서 재귀적으로 수행합니다.



시간 복잡도


우선, 앞서 설명했던 알고리즘 들과 같이 최악의 경우를 고려한 시간 복잡도를 말씀 드리겠습니다.


퀵 정렬에서 최악의 경우는 분할 기준이 매번 제일 크거나 작은 값으로 선택되는 상황입니다.


다시 말해, 이미 정렬된 데이터에 대해서 퀵 정렬을 수행하는 경우입니다.


이럴 때, 분할은 결국 N-1 번 발생하고 각 분할당 최소 1번부터 최대 N-1 번까지 비교하게 됩니다.


그렇게 된다면 결국 퀵정렬의 최악의 경우는 복잡도를 가지게 됩니다.


그럼에도 퀵 정렬을 사용하는 포인트는 다음과 같습니다.


1) 평균적인 경우를 고려하자!







우선 분할의 가장 이상적인 경우는 반반씩 나뉘는 것입니다.


다시 말해, 매 분할마다 정렬해야할 데이터의 크기가 반씩 줄어든다는 의미입니다.


따라서 그럴 경우에는  만큼 분할이 발생하고 각 분할마다 최대 N번의 데이터 비교가 발생합니다.


이런 경우에는 분할 깊이 * 비교 횟수인  시간 복잡도를 가집니다.


2) 분할 기준이 다음 정렬의 대상이 아니다!


퀵 정렬의 경우에는 분할 기준이 다음 정렬에서 정렬 대상이 포함되지 않습니다.


그렇기 때문에,  만큼의 깊이를 가져가는 정렬 방법에서 매우 효과적입니다.



왜 불안정 정렬인가?


선택 정렬이 불안정 정렬임을 보였을 때 처럼 아주 간단한 예시를 보여드리겠습니다.

(이번에도 제가 자주 사용하는 카드를 통해서 알아보겠습니다!)


우선 아래와 같이 스페이스3 - 하트5 - 클로버5 있다고 생각해 봅시다!



원본 데이터가 정렬되어 있지만, 보통 우리는 데이터가 정렬되있다고 판단하기 어렵습니다.


그렇기 때문에 데이터의 정렬 상태를 파악하지 않고 정렬을 진행하게 되는 것이죠!


이제 위 카드를 퀵 정렬 수행하게 된다면,  작은 구간(스페이스 3) / 큰 구간(하트 5) /정렬기준(클로버 5) 분리 됩니다.




그리고 나서 분할 기준(클로버 5)을 큰 구간의 첫 번째 값(하트 5)과 교환하게 됩니다.


교환 후에, 재귀적으로 수행하기 위해서 인덱스 위치를 살펴보니 더 이상 정렬할 구간이 없으므로 종료하게 됩니다.



결과를 살펴보면 기존에는 숫자 5를 가진 카드는  하트5 - 클로버5 순서로 존재했지만,


정렬 후에는 클로버 5 - 하트 5 순서로 존재함을 확인 할 수 있습니다.


따라서 퀵 정렬은 불안정 정렬이 됩니다.


여기서 추가적으로 분할 기준을 다르게 잡으면 가능할까? 라는 생각을 가지신 분들이 있을 수도 있습니다.


하지만, 퀵 정렬의 경우에는 분할 기준과의 값에 대한 교환이 필연적으로 나올 수 밖에 없기 때문에 불안정 정렬이 됩니다. 



퀵 정렬에 대한 내용은 여기까지입니다! 다음 포스팅에서는 퀵 정렬과 가장 많이 비교되는 병합 정렬에 대해서 알아보겠습니다!


개인적인 일 때문에 이번 포스팅이 많이 늦어졌는데 다음 포스팅 부터는 최대한 노력해서 빨리 올려볼게요!


감사합니다 : ) 

이번 시간에는 기본 정렬의 마지막 선택 정렬입니다.


선택 정렬은 버블, 삽입 정렬과 다르게 불안정 정렬입니다.


이 부분에 대해서 글 마지막 부분에 추가적으로 설명해 드리니 집중해서 봐주세요!




선택 정렬(Selection sort) - 불안정 정렬(Unstable sort)


선택 정렬은 매 회전마다 가장 적합하다고 판단되는 값을 선택해 나가는 방법이다.


만약 오름차순으로 정렬한다면, 매 회전마다 가장 작은 값을 선택해 맨 앞 자리 수와 교환하는 것 입니다.

(맨 앞 자리는 i번째 회전 때 배열의 i번째 요소입니다.)


반대로 내림차순으로 정렬한다면, 매 회전마다 가장 큰 값을 선택해 맨 앞 자리 수와 교환하는 것 입니다.


여기서 선택을 한다는 의미는 해당 인덱스를 기억해 맨 앞자리 원소와 교환한다는 의미입니다.


조금 더 자세하게 그림으로 보여드리겠습니다.



1회전 : 

배열의 처음부터 끝까지 탐색하여 최적 값(1)의 Index를 찾습니다.

그리고 선택 위치 Index의 값(7)과 최적 값(1)을 교환합니다.


2회전 :

배열의 두 번째 부터 끝까지 탐색하여 최적 값(2)의 Index를 찾습니다.

그리고 선택 위치 Index의 값(3)과 최적 값(2)을 교환합니다.


3회전 :

배열의 세 번째 부터 끝까지 탐색하여 최적 값(3)의 Index를 찾습니다.

그리고 선택 위치 Index의 값(3)과 최적 값(3)을 교환합니다.


4회전 :

배열의 네 번째 부터 끝까지 탐색하여 최적 값(5)의 Index를 찾습니다.

그리고 선택 위치 Index의 값(5)과 최적 값(5)을 교환합니다.


데이터가 하나 남았으므로 더 이상 비교할 데이터가 없으니 끝냅니다.




소스 코드


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
#include <iostream>
 
using namespace std;
 
//교환
void swap(int * num1, int * num2){
    int temp;
    temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}
int main()
{
    int a[5= {7,3,2,1,5};
    int min;
    
    //선택 정렬
    for(int i = 0; i<4; i++){
        min = i;
        for(int j = i+1; j<5; j++){
            if(a[j] < a[min])
                min = j;
        }
        swap(&a[min],&a[i]);
    }
 
    //출력
    for(int i = 0; i<5 ; i++)
        cout << a[i] << " ";
    return 0;
}
 
cs

배열 a : 정렬하고자 하는 데이터 입니다.

min : 가장 적합한 값의 index 입니다.

Line 6-11 : Swap 함수의 정의입니다.

Line 19 : 선택 위치의 값을 제일 최적 값이라고 생각하고 시작합니다.

Line 20-23 : 선택 위치+1 부터 배열의 끝까지 탐색해 나가며 최적 값의 index를 갱신합니다. 

Line 24 : 최적 값의 위치와 선택 위치의 값을 교환합니다.




시간 복잡도


선택 정렬은 기존 데이터의 구성에 따라 비교 횟수가 변하지 않고, 


모든 비교를 진행하기 때문에 n-1 부터 1 까지 등차수열의 합입니다.


따라서 시간복잡도는 이 됩니다.




왜 불안정정렬인가?


가장 간단하게 선택 정렬시에 불안정 정렬이 되는 예를 보여드리겠습니다.


다음과 같은 카드들이 있습니다.




이 카드들에서 숫자5를 가진 카드들만 본다면 다이아몬드5 - 스페이스5의 순서를 확인 할 수 있습니다.


만약 이 상황에서 카드의 숫자를 기준으로 오름차순으로 정렬하면 1회전때 다음과 같은 교환이 일어납니다.





그리고 나서 결과를 살펴보면 아래와 같이 변합니다.



결국 1회전 이후 완전히 정렬되었으므로 2, 3, 4 회전때는 교환이 일어나지 않습니다.


최종 정렬 결과를 살펴보면 기존의 다이아몬드5 - 스페이스5 순서가 뒤바뀐 모습을 볼 수 있습니다.


이는 앞서 설명했던 불안정 정렬의 기존 순서를 보존하지 않는 특성입니다.


따라서 선택 정렬은 불안정 정렬입니다.


만약 어떤 데이터를 정렬할 때, 위와 같은 결과를 원하시지 않으면 안정 정렬 알고리즘을 선택하는 게 옳습니다.



지금까지 버블, 삽입 정렬에 이어 선택 정렬을 살펴봤습니다. 


다음 글 부터는 본격적으로 고급 알고리즘에 대해서 포스팅 해보도록 하겠습니다.


감사합니다!







이번 시간에는 저번 시간에 이어 기본 정렬 중 하나인 삽입 정렬(Insertion sort)에 대해서 알아보도록 하겠습니다.



삽입 정렬(Insertion sort) - 안정 정렬(Stable sort)


삽입 정렬이란 정렬된 구간그렇지 않은 구간 둘로 나누고, 


정렬되지 않은 구간의 맨 앞 원소를 가져와 정렬된 구간에 삽입하는 알고리즘입니다.


알고리즘의 수행 단계는 다음과 같습니다.


1) 주어진 데이터 중 맨 앞의 원소를 정렬된 구간으로 설정하고, 나머지를 그렇지 않은 구간으로 정합니다.


2) 삽입 데이터 정하기 : 정렬되지 않은 구간의 맨 앞 데이터를 삽입 데이터(key 값)로 정한다.


3) 삽입 위치 파악하며 데이터 밀어내기 : 정렬 구간을 역순으로 탐색하며 Key 값이 삽입될 위치를 파악합니다.


4) 모든 데이터가 정렬될 때까지 2-3 과정을 반복합니다.


좀 더 자세하게 그림으로 보여드리겠습니다.





이 그림을 위에서 언급한 순서와 함께 설명하자면 다음과 같습니다.


1) 주어진 데이터(7-3-2-1-5) 에서 7을 정렬된 구간으로 설정하고 나미저 3-2-1-5를 정렬되지 않은 구간으로 설정하여 시작합니다.


1 회전 : 

2) 3을 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 정렬된 구간을 7부터 역순으로 탐색하며 삽입 위치를 합니다. 이때, (Key 값 > 비교 데이터) && (더 이상 비교할 데이터가 없는가?)를 만족해야 합니다. 따라서, 조건을 비교해가며 결국 첫 번째 자리에 삽입되게 됩니다.


2 회전 :

2) 2를 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 1회전때와 마찬가지로 조건을 비교해 가며 결국 첫 번째 자리에 삽입되게 됩니다.


3 회전 :

2) 1을 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 1, 2회전때와 마찬가지로 조건을 비교해 가며 결국 첫 번째 자리에 삽입되게 됩니다.


4 회전 :

2) 5를 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 1, 2, 3회전과 달리 두 번째 비교작업때 Key 값이 비교데이터(3) 보다 크므로 조건에 위배됩니다. 따라서, 그때 빈 공간에 삽입되게 됩니다.



소스 코드


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
#include <iostream>
 
using namespace std;
 
int main()
{
    int a[5= {7,3,2,5,1};
    int key,j;
 
    //삽입 정렬
    for(int i = 1 ; i< 5; i++){
        key = a[i];
        j = i;
        while(key < a[j-1&& j>0){
            a[j] = a[j-1];
            j--;
        }
        a[j] = key;
    }
 
    //출력
    for(int i = 0 ; i< 5; i++)
        cout << a[i] << " ";
 
    return 0;
}
 
cs



배열 a : 정렬하고자 하는 데이터


key : 정렬되지 않은 구간에서 정렬 구간으로 옮기며 정렬할 값


j : key 값의 삽입 위치


Line 11: 

i 는 정렬되지 않은 구간에서 삽입할 데이터의 위치를 의미합니다. 

따라서 첫 번째 값을 정렬 구간으로 설정하기 때문에 1부터 시작합니다.


Line 12 :

정렬할 데이터를 Key 변수에 저장합니다.


Line 14 :

Key < a[j-1] -> Key 값 보다 큰 값이 이전에 있으면 계속 진행하는 조건 입니다.

j>0 -> key 값이 제일 작아 처음에 삽입되어야 하는 조건입니다.


Line 15-16 :

데이터의 삽입을 위해 정렬된 구간의 데이터들을 뒤로 한칸씩 미룹니다. 또한 다음 탐색을 위해 j값을 감소시킵니다.


Line 18 :

한 회전을 통해서 삽입할 위치를 찾았으니 데이터를 삽입합니다.



시간 복잡도


삽입 정렬에서 최악의 경우는 버블 정렬과 마친 가지로 역순으로 정렬되어 있을 경우다.


즉, 매 회전마다 삽입되는 데이터가 정렬 구간의 처음에 삽입된다면,


1회전에 1번, 2회전 2번 ... n-1 회전에 n-1번 동작하기 때문에


1부터 n-1 까지 등차 수열의 합이므로 n에 대한 2차식이다. 따라서 시간복잡도는 이 됩니다.



 

저번 글에서 언급했듯이 이제부터 본격적으로 정렬 알고리즘에 대해서 알아보도록 하겠습니다.


이번 시간에는 기본적인 정렬 알고리즘 세 개 중 하나인 버블 정렬입니다.

(삽입과 선택은 다음 시간에 다루겠습니다!)


버블 정렬(Bubble Sort) - 안정 정렬


버블 정렬이란 인접한 두 원소를 계속 비교해 나가며 최종 정렬 값을 하나씩 완성해 나가는 방법입니다.


글로써는 이해하기가 어려울 수 있으니 그림으로 자세하게 설명드리도록 하겠습니다.







위 그림은 주어진 데이터를 오름 차순으로 버블 정렬하는 과정입니다.(데이터의 사이즈 n = 5)


정렬 과정은 데이터의 수 - 1 만큼 회전(반복)하며 큰 값을 결정해 나가는 것입니다.


다시 말해 1회전 - 첫 번째로 큰 값(7), 2회전 - 두 번째로 큰 값(5) ... 마지막으로  n-1 번째로 큰 값(2)을 결정하고 끝입니다.

(n번째 큰 값 1은 n-1번째로 큰 값이 정해지면 알아서 정해지므로 n-1번째 까지만 진행합니다.)


최종적으로 7 - 3 - 2 - 1 -5 의 데이터가 1 -2 - 3 - 5 - 7 로 정렬됨을 확인할 수 있습니다.



소스 코드


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
#include <iostream>
 
using namespace std;
 
void swap(int *a, int * b){
    int temp;
    temp = *a;
    *= *b;
    *= temp;
}
 
int main()
{
    int a[5= {7,3,2,1,5};
    bool endFlag;
    
    //정렬
    for(int i = 0 ; i < 4;i++){
        endFlag = true;
        for(int j=0; j <4-i;j++){
            if(a[j]>a[j+1]){
                swap(&a[j],&a[j+1]);
                endFlag = false;
            }
        }
        if(endFlag) break;
    }
    
    //출력
    for(int i = 0; i <=4; i++)
        cout << a[i] <<" ";
    return 0;
}
 
cs



코드 설명


배열 a : 정렬하고자 하는 데이터 입니다.


endFlag : 정렬 과정 중에서 데이터의 교환(swap)이 일어나지 않으면, 정렬된 상태이므로 이 때 탈출하기 위한 신호(Flag) 변수입니다.


Line 5 - 10 : 데이터의 위치를 바꾸는 함수 정의입니다.


Line 19 : 매 회전마다 교환 여부를 파악하기 위해 true로 초기화


Line 21 -24 : 인접한 데이터의 순서가 맞지 않으면 교환하고 endFlag를 false로 변경하여 탈출하지 않습니다.


Line 26 : endFlag 값을 보고 정렬 완성 상태를 파악한 후 반복문을 끝낼지 결정하는 부분입니다.



시간 복잡도


버블 정렬을 사용했을 때 최악의 경우는 정렬하고자 하는 방향의 반대로 구성된 데이터들을 정렬할 때 입니다.


다시 말해서 오름차순으로 정렬하고자 할 경우 내림차순으로 정렬된 데이터들을 오름차순으로 정렬하는 경우입니다.


이 경우에는 endFlag 인해서 중간에 break가 되지 않고, 끝까지 돌아갑니다.


입력 데이터의 크기가 n 일때 시간복잡도를 계산해보면,


1회전 : n-1번비교, 2회전 : n-2번 비교  n-1회전 : 1번 비교


이를 계산하면 n-1 부터 1까지 등차 수열의 합이므로 최고 차항은 n에 대한 2차식이 됩니다.


따라서 시간복잡도는 이 됩니다.











저번 포스팅에서 언급했듯이 정렬에 대해서 알아보도록 하겠습니다.


우선 정렬 알고리즘을 배우기 전에 정렬의 안정적 특성에 대해서 알아야 할 필요가 있습니다.


이 특성을 모르고 정렬 알고리즘을 선택한다면, 우리가 원하는 결과를 얻지 못할 수 있기 때문입니다.




정렬의 안정적 특성이란?


정렬의 안정적 특성이란 "정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되느냐" 입니다.


이러한 정렬의 안정적 특성에 따라서 정렬 알고리즘은 안정 정렬과 불안정 정렬로 구분 할 수 있습니다.


예를 들어, 아래와 같은 포커 카드에 대해서 번호를 키값으로 하여 오름차순으로 정렬하고자 합니다


이때, 우리는 약간 이상한 성향으로 인해(?) 같은 숫자카드의 무늬 순서를 유지시키고자 합니다.


즉, 아래 그림의 경우 정렬 후에도 하트4 뒤쪽에 스페이스4가 위치하게 하고 싶다는 의미입니다.


"당연히 유지되는게 정상 아니야?" 라고 생각 하실 수 있지만, 정렬 알고리즘에 따라서 정렬 후에 이 순서가 바뀔 수도 있습니다.



안정 정렬(Stable Sort) 


안정 정렬의 경우에는 정렬 후에도 원래의 순서가 유지되며, 결과는 다음과 같습니다.


정렬된 결과에서 하트4와 스페이스4의 순서가 그대로 유지되고 있음을 확인 할 수 있습니다.



불안정 정렬(Unstable Sort)


불안정 정렬의 경우에는 정렬 후에도 원래의 순서가 유지된다는 보장을 할 수 없으며, 결과는 다음과 같을 수 있습니다.


안정 정렬의 결과와는 달리 스페이스4와 하트4의 순서가 바뀐 모습을 확인 할 수 있습니다.

 




앞으로 배울 정렬 알고리즘에는 안정 정렬 알고리즘도 있고, 불안정 정렬 알고리즘도 있습니다.


따라서 이를 구분해서 학습을 해야 합니다. 너무 걱정하지는 마세요! 정렬 알고리즘을 설명할 때 같이 하도록 하겠습니다.


이번 포스팅은 여기까지며 다음 글부터 본격적으로 정렬 알고리즘에 대해서 알아보도록 하겠습니다!






알고리즘(Algorithm)?


우리는 컴퓨터로 많은 문제를 해결합니다.


여기서 문제를 해결한다는 의미는 우리가 아는 흔한 수학 문제일 수도 있고 실생활에 필요한 요구사항일 수도 있습니다.


하지만 컴퓨터는 사람처럼 똑똑하지 않아서 시키는 일만 수행합니다.


그렇기 때문에 컴퓨터로 사람이 요구 하는 문제를 해결하기 위해서는 그 문제에 대한 해결 방법을 함께 제시해줘야 합니다.


그것을 알고리즘이라고 부릅니다. 더불어 한 가지 문제에대한 여러 가지 해결 방법이 있을 수 있고,


이러한 상황 속에서 성능 분석을 통해서 가장 좋은 알고리즘을 선택해야 합니다.




공간 복잡도(Space Complexity)와 시간 복잡도(Time Complexity)


컴퓨터에게 명령을 내리는 알고리즘의 성능의 척도에는 공간 복잡도와 시간 복잡도가 있습니다.


공간 복잡도는 해당 알고리즘을 수행하는 데 있어서 필요한 메모리 양이며,


시간 복잡도는 해당 알고리즘을 수행하는 데 필요한 시간입니다.


그리고 이러한 복잡도를 우리는 세 가지 점근적 표기법을 활용해 나타냅니다.




점근적 표기법


점근적 표기법은 아래와 같이 세 가지로 표시하며 뜻은 다음과 같습니다.


점근적 상한을 나타내며, "아무리 심해야 이 정도다." 라는 의미입니다. (최악의 경우)


점근적 하한을 나타내며, "최소한 이 정도다" 라는 의미입니다.(최선의 경우)


점근적 하한을 나타내며, "대략 이 정도다" 라는 의미입니다.(평균적인 경우)


이러한 표기법들은 보통 문제 해결에 대한 입력 n에 대해서 표기합니다.


앞으로 다양한 알고리즘을 소개할 때, 보통 Oh 표기법을 많이 활용할 것 입니다.


왜냐하면 많은 시스템에서 성능을 보장하기 위해서는 최악의 경우를 고려하는 것이 올바르기 때문입니다.




이번 포스팅은 여기까지 진행하도록 하겠습니다!


추가적으로 설명이 필요한 부분이 있다면, 언급해주시고 계속 수정하도록 할게요


그리고 다음 포스팅에서는 의 시간 복잡도를 가지는 정렬 알고리즘에 대해서 알아보도록 하겠습니다.





+ Recent posts