앞으로 git을 활용하고 추후에 github를 사용하게 되면 마크다운 에디터를 이용하여 README를 작성하는 날을 위해 대표적인 마크다운 에디터인 Typora를 설치하고 사용해 보려고 한다.

이 포스팅은 https://steemit.com/kr/@yahweh87/typora-2-2 의 포스팅을 참고하여 작성했습니다.

 

1. 설치

설치 환경은 Linux 18.04

리눅스에서는 아래의 명령어를 통해서 설치가 가능하다.

# or run:
# sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys BA300B7755AFCFAE
:~$ wget -qO - https://typora.io/linux/public-key.asc | sudo apt-key add -

# add Typora's repository
:~$ sudo add-apt-repository 'deb https://typora.io/linux ./'
:~$ sudo apt-get update

# install typora
:~$ sudo apt-get install typora

 

2. 실행 

터미널에서 typora 라고 치면 아래와 같이 하얀색 창이 뜨게 된다.

typora 첫 실행 화면

3. typora 문법

1. 제목 정하기

타이포라에서는 '#'의 개수로 제목의 크기를 정할 수 있다. #(띄어쓰기)(제목) 을 쓰면 된다. 아래는 예시를 보여준다.

# 제목1
## 제목2
### 제목3
#### 제목4
##### 제목5
###### 제목6

 

실제 생성된 제목

 

2. 코드 펜스

코드 펜스는 마크다운 문법이 적용되지 않는 구간을 의미한다. 이 구간에서는 마크다운에 사용되는 여러 특수 문자들을 순수하게 특수 문자로써 사용할 수 있기 때문에, 소스 코드를 코드 펜스에 넣어서 보여줄 수 있다. 사용 방법은 특수문자 ` ( 물결표시가 있는 키 )를 세번 쓰고 엔터를 누르면 아래와 같이 코드 펜스가 생긴다.

그리고 ```를 치고 옆에 코드 펜스 안에 들어갈 프로그래밍 언어를 입력하면 해당 언어가 선택된다.

``` c를 하면  c언어가 선택된다.
c언어가 선택된 모습

3. 표 만들기

타이포라에서는 표만들기도 문법으로 제공한다. 특수문자 | 와 - 를 이용하면 된다. ( 엔터 키 위에 있는 특수문자 )

타이포라에 |1열|2열|3열| 을 입력하면 아래와 같은 표가 만들어 진다.

4. 인용구

특수문자 를 사용하면 인용구로 사용할 수 있다. > (하고싶은 말)

5. 수평선

특수문자 - 를 3개 사용해서 수평선을 만들 수 있다. ( --- )

6. 일반 링크

 마크다운 문법을 통해서 원하는 url의 링크를 걸 수 있다. 

사용법 : [이름](url)

위의 문법이 적용되어 아래와 같이 'Kwakcena의 블로그' 가 된다.

 

7. 참조 링크

참조 링크는 어떤 링크에 id를 부여하고 원하는 문자열에 id를 할당하여 그 문자열에 링크를 걸어주는 방법이다.

사용법 : [원하는 id]:(url)

 

실제 사용할때는 [문자열][링크id] 를 통해서 사용한다.

8. 텍스트 사용법 - 기울임체

기울임체를 사용하기 위해서는 특수문자 * 또는 _ 를 사용하면 된다.

9. 텍스트 사용법 - 굵은 글씨체

굵은 글씨체를 사용하기 위해서는 특수문자 ** 를 사용한다.

10. 텍스트 사용법 - 기울이면서 굵은 글씨체

기울이면서 굵은글씨체를 사용하는 방법은 특수문자 *** 또는 ___ 을 사용한다.

11. 텍스트 사용법 - 취소줄

취소줄을 사용하는 방법은 특수문자 ~~ 를 사용한다.

 

시간복잡도


< 동기 >


시간복잡도가 생긴 동기는 문제를 효율적으로 해결하기 위함이다. 즉, 똑같은 문제를 해결하는 두개의 알고리즘이 있다면, 같은 입력을 제공했을 때 어느 프로그램이 더 빠른지를 측정하여 효율정을 판단하는 것이다.


< 개념 >


프로그램을 돌려보지 않고도 대충 어느정도의 빠르기를 예측하는 것이 시간복잡도의 개념이다.

"프로그램이 대략적으로 몇개의 명령을 수행하는가?" 를 계산하기 위해서 시간복잡도를 계산한다.


< 예제 >

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
 
int main()
{
    int a;
    int b, c;
 
    scanf("%d %d"&b, &c);
 
    a = b + c;
    printf("%d\n", a);
    
    return 0;
}
cs

위와 같은 코드는 main문에 총 6줄의 명령이 존재한다. 

시간복잡도는 대략적인 수행 시간의 판단이므로 "대충 6개 정도의 명령 수행 시간이 걸리지 않을까?" 라고 판단할 수 있고 이를 O(6) 으로 표기한다.

컴퓨터는 엄청 빠르기 때문에 상수 번 명령의 수행은 O(6) 이든 O(100) 이든 모두 O(1)로 표기할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
 
int main()
{
    int n;
    int sum = 0;
 
    scanf("%d"&n);
    for (int i = 0; i < n; i++) {
        sum += i;
    }
    printf("%d\n", sum);
    
    return 0;
}
 
cs

위 코드는 n의 입력에 따라 for문의 반복 횟수가 달라진다. for문을 제외하고 상수개의 명령은 5개이므로 O(n+5)의 시간복잡도로 표기할 수 있다.

하지만 5에 비해서 n의 비중이 크기때문에 대략적으로 판단한다는 관점에 따르면 이는 O(n)의 시간복잡도로 표현이 가능하다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
 
int main()
{
    int n;
    int sum = 0;
 
    scanf("%d"&n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum += i * j;
        }
    }
 
    for (int i = 0; i < n; i++) {
        sum += i;
    }
 
    printf("%d\n", sum);
    
    return 0;
}
 
cs

이번에는 2중 for문과 for문이 존재한다. 둘 다 n의 입력에 따라서 명령 수행 개수가 달라지는 구조를 갖는다.

2중 for문의 경우 O(n^2) 으로 표현할 수 있고, for문의 경우 O(n) 으로 표현이 가능하여 전체적인 시간복잡도는 O(n^2 + n) 이지만 n^2의 비중이 n보다 크므로 대략적인 판단에 의해 이는 O(n^2)의 시간복잡도로 표현이 가능하다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
 
int main()
{
    int n;
    int sum = 0;
 
    scanf("%d"&n);
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            sum += i * j;
        }
    }
 
    printf("%d\n", sum);
    
    return 0;
}
 
cs

이번에는 i의 값에 따라 2중 for문의 내부 for문 명령 수행 개수가 달라지는 예제이다.

i = 0 --> j = 0 ~ n -1 (n개)

i = 1 --> j = 1 ~ n -1 (n-1개)

i = 2 --> j = 2 ~ n -1 (n-2개)

이와 같은 과정을 거치는 for문이므로 1 + ... + n 까지 더한 명령수를 갖는다. 이는 O(n(n+1)/2) 로 나타낼 수 있으며 영향력이 가장 큰것으로 판단해보면 시간복잡도는 O(n^2) 로 표현할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
 
int main()
{
    int n;
    int sum = 0;
 
    scanf("%d"&n);
    for (int i = 0; i < n; i++) {
        if (i*== n) {
            printf("%d\n", i);
            break;
        }
    }
 
    printf("%d\n", sum);
    
    return 0;
}
 
cs

이번에는 중간에 조건문이 추가된 for문의 시간복잡도를 판단해보자. 여기서 중요한 것은 우리가 시간복잡도를 판단할 때는 가장 최악의 경우를 가져가야 한다는 것이다. 사실상 반복문이 시간복잡도를 결정하므로 O(n)의 시간복잡도로 표현할 수 있다.


<정리>


위의 예제에서 보았듯이 우리는 입력 n이 몇번 곱해지는가를 통해 시간복잡도를 결정하는 것을 알 수 있다. 앞으로 알고리즘을 배우거나 판단할 때 해당 알고리즘이 얼마의 시간복잡도를 갖는지 생각하는 것이 중요하다.


※ 그렇다면 시간복잡도가 얼마인지는 알고 있는데, 실제 시간은 얼마나 걸리는가 ?

명령 수행 개수와 시간의 관계를 구체적으로 알고 싶을 수 있다. 하지만 이는 컴퓨터마다 사양이 다르므로 명령 수행 시간은 다를 수 있으니 너무 깊이 들어가지는 말자.


O(n)의 명령 수행 시간은 전체적으로 입력이 커지면서 수행시간도 커진다. 이는 일직선을 이루지 않고 약간 삐둘삐둘한 형태의 일직선을 갖는데, 컴퓨터가 우리의 프로그램만 실행시키는 것이 아니라 다른 프로세스도 같이 동작시키기 때문에 우리의 프로그램에 신경쓰지 못하는 시간이 조금씩 생길 수 있다. 반대로 더 많이 신경쓸때도 있기 때문에 일직선을 이루지 못하는 것이다.


가장 중요한 것은 시간복잡도가 O(n)인 알고리즘의 수행시간을 어림짐작하면 대략 1억번의 연산을 수행하면 1초가 걸린다는 것이다. 우리가 짠 알고리즘의 시간복잡도가 O(n)이고 제한시간이 1초라면 n은 1억개까지는 괜찮다는 것이다. 

만약 O(n^2) 이라면 n은 1만이 될 것이다. 즉, 문제에서 주어진 n 제한이 10만, 제한시간이 1초라면 O(n^2)이 걸리는 알고리즘은 시도해보지 않아도 된다고 판단할 수 있다. 


< 정렬의 시간복잡도 >


1. 선택정렬

선택정렬은 최소값을 한번 찾는데 O(n)의 시간이 걸리고 이 행위를 n번 해야 되므로 총 O(n^2)의 시간복잡도를 갖는다.


2. 삽입정렬

삽입정렬은 원소 하나를 삽입하는데 O(n)의 시간복잡도가 걸린다. (최악의 경우 맨 앞까지 가야되므로.) 이러한 삽입을 n번 해야되므로 총 O(n^2)의 시간복잡도를 갖는다.


3. 버블정렬

인접한 원소를 비교하여 큰 수를 뒤로 보낸다. 맨 뒤의 숫자를 확정짖는데에 O(n)의 시간복잡도를 가지고 n개의 숫자를 확정해야 되므로 총 O(n^2)의 시간복잡도를 갖는다. 


기본적인 정렬 방법은 모두 O(n^2)의 시간복잡도를 가지므로 취향에 맞는 정렬을 사용하면 된다. 그리고 이러한 정렬방법은 1초에 만개의 숫자까지 정렬할 수 있다. 그 이상의 정렬은 좀 더 빠른 정렬이 필요하다.

'알고리즘 공부' 카테고리의 다른 글

시간 복잡도  (0) 2019.03.06
기본 정렬 (선택 정렬, 삽입 정렬, 버블 정렬)  (0) 2019.03.06
완전 탐색에 대해 이해하기  (0) 2019.02.25

정렬의 개념

순서없이 배치된 어떤 숫자들을 '오름차순' 또는 '내림차순'으로 숫자를 나열하는 것을 말한다. 

오름차순 정렬은 갈수록 커지는 정렬을 의미하고 내림차순은 갈수록 작아지는 정렬을 의미한다.


정렬의 기본 3가지

선택 정렬, 삽입 정렬, 버블 정렬 이 세 가지가 가장 기본이 되는 정렬이다. 모두 숫자에 특정 기준을 적용하여 나열한다. 

앞으로 나올 정렬의 예제는 오름차순 정렬을 사용한다.


1. 선택 정렬 


가장 단순한 정렬 방법으로 오름차순 기준 최솟값을 앞으로 이동시키는 정렬이다.


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
#include <iostream>
using namespace std;
#define MAXLEN 10
 
int main()
{
    int arr[MAXLEN] = { 8 ,9 ,24 ,31 ,2 ,56 ,3 ,81 ,7 ,22 };
    int min = 0;
 
    printf("정렬  전 : ");
    for (int i = 0; i < MAXLEN; i++printf("%d ", arr[i]);
    printf("\n");
 
    for (int i = 0; i < MAXLEN; i++) {
        int index = i;
        for (int j = i + 1; j < MAXLEN; j++) {
            if (arr[j] < arr[index]) 
                index = j;
        }
 
        int temp;
        temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
 
        printf("정렬 %d번 : ", i + 1);
        for (int i = 0; i < MAXLEN; i++printf("%d ", arr[i]);
        printf("\n");
    }
    return 0;
}
cs


출력 결과


출력 결과를 보면 정렬을 1번 했을 때 최소값인 2와 가장 첫번째 인덱스의 값이 자리가 바뀌었고, 두번째 정렬에서는 첫번째 인덱스를 제외한 나머지 값들에서의 최소값인 3이 두번째 인덱스 자리의 값과 자리가 바뀌는것을 볼 수 있다. 이를 반복하여 마지막에 오름차순 정렬이 완성된다.


2. 삽입 정렬


원소를 차례대로 정렬된 배열에 삽입시키는 정렬이다. 가장 왼쪽에 기준이 되는 bar가 있다고 가정하자. 그 bar를 기준으로 왼쪽은 정렬이 된 배열, 오른쪽은 정렬되지 않은 배열을 뜻한다. bar의 오른쪽에 있는 값을 왼쪽에 있는 값과 비교하면서 오름차순 기준 자신보다 작으면 자리를 바꾸는 정렬이다.


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
#include <iostream>
using namespace std;
#define MAXLEN 10
 
int main()
{
    int arr[MAXLEN] = { 8 ,9 ,24 ,31 ,2 ,56 ,3 ,81 ,7 ,22 };
    int min = 0;
 
    printf("정렬  전 : ");
    for (int i = 0; i < MAXLEN; i++printf("%d ", arr[i]);
    printf("\n");
 
    for (int i = 0; i < MAXLEN; i++) {
        for (int j = i; j >= 1; j--) {
            if (arr[j] < arr[j-1]) {
                int temp;
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1= temp;
 
                for (int i = 0; i < MAXLEN; i++printf("%d ", arr[i]);
                printf("\n");
            }
            else break;
        }
    }
    return 0;
}
cs


출력 결과

삽입 정렬의 결과를 보면 0번 index부터 증가하면서 자신의 오른쪽 숫자와 비교를 한다.

오른쪽의 숫자가 자신보다 작으면 자리를 바꿔가며 왼쪽으로 한칸씩 이동하는게 보일 것이다. bar가 이동하는 기준은 왼쪽의 값들이 정렬되어 있을 때 움직이게 된다 출력 결과의 두번째 줄은 첫번째 줄에서 31과 2를 비교했을 때 2가 더 작아서 31과 2의 자리가 바뀌고, 세번째 줄은 두번째 줄의 24와 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
#include <iostream>
using namespace std;
#define MAXLEN 10
 
int main()
{
    int arr[MAXLEN] = { 8 ,9 ,24 ,31 ,2 ,56 ,3 ,81 ,7 ,22 };
    int min = 0;
 
    printf("정렬  전 : ");
    for (int i = 0; i < MAXLEN; i++printf("%d ", arr[i]);
    printf("\n");
 
 
    for (int i = MAXLEN; i >= 1; i--) {
        for (int j = 0; j < i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1= temp;
 
                for (int i = 0; i < MAXLEN; i++printf("%d ", arr[i]);
                printf("\n");
            }
        }
    }
    return 0;
}
cs


출력 결과

0과1, 1과2, 2와3, 3과4 ... 8과9 를 비교하여 index 9 에 가장 큰 수인 81이 온다.

그 다음에는 다시 0과1, 1과2, 2와3 ... 7과 8을 비교하여 그다음 큰 수인 56이 오게 된다. 이를 반복하여 오름차순 정렬이 완성되는 것이다.

'알고리즘 공부' 카테고리의 다른 글

시간 복잡도  (0) 2019.03.06
기본 정렬 (선택 정렬, 삽입 정렬, 버블 정렬)  (0) 2019.03.06
완전 탐색에 대해 이해하기  (0) 2019.02.25

+ Recent posts