'재미있는공부이야기/알고리듬' 카테고리의 글 목록

재미있는공부이야기/알고리듬

백준 17071번 숨바꼭질 5

투폭 2019. 3. 21. 22:16

2019. 3. 21. 22:16

이번 문제는 으딘가에서 나왔을법한 숨바꼭질 5입니다
수빈이가 이동할수있는곳을 다 찍어두고 
동생을 이동시키면서 시간의 최소값을 찾아보는 방식입니다.

특이점은 수빈이를 이동시킬때
oldTime[2][500000] 으로 맵을 만들고 (풀이에서는 500004로 정해놨음 )
홀수일때 짝수일대로 나눕니다. 그이유는
홀수는 홀수끼리 2씩 차이가나죠? 1 - 3 - 5 - 7 
근데 수빈이는 2턴을 지나게되면 제자리로 올수있는 기능이있습니다.
따라서 최소시간동안 동생이 지나갈곳에 도착을 하여서 대기를 하고있으면 동생은 알아서 찾아온다 이말입니다.
하지만 수빈이가 짝수시간에 도착을 한곳에 동생이 홀수시간에 도착을하면 절대로 만날수가없겠죠? (바로옆칸인데 못만나는 슬픔 ㅜ )
그래서 짝수시간에 도착했을때랑 홀수시간에 도착했을때 , 이두가지를 저장하기위하여 2줄짜리 배열을 만들어줍니다.

처음에 맵을 -1로 초기화시킨뒤에
초기 수빈이의 위치를 0 으로 놔줍니다. ( 초기 위치가 0이기때문에 맵자체를 0으로 해두면 오류나서 -1로함)
그리고 이제 이동하면서 -1인경우 숫자를채워줍니다 bfs기때문에 작은숫자부터 차근차근 잘들어가겠죠?
수빈이가 홀수타임때, 수빈이가 짝수타임때 위치에 시간을 저장해줍니다.

그리고 동생을 돌리면서 
동생의 현재 시간보다 작은값이 들어있으면 ( -1은 제외시킴)
그때 시간을 따로 저장해둡니다.
그리고 계속 찾아갑니다.뒤에 그 시간보다 짧은시간에 만난 친구가 있을수도있으니

그리고 마지막에 그 최소값을 출력해주면됩니다.
물론 처음 시간인 500004 에서 하나도 안바뀌었으면 만나지않는거니까 -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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#define _CRT_SECURE_NOWARNINGS
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
queue<pair<int, int>> myq;
int oldTime[2][500004] = { 0, };
int oldP, youngP;//형 +-1,x2  동생  +1 +2 +3 +4 +5
int qsize, youngT = 0;
int place = 0;
int minT = 500004;
bool isin(int a) {
    if (a < 0 || a>500000)return false;
    else return true;
}
void precheck(int old, int time) {
    if (isin(old - 1)) {
        if (oldTime[(time + 1) % 2][old - 1] < 0)//-1 부분 있냐
        {
            oldTime[(time + 1) % 2][old - 1] = time + 1;
            myq.push(make_pair(old - 1, time + 1));
        }
    }
    if (isin(old + 1)) {
        if (oldTime[(time + 1) % 2][old + 1] < 0 && isin(old + 1))//+1 부분 있냐
        {
            oldTime[(time + 1) % 2][old + 1] = time + 1;
            myq.push(make_pair(old + 1, time + 1));
        }
    }
    if (isin(old * 2)) {
        if (oldTime[(time + 1) % 2][old * 2] < 0 && isin(old * 2))//*2부분 있냐
        {
            oldTime[(time + 1) % 2][old * 2] = time + 1;
            myq.push(make_pair(old * 2, time + 1));
        }
    }
}
int main() {
    cin >> oldP >> youngP;
    for (int i = 0; i < 500004; i++) { // -1로 초기화
        oldTime[0][i] = -1;
        oldTime[1][i] = -1;
    }
    myq.push(make_pair(oldP, 0)); //처음값넣기
    oldTime[0][oldP] = 0; // 출발위치 0으로 초기화
    while (!myq.empty()) {
        qsize = myq.size();
        for (int i = 0; i < qsize; i++) {
            precheck(myq.front().first, myq.front().second);
            myq.pop();
        }
    }
    place = youngP;
    while (place <= 500000) { //동생돌리기
        if (oldTime[youngT % 2][place] > -1 && oldTime[youngT % 2][place] <= youngT) {
            minT = min(minT, youngT);
        }
        youngT++;
        place += youngT;
    }
    if (minT == 500004)cout << -1;
    else cout << minT;
    return 0;
}
Colored by Color Scripter
cs

'재미있는공부이야기 > 알고리듬' 카테고리의 다른 글

백준 9019번 DSLR (0)	2019.02.28
백준 14499번 주사위굴리기 (0)	2019.02.28
백준 7569번 토마토 (0)	2019.02.20
백준 2178번 미로찾기 (0)	2019.02.20
KMP 알고리즘 (0)	2019.02.15

백준 9019번 DSLR

투폭 2019. 2. 28. 23:33

2019. 2. 28. 23:33

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
84
85
86
87
88
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
queue<pair<int, string>> dongdong;
int ca, allsize;
int q, aw, start;
int checked[10000] = { 0, };
int temp;
int qsize;
void cal(int a, int b) {
    if (dongdong.front().first == aw) {
        cout << dongdong.front().second << endl;
        qsize = 0;
        queue < pair<int, string> >emptyq;
        swap(dongdong, emptyq);
        memset(checked, 0, sizeof(checked));
    }
    if (a != b) {
 
        if (a * 2 >= 10000) {
            start = a * 2 % 10000;
            if (checked[start] != 1) {
                dongdong.push(make_pair(start, dongdong.front().second + "D"));
                checked[start] = 1;
            }
        }
        else {
            start = a * 2;
            if (checked[start] != 1) {
                dongdong.push(make_pair(start, dongdong.front().second + "D"));
                checked[start] = 1;
            }
 
        }
        if (a == 0) {
            start = 9999;
            if (checked[start] != 1) {
                dongdong.push(make_pair(start, dongdong.front().second + "S"));
                checked[start] = 1;
            }
 
        }
        else {
            start = a - 1;
            if (checked[start] != 1) {
                dongdong.push(make_pair(start, dongdong.front().second + "S"));
                checked[start] = 1;
            }
        }
        start = a * 10 % 10000 + a / 1000;
        if (checked[start] != 1) {
            dongdong.push(make_pair(start, dongdong.front().second + "L"));
            checked[start] = 1;
        }
        start = a % 10 * 1000 + a / 10;
        if (checked[start] != 1) {
            dongdong.push(make_pair(start, dongdong.front().second + "R"));
            checked[start] = 1;
        }
    }
}
int main() {
    //freopen("test.txt", "r", stdin);
    cin >> ca;
 
 
    for (int k = 0; k < ca; k++) {
        cin >> q >> aw;
 
        dongdong.push(make_pair(q, ""));
 
        while (!dongdong.empty()) {
            qsize = dongdong.size();
 
            for (int i = 0; i < qsize; i++) {
                cal(dongdong.front().first, aw);
                if (!dongdong.empty())dongdong.pop();
            }
 
        }
    }
 
}
 
Colored by Color Scripter
cs

DSLR 다시풀어봐도 몇번 틀리고 ..

'재미있는공부이야기 > 알고리듬' 카테고리의 다른 글

백준 17071번 숨바꼭질 5 (0)	2019.03.21
백준 14499번 주사위굴리기 (0)	2019.02.28
백준 7569번 토마토 (0)	2019.02.20
백준 2178번 미로찾기 (0)	2019.02.20
KMP 알고리즘 (0)	2019.02.15

백준 14499번 주사위굴리기

투폭 2019. 2. 28. 23:32

2019. 2. 28. 23:32

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
 
int mapW, mapH, placeX, placeY, cnt;
int map[27][27] = { 0, };
int moveM[1004] = { 0, };
int dice[6] = { 0,0,0,0,0,0 };
int temp = 0;
bool isin(int a,int b) {
    if (a >= 0 && a < mapW&&b >= 0 && b < mapH)return true;
    else return false;
}
int roll(int a) {
    switch (a) {
    case 1:
        //cout << " 오른쪽"<<endl;
        temp = dice[1];
        dice[1] = dice[2];
        dice[2] = dice[3];
        dice[3] = dice[5];
        dice[5] = temp;
        cout << dice[5] << endl;
        break;
    case 2:
        //cout << "왼쪽" << endl;
 
        temp = dice[3];
        dice[3] = dice[2];
        dice[2] = dice[1];
        dice[1] = dice[5];
        dice[5] = temp;
 
        cout << dice[5] << endl;
        break;
    case 3:
        //cout << "위로"<<endl;
        temp = dice[0];
        dice[0] = dice[2];
        dice[2] = dice[4];
        dice[4] = dice[5];
        dice[5] = temp;
        cout << dice[5] << endl;
        break;
    case 4:
        //cout << "아래로"<<endl;
        temp = dice[5];
        dice[5] = dice[4];
        dice[4] = dice[2];
        dice[2] = dice[0];
        dice[0] = temp;
        cout << dice[5] << endl;
        break;
    }
    return 0;
}
void search(int k) {
    for (int i = 0; i < cnt; i++) {
        
        if (moveM[i] == 1 && isin(placeX, placeY+1)) {
            roll(1);
            if (map[placeX][placeY+1] == 0) map[placeX][placeY + 1] = dice[2];
            else {
                dice[2] = map[placeX][placeY + 1];
                map[placeX][placeY + 1] = 0;
            }
            //cout << "굴린다음에 아래에있는 숫자를 map[" << placeX << "][" << placeY << "]로 바꿈"<<endl;
            placeY++;
        }
        if (moveM[i] == 2 && isin(placeX, placeY-1)) {
            roll(2);
            if (map[placeX][placeY-1] == 0) map[placeX][placeY-1] = dice[2];
            else{ dice[2] = map[placeX][placeY-1];
            map[placeX][placeY - 1] = 0;
            }
            //cout << "굴린다음에 아래에있는 숫자를 map[" << placeX << "][" << placeY << "]로 바꿈"<<endl;
            placeY--;
        }
        if (moveM[i] == 3 && isin(placeX-1, placeY)) {
            roll(3);
            if (map[placeX-1][placeY] == 0) map[placeX-1][placeY] = dice[2];
            else{ dice[2] = map[placeX-1 ][placeY];
            map[placeX-1][placeY] = 0;
            }
            //cout << "굴린다음에 아래에있는 숫자를 map[" << placeX << "][" << placeY << "]로 바꿈"<<endl;
            placeX--;
        }
        if (moveM[i] == 4 && isin(placeX+1, placeY)) {
            roll(4);
            if (map[placeX+1][placeY] == 0) map[placeX+1][placeY] = dice[2];
            else {dice[2] = map[placeX+1][placeY];
            map[placeX+1][placeY ] = 0;
            }
            //cout << "굴린다음에 아래에있는 숫자를 map[" << placeX << "][" << placeY << "]로 바꿈"<<endl;
            placeX++;
        }
        //cout << "현재아랫면" << dice[2] << endl;
    }
}
int main() {
    //freopen("test.txt", "r", stdin);
    cin >> mapW >> mapH >> placeX >> placeY >> cnt;
    for (int i = 0; i < mapW; i++) {
        for (int j = 0; j < mapH; j++) {
            cin >> map[i][j];
 
        }
    }
    for (int i = 0; i < cnt; i++) {
        cin >> moveM[i];
    }
 
    search(0);
}
Colored by Color Scripter
cs

원시적인코드 dice[] 배열에 현재 좌우앞뒤위아래 상황을 다 저장한다

'재미있는공부이야기 > 알고리듬' 카테고리의 다른 글

백준 17071번 숨바꼭질 5 (0)	2019.03.21
백준 9019번 DSLR (0)	2019.02.28
백준 7569번 토마토 (0)	2019.02.20
백준 2178번 미로찾기 (0)	2019.02.20
KMP 알고리즘 (0)	2019.02.15

백준 7569번 토마토

투폭 2019. 2. 20. 23:22

2019. 2. 20. 23:22

아직 좌우앞뒤위아래 매커니즘이 뇌에 안박혀있어서 굉장히 원시적입니다.

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
84
85
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
 
using namespace std;
int box[104][104][104] = { 0, };
int x, y, z;
queue<pair<pair<int, int>, int>> myq;
 
bool isin(int a, int b, int c) {
    if (a >= 0 && b >= 0 && c >= 0 && a < x&&b < y&&c < z&&box[a][b][c] == 0)return true;
    else return false;
}
 
void bfs(int a, int b, int c) {
    if (isin(a - 1, b, c)) {
        box[a - 1][b][c] = 1;
        myq.push(make_pair(make_pair(a - 1, b), c));
    }
    if (isin(a + 1, b, c)) {
        box[a + 1][b][c] = 1;
        myq.push(make_pair(make_pair(a + 1, b), c));
    }
    if (isin(a, b - 1, c)) {
        box[a][b - 1][c] = 1;
        myq.push(make_pair(make_pair(a, b - 1), c));
    }
    if (isin(a, b + 1, c)) {
        box[a][b + 1][c] = 1;
        myq.push(make_pair(make_pair(a, b + 1), c));
    }
    if (isin(a, b, c - 1)) {
        box[a][b][c - 1] = 1;
        myq.push(make_pair(make_pair(a, b), c - 1));
    }
    if (isin(a, b, c + 1)) {
        box[a][b][c + 1] = 1;
        myq.push(make_pair(make_pair(a, b), c + 1));
    }
}
int main() {
    //freopen("test.txt", "r", stdin);
    cin >> x >> y >> z;
 
    for (int i = 0; i < z; i++) {
        for (int j = 0; j < y; j++) {
            for (int k = 0; k < x; k++) {
                cin >> box[k][j][i];
                if (box[k][j][i] == 1) {
                    myq.push(make_pair(make_pair(k, j), i));
                    
                }
 
            }
        }
    }
 
    
    int qsize, cnt = 0;
 
    while (!myq.empty()) {
 
        qsize = myq.size();
 
        for (int i = 0; i < qsize; i++) {
            bfs(myq.front().first.first, myq.front().first.second, myq.front().second);
            myq.pop();
        }
        if (myq.size() > 0)cnt++;
 
    }
    for (int i = 0; i < z; i++) {
        for (int j = 0; j < y; j++) {
            for (int k = 0; k < x; k++) {
                if (box[k][j][i] == 0) {
                    cout << "-1";
                    return 0;
                }
            }
        }
    }
    cout << cnt;
}
 
Colored by Color Scripter
cs

'재미있는공부이야기 > 알고리듬' 카테고리의 다른 글

백준 9019번 DSLR (0)	2019.02.28
백준 14499번 주사위굴리기 (0)	2019.02.28
백준 2178번 미로찾기 (0)	2019.02.20
KMP 알고리즘 (0)	2019.02.15
3장. 문자열 (0)	2019.02.13

백준 2178번 미로찾기

투폭 2019. 2. 20. 23:18

2019. 2. 20. 23:18

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

미로찾기입니다.

bfs를 사용해서 풀려고하였고

아직 탐색이 익숙하지않아서 좀 원시적으로 풀었습니다.

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
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
 
using namespace std;
 
int way[104][104] = { 0, };
int n, m;
int nowa, nowb;
queue<pair<int,int>> myq;
int cnt = 0;
bool isin(int a, int b) {
    if (a >= 0 && b >= 0 && a < m&&b < n&&way[a][b] == 1)return true;
    else return false;
}
void bfs(int a, int b) {
    nowa = a;
    nowb = b;
    way[a][b] = 0;
    if (isin(a - 1, b)) {
        way[a - 1][b] = 0;
        myq.push(make_pair(a - 1, b));
    }
    if (isin(a + 1, b)) {
        way[a + 1][b] = 0;
        myq.push(make_pair(a + 1, b));
    }
    if (isin(a, b - 1)) {
        way[a][b - 1] = 0;
        myq.push(make_pair(a , b-1));
    }
    if (isin(a, b + 1)) {
        way[a][b + 1] = 0;
        myq.push(make_pair(a, b+1));
    }
 
}
int main() {
//freopen("test.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &way[j][i]);
        }
    }
    myq.push(make_pair(0, 0));
    int qsize;
    while (!myq.empty()) {
        qsize = myq.size();
        for (int i = 0; i < qsize; i++) {
            bfs(myq.front().first,myq.front().second);
            myq.pop();
            if (nowb == n - 1 && nowa == m - 1) {
                cnt++;
                cout << cnt;
                return 0;
            }
        }
        cnt++;
        
        
    }
 
}
Colored by Color Scripter
cs

'재미있는공부이야기 > 알고리듬' 카테고리의 다른 글

백준 14499번 주사위굴리기 (0)	2019.02.28
백준 7569번 토마토 (0)	2019.02.20
KMP 알고리즘 (0)	2019.02.15
3장. 문자열 (0)	2019.02.13
2장. 정렬 (0)	2019.02.09

KMP 알고리즘

투폭 2019. 2. 15. 19:04

2019. 2. 15. 19:04

오늘은 KMP알고리즘에대해서 알아보자.

일단 KMP는 사람이름 앞글자를따왔다. 김현복, 민기찬, 박형욱

사실 Knuth–Morris–Pratt Algorithm 이다.

알고리즘때문에 머리만 싸매다보면 정신이 혼미해진다.

우선 저번 문자열에서 공부했듯이, 기본적인 문자열검색에서는 O(N*M) 시간을갖는데,

이 KMP알고리즘을 쓰면 O(K+N) 이라는 시간이된다.

50 50으로 본다면

기본적인건 2500 이지만 KMP를 쓰면 100으로 줄인다(실제론 100은아님, 아주쬐끔더큼)

일단 공부를하려고 다른블로그나 자료를 찾아보았지만 내 뇌 수준에 맞는 글이없었다.

그래서 오랜만에 친절한 설명을 곁들여 볼려고 한다.

ABC ABCDAB ABCDABCDABDE
ABCDABD

백준의 문제에서 따왔다. 어차피 다음글에서 풀어볼것이다.

지금부터 빨간 문자열은 무조건 긴문자열(문자열을찾게되는곳)으로 고정할것이고 파란문자열은 찾을 문자열로 고정할것이다.(보기쉽게)

위의 문자열에서 아래 문자열을 찾는문제인데, 잘보면 가운데 문자열이 ABCDAB 이다. 어 마지막 D만 일치안하네?

이걸 넣은이유가 무엇일까? KMP로 풀어서 처음에

긴문자열	A	B	C	D	A	B
찾을문자열	A	B	C	D	A	B	D

바로 저 D에 주목하라는것이다.

기본적인 문자열비교 알고리즘으로 간다면

다음비교는 분명

긴문자열	A	B	C	D	A	B
찾을문자열		A	B	C	A	B	D

이런식으로 갈것이다.

하지만 KMP를 이용해서

긴문자열의 가운데인 ABCDAB 를통째로 뛰어넘으라는 문제이다. ( 물론 앞에 ABC도 한번비교후에 뛰어넘음)

그럼 간단하게, 비교 시키위치 저장시킨다음에 만약틀리면 거기서부터 다시 이어서 비교하면 되는거아닌가? 라고 생각할수도있다.

이제 그거에 대해서 태클을 걸려고 다음문자열인 ABCDABCDABDE가 존재한다.

긴문자

찾는문자

첫비교가 이렇게 된다고 치자.

우리는 c 가 다르기때문에 다음 검색으로 넘어가야한다.

하지만 틀린위치를 저장하고 그다음부터 검색한다면

긴문자

찾는문자

이런식으로 검색을 시작할것이다.

우리가 원하는 건 노란색 테두리의 문자이고,

그건 이번검색전에 검색해야됐지만 , 검색할것을 훌쩍 뛰어넘어버리는것이다.

이것을 방지하기위해 우리는 P[ i ] 배열을 짜야한다. ~~다른곳에서는( Pi[ ] 배열로 설명을하는데 여긴내블로그니까 내맘대로하꾸여)~~

P[i]배열을 구하기위해서는 단계가 있는데

우선 접두사와 접미사를 알아야한다.

접두사와 접미사를 알아야하는 이유는 내가 어떤블로그에서 열심히 읽어도 이해하기가 힘들었으나

끝까지 이해하고나니까 알아야 하는 이유를 알게 되었다.

그러니 일단 따라가보자. 그럼 마지막에는 이유를 찾게 될것이다.

검색하려는 ABCDABD로 알아보자

접두사: A AB ABC ABCD ABCDA ABCDAB ABCDABD

접미사: D BD ABD DABD CDABD BCDABD ABCDABD

접두사는 for (int i=0 ;i<length;i++) 느낌이고

접미사는 for(int i=length;i>0;i--) 이런느낌이다. 등호 그런건 중요치않고 이런느낌이라고 느낌적인느낌.

접두사와 접미사가 뭔지는 중요하지않다. 아 접두사는 저렇게 보는거고 접미사는 저렇게 보는거구나 정도만 알면된다.

그럼이제 우리는 P [ i ] 로 돌아가보자.

P [ i ] 는 찾을 문자열의 부분배열과 관련되어있다.

ABCDABD의 부분배열의 갯수는 문자열의 길이와 같다.

아래에 부분배열들을 나타내본다.

ABC

ABCD

ABCDA

ABCDAB

ABCDABD

이렇게 7개가 된다.

이제여기서 접두사 = 접미사가 같은 것중에 가장 긴놈을 찾는다.

단, 자기자신은 제외해야된다. 위에서봤듯이 접두사(자기자신) = 접미사(자기자신) 가 무조건 성립하게되어버리니까 제외한다.

해보는게 빠르니 해보도록한다.

A => 접두사 A , 접미사 A (자기자신은 위에서 안된다고함) // 총 0개

AB => 접두사 A , 접미사 B (다름) // 총 0개

ABC => 접두사 A,접미사C (다름) 접두사AB 접미사BC (다름) // 총 0개

ABCD => 접두사 A,접미사D(다름) 접두사AB 접미사CD (다름) 접두사ABC 접미사BCD(다름) // 총 0 개

ABCDA => 접두사A 접미사A (같음!) 접두사AB 접미사DA (다름) 접두사ABC 접미사CDA(다름) 접두사ABCD 접미사BCDA(다름 ) //총 1개

ABCDAB => 접두사A 접미사B(다름) 접두사AB 접미사AB (같음!) 접두사ABC 접미사DAB(다름) 접두사ABCD 접미사CDAB(다름) 접두사ABCDA 접미사BCDAB(다름) // 총 1개

ABCDABD => 접두사A 접미사D(다름) 접두사AB 접미사BD(다름) 접두사ABC 접미사ABD(다름) 접두사ABCD 접미사DABD(다름) 접두사ABCDA 접미사CDABD(다름) 접두사ABCDAB 접미사BCDABD(다름) // 총 0개

다구했다. 물론 본인이 뒤에 개수를써놨지만 개수는 그리 중요하지않다.

밑줄친곳이 중요한데 접두사와 접미사가 일치하는것중의 최대 길이를 사용한다!.

첫번째 밑줄에서

접두사 A와 접미사A가 같으니 그 길이인 1을 출력한다.( AA라서 2가아니라 A로 같기때문에 1임)

두번째 밑줄에서

접두사 AB와 접미사 AB가 같으니 그 길이인 2를 출력한다. (마찬가지)

그러면 이제 ABCDABD의 P[ i ] 가 나왔는가? P [ 7 ] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 } 이 된다.

이해가 안간다면 아래 예제들을해본다.

ABAABAB => { 0 , 0 , 1 , 1 , 2 , 3 , 2 } P[2]의 요소가 왜 1인지 P[6]의 요소가 왜 2인지 머리속으로 그려보면, 아 A-A라서 한개 ㅋ AB-AB라서 2네 ㅋ 라는 게 확 와닿을것이다.

AABAA => { 0 , 1 , 0 , 1 , 2 }

AAAAA => { 0 , 1 , 2 , 3 , 4 } 부분문자열부터 생각해야된다는것을 생각하자. 처음부분문자열은 A하나라서 0일수밖에없다, 모든 P[i]의 0번째 원소는 0일수밖에없다 (자기자신포함안되므로) 그래서 잘따라가면 0 1 2 3 4 의 이유를 알 수 있다.

자 우리는 이제 P[ i ] 를 구했다.

이제 이걸 사용하면 끝.

우리가 풀려는 문자로 돌아가자.

[나만 돌아가면된다 ]

ABC ABCDAB ABCDABCDABDE
ABCDABD

이런 문자열이 있고 우린 빨간색에서 파란색을 찾을것이다.

그리고 우린 지금까지 P[i]를 구하는연습을했고 여기선

ABCDABD 에 대하여 P[7] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 } 라는 것 까지 알아냈다.

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧	A	B	C	D	A	B	D

검사를하자.

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧	A	B	C	D	A	B	D

~~아래부터 말투가 왔다갔다하니조심.~~

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧	A	B	C	D	A	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧	A	B	C	D	A	B	D

짠 D에서 다르다는걸 찾아냈습니다. D는 짧은것의 4번째 원소입니다. 그러니 저희는 P의 3번째 원소를 확인해줍니다.(3번째까지 맞았으니)

따라서 , P[2]을 확인합시다. ( i는 0부터 시작해서 0 1 2 , 2가 세번째에있는건 아시져?)

P[7] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 }

p[2]은 0이다. 따라서 접두와 접미가 같은게 없다는 말. 주의할게없다~ 바로 다음으로 넘어간다..

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧				A	B	C	D	A	B	D

Index 3에서 틀렸고 Index2까지 일치했습니다, p[2]의 값이 0 이었으므로 틀린곳(index 3)부터 이어서 시작해줍니다. (접두와 접미가 같은게 없으니 주의할필요가없음.)

계속 비교를해봅시다

P[7] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 }

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧				A	B	C	D	A	B	D

처음부터 달라버리네요 바로 다음으로 밀어줍니다

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧					A	B	C	D	A	B	D

계속 비교합시다

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧					A	B	C	D	A	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧					A	B	C	D	A	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧					A	B	C	D	A	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧					A	B	C	D	B	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧					A	B	C	D	A	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧					A	B	C	D	A	B	D

P[7] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 }

틀린부분이 나왔습니다 10번째에서.

위에글을 다 읽었으면 아시겠지만 여기는 도중에 접미가 같은 AB가 걸쳐있기때문에 뭔가 있다는걸 인지 하셔야합니다.

짧은문자열의 마지막 알파벳인 D에서 틀렸습니다 즉 7번째 알파벳.

그러니 저희는 그전까지 맞았던 6번째에 집중할필요가있습니다.

P의 6번째 원소인 P[5] = 2 입니다 .따라서 저희는 이녀석의 접두 접미에서 겹치는것중에 제일긴게 2다. "2칸을 조심해야한다" 라는걸 알수있습니다.

따라서 저희는 다음 비교를 index10에서 시작하는것이 아니라 2칸앞인 index8 부터 시작해줍니다 ( 2칸앞이라는걸 p[5] =2 로 알 수 있습니다)

앞에서말햇던 "그건 이번검색전에 검색해야됐지만 , 검색할것을 훌쩍 뛰어넘어버리는것이다." 라는게 P[i]로 인하여 해결되는 순간입니다.

그러면 다음단계는 아래와 같습니다.

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧									A	B	C	D	A	B	D

쭉검색을합시다

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧									A	B	C	D	A	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧									A	B	C	D	A	B	D

P[7] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 }

이제 쉽게 알수있다

3번째에서 틀렸으니까 2번째까지 맞은것이고 P의 두번째원소인 P[1] 을 보면 0 이기때문에 접두접미상관없다 그냥 다땡겨!

그럼 다음비교는 index10부터 시작하게된다.

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧											A	B	C	D	A	B	D

첨부터 다르다. 넘겨

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧												A	B	C	D	A	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧												A	B	C	D	A	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧												A	B	C	D	A	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧												A	B	C	D	A	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧												A	B	C	D	A	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧												A	B	C	D	A	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧												A	B	C	D	A	B	D

다른게 나왔다.

P[7] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 }

틀린건 ABCDABD에서 ABCDAB 즉 6번째까지 맞았기 때문에 P[5] 를 보면 2이므로 길이가 2짜리인 접두접미같은게 있다는것이다.

그래서 2칸을 방지하는겸 , index 17 로 넘어가지말고 2칸앞인 index15를 다음 비교점으로 잡는다.

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧																A	B	C	D	A	B	D

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧																A	B	C	D	A	B	D

귀찮으니 생략

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
긴	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
짧																A	B	C	D	A	B	D

P[7] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 }
오! 드디어 맞는 문자열이 나오게되었다. 이경우에는 7알파벳이 다맞으니 쉽게생각해서 P에서 마지막 원소인 0을 사용한다.

그렇게되면 방지할필요없이 그냥 바로 다음인 Index22부터 다시 검색을 시작하면된다.

스크롤양으로봐서는 굉장히 어렵고 복잡하다고 생각할수도있지만, 하다보면 재밌다.

접두접미를 이용해서 처음부터 방지를 해주니까 P 요소만 보고도 얼마나 뛰어넘을지 알수있으니 참편하다.

원리는 완전 깨달았으니 다음에 코드를 짜보도록 하자!

그나저나 말투 통일이 왜이렇게 안돼!!

'재미있는공부이야기 > 알고리듬' 카테고리의 다른 글

백준 7569번 토마토 (0)	2019.02.20
백준 2178번 미로찾기 (0)	2019.02.20
3장. 문자열 (0)	2019.02.13
2장. 정렬 (0)	2019.02.09
백준 2846번 오르막길 (0)	2019.02.09

3장. 문자열

투폭 2019. 2. 13. 20:58

2019. 2. 13. 20:58

문자열은 문자의 배열이기 때문에 수열과 비슷한 원리로 해결할수도있습니다 마찬가지로 문자열과 비슷한원리로 수열 문제를 해결할 수도있습니다.

문자열은 알고리즘문제에서 출제가 꽤 많이 됩니다. 프로그래머스에서 보는 알고 시험들이나 등등이거의 문자열문제가 많이 나오는 느낌입니다.

1. 문자열 탐색

show me the money 에서 mon을 찾으세요 하는 문제가나오면

show me the money자체에 "mon"이란 단어를 하나씩 비교하여

sho -> mon X

how -> mon X

ow -> mon X

이런식으로 비교할 수 있습니다. 물론 짧고 적절한 문자열에서는 이게 구현하는게 편하기때문에 이렇게 구현해도 괜찮다고 봅니다.

우선 mon이 하나밖에 없으면 재미없으니까 중간에 monkey를 끼도록 합니다.

show me the monkey money.

로 코드를 한번 구현해보았습니다,

위에서 설명한 가장 기본적인 문자열 탐색입니다. 물론 입력과 출력은 시험보는것 마냥.

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
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
using namespace std;
string sentence;
string word;
void searchword(string sen, string words) {
    int k = 0; // 탐색된 개수를 저장합니다. 여기서는 문장에포함된 mon개수입니다.
    for (int j = 0; j < sen.size(); j++) { //문장크기만큼 비교합니다.
 
        for (int i = 0; i < words.size(); i++) { //단어크기만큼 비교합니다.
 
            if (sen[j+i] == words[i]) {   //단어의시작점부터 비교대상을 함꼐 한글자씩 옆으로 움직입니다.
                if (i == words.size() - 1) {
                    k++;
                    break;
                }
                continue;
            }
            else break;
            
        }
    }
    cout << k;
}
int main() {
    getline(cin, sentence);
    getline(cin, word);
 
    searchword(sentence, word);
    
}
Colored by Color Scripter
cs

이렇게 풀어주었습니다. searchword 안의 sen[j+i]만 이해하면 끝날듯..

하지만 몇번나오는지가 아니라 존재하는지 알고싶다? 그러면 string 에서 제공하는 find 를 사용하면됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
using namespace std;
string sentence;
string word;
int k = 0;
int main() {
    getline(cin, sentence);
    getline(cin, word);
    
    k=sentence.find(word);
    k > 0 ? cout << "존재" : cout << "안존재";
}
Colored by Color Scripter
cs

find는 처음으로 탐색된 문자의 첫번째 자리를 반환합니다.

만약없다면 -1을 리턴하는걸 이용하여서

이런식으로 코드를 짜주었습니다.

find함수는 엄청유용합니다.

검색하는데 자주쓰이는데 아래와 같은 인자들이 쓰입니다.

find(const basic_string& str, size_type pos = 0) const;

str - 찾고자 하는 문자열

pos- 검색시작할 위치

find(const CharT* s, size_type pos, size_type count) const;

s- 찾고자 하는 문자열 포인터

pos- 검색시작할 위치

count - 찾고자하는 문자열 길이

근데 이 find가 string헤더에도있고 algorithm헤더에도 있다는사실.

배열에서 사용할때에는 인자로 배열의 시작점,끝점, 찾을값 을 넣어줘야하며 모두 주소값입니다. 물론 찾을값빼고

1
2
3
4
5
6
7
8
9
10
11
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
using namespace std;
int good[10] = { 10,9,8,7,6,5,4,3,2,1 };
int *answer;
int main() {
    answer = find(good, good+10,12);
    answer == good + 10 ? cout << "못찾음" : cout << "찾음";
    cout << endl;
}
Colored by Color Scripter
cs

숫자로 코드 예를 하나 들어보겠습니다. find마지막인자인 찾을값에 12가 들어갔으므로 못찾음으로 결과가 출력됩니다.

find는 결국 해당값을 찾으면 찾은위치 주소를 리턴하게되고, 못찾았으면 가장끝점의 위치를 리턴합니다.
그래서 find의 결과값을 가장끝점의위치인 good+10과 비교해서 같으면~ 못찾은거고, 다르면 찾은거고. 물론 리턴값으로는 그 주소값이 나옵니다.

어 ? 그러면 find쓰면서 주소값 적절히 빼주면서 카운트 세면면 갯수를 찾을수 있겟네? 라고 생각할수도 있지만 갯수를 세는 함수도 있습니다.

1
2
3
4
5
6
7
8
9
10
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
using namespace std;
int good[10] = { 10,9,8,7,6,5,4,3,3,13 };
int answer;
int main() {
    answer = count(good, good+10,3);
    cout << answer << endl;
}
Colored by Color Scripter

count 함수를 쓰게되면 인자로 똑같이 시작점, 끝점, 찾을것 을 넣게됩니다.
알고리즘헤더에서는 find_if 와 count_if 도 제공합니다.
둘다비슷하니 find_if만 설명하겠습니다.
find_if는 조건 검색입니다.
find는 특정한값을 찾는다고 생각하면 find_if는 말그대로 조건에 만족하는 값을 찾아줍니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;
int good[10] = { 10,9,8,7,6,5,4,3,3,13 };
int *answer = good;
bool jogun(int n) {
    return (n > 5);
}
int main() {
    while (answer != good + 10) {
        answer = find_if(answer, good + 10, jogun);
        cout << answer-good << endl;
        answer++;
    }
}
Colored by Color Scripter
cs
이렇게 한번 구현해 보았습니다. find_if 는 매개변수에서 값대신 함수 포인터를 넘겨줍니다. 이 함수는 매개변수로 해당 자료형을 받고
리턴형은 bool값이 됩니다. 저는 이름을 jogun(조건) 이라고 지었습니다. true가 리턴되면 조건에 맞다는 뜻입니다.
answer에 시작위치를넘겨주고 하나씩 증가시키면서 위치를 찾도록 시켜보았습니다.

이렇게 5보다 큰 숫자들의 위치가 출력됩니다.
카운트도 똑같이 쓰면 조건에 맞게 카운트를 할수 있습니다.

문자열검색으로 다시 돌아가봅니다.
show me the money 에서 mon을 찾으세요 하는 문제가나오면
show me the money자체에 "mon"이란 단어를 하나씩 비교하여
sho -> mon    X
 how -> mon    X
   ow -> mon    X 
이런식으로 검색할경우. 처음 s위치에서 mon만큼 h위치에서 mon만큼
빅오표기법으로할때 총 O(전체문자열 * 찾을문자열) 이 될것입니다.
하지만 KMP알고리즘을 사용하게되면 O(전체문자열+찾을문자열) 로 처리할 수 있습니다.

abckkkabcd
에서 abcd를 찾는다고 생각해봅시다.
원래방식대로라면 

abckkkabcd
abcd
abckkkabcd
 abcd
abckkkabcd
   abcd

이런 차례로 검색하게됩니다. 
아니 abck가나와서 다른거면
abck 순서 다넘기고 kkab부터 검색하면되는거아니냐? 에서 착안된것입니다.
다음 글에서 다루도록 하겠습니다. 

'재미있는공부이야기 > 알고리듬' 카테고리의 다른 글

백준 2178번 미로찾기 (0)	2019.02.20
KMP 알고리즘 (0)	2019.02.15
2장. 정렬 (0)	2019.02.09
백준 2846번 오르막길 (0)	2019.02.09
백준 2920번 음계 (0)	2019.02.07

2장. 정렬

투폭 2019. 2. 9. 16:38

2019. 2. 9. 16:38

배열을 쓰다보면 정렬을 빼놓을수없다.

애초에 배열이 오름차순 내림차순 정렬이 되어있어야 쓰기 편할뿐 아니라

탐색이나 다른 알고리즘을 최적화하는데 아주 중요하다.

거품 선택 삽입 힙 퀵 만 보도록 한다.

거품(bubble) 정렬.

뽀글뽀글이다. 1번2번 비교해서 정렬하고, 2번 3번비교해서 정렬하고.. ...쭈욱가다보면 마지막 원소만 원하는값으로 정렬이 되었을것이다. 만약 이 마지막 인덱스를 n이라고 치면

n-1번만에 된것. 그다음은 n-2번만에 될것이고 ...쭉가다보면 한번만에 정렬이 끝날것이다.

그렇게되면 정렬은 n(n-1) / 2 번만에 이루어질것이다.

이 정렬은 거의 모든상황에서 최악의 성능을 보여준다. 물론 이미 정렬된자료에서는 1번만 돌면되기때문에 최고의 성능을 보여주지만, 이미정렬된자료를 정렬한다고? 여기까지.

void Bubble_Sort(int len)
{
     for(int i=0; i<len; i++)
          for (int j = 0; j < len - i - 1; j++)
               if (a[j] > a[j+1])
               {
                    int t = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = t;
               }
}

Colored by Color Scripter

이경우 클수록 제일 큰 인덱스로 넣는 코드를 보여준다.

선택(selection) 정렬

하나하나 꼽아넣는 형태이다.

처음부터 끝까지 다 훑어서 제일작은걸 첫번쨰. 두번째부터 쭉 훑어서 제일작은걸 그다음. 이렇게 놓는방식인데

어떻게보면 버블이랑 비슷해 보일수도있다.

버블정렬보다 swap을 많이 안한다는게 장점이며, 평균적인 시간도 빠르다.

하지만 중복된 값들을 여러번 swap할 가능성이있어서 불안정하다고 한다.

void SelectionSort(int arr[], int len) {
    int i, j;
    int min, temp;
    for(i=0; i<len-1; i++) {
        min = i;
        for(j=i+1; j<len; j++) {
            if(arr[j] < arr[min]) min = j;
        }
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}
 

Colored by Color Scripter

이렇게 돌아가는구나..정도만 알면 될것같다.

애초에 정렬자체가 요즘엔 버블 선택이런것보다 인클루드해서 쉽게 정렬하는방법이 많으니..

삽입(insertion) 정렬

하나뽑아서 적절한위치에 넣고 나머지 자리를 당기는 방식이다.

6 8 5 7 4 9 3 2 1 이런식으로 되어있을때

6을 먼저뽑아서 그자리에 놓는다. 이미 정렬된게 없기때문.

다음 8 을뽑아서 8의 적절한자리인 6다음에 놓도록 한다. 그럼 6 8 그대로 된다.

그다음 5를 뽑아서 적절한위치를 찾기위해 8을 당기고 6을 당겨서 제일 앞자리로 위치할수있게한다. 그러면 5 6 8 7 4.... 이 된다. 이런식으로 진행한다.

평균적으로는 빠른편이긴한데(거품 선택 삽입 중에서) 위 예시처럼 작은수가 뒤에 몰려있으면 당겨야하는 수도 그만큼많아지기때문에 지옥..

힙(heap) 정렬

시간복잡도 O(N*logN)

힙 정렬은 힙을사용한건데

자료구조에서 힙이란 완전이진트리의 일종으로 우선순위큐를 위한것이다.

최대값 최소값을 쉽게 얻어낼수있는데

제일 root에 가장큰값이 있다면 최대힙, 가장작으면 최소힙이라고 한다.

최대힙기준

모든 원소를 힙에 삽입하고

루트에있는값은 최대값이므로 출력한후에 루트에서 제거한다.

삭제된 루트노드에는 그 힙의 마지막 노드를 넣는다. 그러고선 다시 힙을 완성시키고 루트값을 출력하고 제거하는 반복적인 일만 남았다.

코드로 짤경우 2세트 정도가 필요하다.

힙삽입, 루트제거

다음 문제로 알아보도록한다.

퀵(quick) 정렬

퀵정렬은 평균적인 상황에서 최고의 성능을 자랑한다.

피벗을정해서 양쪽을 기준으로 또 피벗정하고의 반복인데. 피벗이 계속 제일작은값이거나 제일큰값이면 시간복잡도 O(n^2)의 성능을 가지게되서 엄청구리다.

이를 보완하기위한 방법으로는 random quicksort나 전체수에서 임의의 3개나 9개값을 뽑아서 그들의 중간값으로 피벗을 정하는것.

최악의 경우를 막기위해서 생긴 방법이라고는 하나, 저렇게 해도 빠르다.

3 2 1 6 5 4 9 8 7

1.피벗을하나뽑는다. -> 제일왼쪽 3으로 하겠다.

2.피벗을제외한 2 1 6 5 4 9 8 7 을 봤을때 제일 왼쪽값을 left, 오른쪽값을 right로 하겠다. 지금은 left =2, right =7

3.순서는 반복적이다. 피벗과 left비교 -> 피벗과 right비교-> 자리바꿀지여부

4.피벗과 left를 비교하여 left가 더 크다면 right와 피벗을비교 or 피벗과 left를 비교하여 left가 더 작다면 left를 한칸 우측으로 이동시킨다.

5. 지금은 피벗인 3이 left인 2보다 더 크므로, left를 한칸 우측으로 이동시켜 1로 한다.

6. 현재 left = 1 , right = 7, 피벗 = 3

7. left가 피벗보다 작으므로 그대로 두고 right를 비교해본다.

8. right(7)보다 피벗(3)이 더작으므로, right를 한칸 좌측으로 이동시킨다. 그렇다면 right=8이 된다.

말은 복잡하지만( 필자가 잘 쓰질 못함..)

해보면 엄청 간단하다.

이렇게하게되면 피벗 (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
47
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
 
void swap(int arr[], int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
 
int cut(int arr[] , int cutstart, int cutend) {
    int pivot = arr[cutstart];
    int left = cutstart + 1;
    int right = cutend;
 
    while (left <= right) {
        while (pivot >= arr[left] && left <= cutend){
            left++; // left를 우측으로
        }
        while (pivot <= arr[right] && right >= cutstart +1){
            right--; // right를 좌측으로
        }
        if (left <= right){
            swap(arr, left, right); //left,right스왑
        }
    }
    swap(arr, cutstart, right); // 피벗과 high가 가리키는 대상을 교환 
    return right;
}
 
void quicksort(int arr[], int start, int end) {
    if (start <= end) {
        int pivot = cut(arr, start, end);
        quicksort(arr, start, pivot - 1);
        quicksort(arr, pivot + 1, end);
    }
}
int main() {
    int arr[9] = { 3,2,1,6,5,4,9,8,7 };
    cout << "3 2 1 6 5 4 9 8 7 을 정렬 합니다." << endl;;
    quicksort(arr, 0, 8);
 
    for (int i = 0; i < 9; i++) {
        cout << arr[i] << " ";
    }
    cout << " << 정렬 결과 " << endl;
}
Colored by Color Scripter
cs

이런식으로 구현했다. cut 이 자르기위해 피버를정해서 정렬하는 과정이고 quicksort에서는 이걸 재귀로하여 정렬하였다.

'재미있는공부이야기 > 알고리듬' 카테고리의 다른 글

KMP 알고리즘 (0)	2019.02.15
3장. 문자열 (0)	2019.02.13
백준 2846번 오르막길 (0)	2019.02.09
백준 2920번 음계 (0)	2019.02.07
1장. 배열 (0)	2019.02.07

백준 2846번 오르막길

투폭 2019. 2. 9. 14:26

2019. 2. 9. 14:26

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

문제

상근이는 자전거를 타고 등교한다. 자전거 길은 오르막길, 내리막길, 평지로 이루어져 있다. 상근이는 개강 첫 날 자전거를 타고 가면서 일정 거리마다 높이를 측정했다. 상근이는 가장 큰 오르막길의 크기를 구하려고 한다.

측정한 높이는 길이가 N인 수열로 나타낼 수 있다. 여기서 오르막길은 적어도 2개의 수로 이루어진 높이가 증가하는 부분 수열이다. 오르막길의 크기는 부분 수열의 첫 번째 숫자와 마지막 숫자의 차이이다.

예를 들어, 높이가 다음과 같은 길이 있다고 하자. 12 3 5 7 10 6 1 11. 이 길에는 2 개의 오르막길이 있다. 밑 줄로 표시된 부분 수열이 오르막길이다. 첫 번째 오르막길의 크기는 7이고, 두 번째 오르막길의 크기는 10이다. 높이가 12와 6인 곳은 오르막길에 속하지 않는다.

가장 큰 오르막길을 구하는 프로그램을 작성하시오.

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
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
 
int num = 0, bottom = 0,top = 0;
int maxgap = 0;
int numarr[1004] = { 0, };
 
int main() {
    //freopen("test.txt", "r", stdin);
    cin >> num;
    for (int i = 0; i < num; i++) {
        cin >> numarr[i];
    }
 
    bottom = numarr[0];
    for (int i = 0; i < num; i++) {
        //cout << "현재바텀 : " << bottom << endl;
        if (numarr[i] < numarr[i + 1]) {
            top = numarr[i + 1];
            //cout << "현재탑 : " << top << endl;
        }
        else {
            if (maxgap < top - bottom) {
                maxgap = top - bottom;
                //cout << "최대차이는 : " << maxgap << endl;
            }
            top = 0;
            bottom = numarr[i+1];
        }
    }
    cout << maxgap;
}
Colored by Color Scripter
cs

이렇게 풀어주었습니다.

첫번째 인덱스를 가지고 바텀에 넣어준뒤에

그뒤의 요소와 비교를해서 크면 바텀은유지, 탑은 그다음큰값으로 쭉쭉 나아가게해서

같거나 다른수가나왔을때는 가장큰 오르막 경사와 비교를하여(gap) 최대 gap을 지정해줍니다.

그리곤 이미 오르막이 끝났다는 경우니, 탑을 초기화 시키고 그 끝난 다음의 요소를 바텀으로 지정해줍니다.

증가수열판단이 적용되는 문제라 생각됩니다.

'재미있는공부이야기 > 알고리듬' 카테고리의 다른 글

KMP 알고리즘 (0)	2019.02.15
3장. 문자열 (0)	2019.02.13
2장. 정렬 (0)	2019.02.09
백준 2920번 음계 (0)	2019.02.07
1장. 배열 (0)	2019.02.07

백준 2920번 음계

투폭 2019. 2. 7. 17:13

2019. 2. 7. 17:13

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

문제

다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다.

1부터 8까지 차례대로 연주한다면 ascending, 8부터 1까지 차례대로 연주한다면 descending, 둘 다 아니라면 mixed 이다.

연주한 순서가 주어졌을 때, 이것이 ascending인지, descending인지, 아니면 mixed인지 판별하는 프로그램을 작성하시오.

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
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
 
int now = 0;
int umgye[8] = { 0, };
 
int main() {
    //freopen("test.txt", "r", stdin);
    for (int i = 0; i < 8; i++) {
        cin >> umgye[i];
    }
    for (int i = 0; i < 7; i++) {
        if (umgye[i + 1] == umgye[i] + 1)now = 1;
        else if (umgye[i + 1] == umgye[i] - 1)now = 2;
        else {
            now = 3;
            break;
        }
    }
    switch (now) {
    case 1: cout << "ascending";
        break;
    case 2: cout << "descending";
        break;
    case 3: cout << "mixed";
        break;
    }
}
Colored by Color Scripter
cs

이렇게 풀이했습니다.

현재상태를 now로 저장을해서 1인경우는 ascending 2인경우에는 descending 3인경우는 mixed로 출력하게했습니다

다음요소가 현재요소보다 1이 크다면 계속 1을 대입하고 1보다 작은순간은 2를 넣습니다.

이게 1씩증가하는 수만의 조합이라면 2차이가 날 수 없기 때문에 차이가 2가 나는순간 바로 mixed로 판별이되고 break로 구문을 빠져나오게 됩니다.

'재미있는공부이야기 > 알고리듬' 카테고리의 다른 글

KMP 알고리즘 (0)	2019.02.15
3장. 문자열 (0)	2019.02.13
2장. 정렬 (0)	2019.02.09
백준 2846번 오르막길 (0)	2019.02.09
1장. 배열 (0)	2019.02.07

PREV 이전 1 2 NEXT 다음

투폭네