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

이번 문제는 으딘가에서 나왔을법한 숨바꼭질 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    bool next_permutation(int *a, int n) {
        int i = n - 1l
            while (i > 0 && a[i - 1] >= a[i]) i -= 1;
        if (i <= 0) return false; // 마지막 순열
        int j = n - 1;
        while (i<j) {
            swap(a[i], a[j]);
            i += 1; j -= 1;
        }
        return true;
    }
Colored by Color Scripter
cs

N개중에 일부를 선택해야하는경우.

재귀호출이나 비트마스크 사용하면 더쉬움

그래서 잘안씀

123더하기 9095번문제

1~N까지로 이루어진 순열

123

4123

겹치는수없음

크기는항상 N이 되어야하고 순서가 중요

N!

순열을 사전순으로했을때

첫순열 : 오름차순

마지막 ; 내림차순

예)

123

132

213

231

312

321

다음순열 -> 사전순으로했을때 사전순으로 다음에 오는 순열

C++ STL의 algorithm에는 이미 next_permutation 과 prev_permutation(이전순열) 이 존재함. 자바에없음 개꿀

다음순열 -> 순열의 마지막수에서 끝나는 가장 긴 감소수열 찾으면됨

크기가 n인 배열 a의 다음순열

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    bool next_permutation(int *a, int n) {
        int i = n - 1l
            while (i > 0 && a[i - 1] >= a[i]) i -= 1;
        if (i <= 0) return false; // 마지막 순열
        int j = n - 1;
        while (i<j) {
            swap(a[i], a[j]);
            i += 1; j -= 1;
        }
        return true;
    }
Colored by Color Scripter
cs

차이를최대로 10819 문제   안품

외판원순회2  10971 문제   품

로또         6603 문제   품

연산자 끼워넣기 14888문제 품

'재미있는공부이야기 > 혼자끄적' 카테고리의 다른 글

브루트포스 (0)	2019.02.26
수학 (0)	2019.02.26

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

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

모든 경우의수 다해보는거

ex) 비번 4자리면

0000 부터 9999까지

총 1만가지

시도해보는 경우의수가 중요

비번이 12자리이고

경우의수가 0이 12개있는거부터 9가 12개있는거까지 1조 가지 경우의수

1.문제의 가능한 경우의 수를 계산해본다 -> 손으로

2. 가능한 모든방법을 다 만들어본다. -> 빠짐없이해야됨. 그냥해보기, for문, 순열, 재귀, 비트마스크

3. 각각의 방법을 이용해서 답을 구해본다.

시간복잡도 O(경우의수 x 방법1개를 시도해보는데 걸리는시간복잡도)

걍 다해보기 -) 2309 일곱난쟁이

1476 날짜계산 ( 중국인의 나머지정리? 도 있긴한데 안중요)

14500 테트로미노

'재미있는공부이야기 > 혼자끄적' 카테고리의 다른 글

N중포문 순열사용하기 (0)	2019.02.28
수학 (0)	2019.02.26

수학

1. 나머지연산

정답을 구할때 너무크면 나머지로 출력하는문제많음.

최종에서하지말고

매번나머지해도됨

나머지연산은 덧셈곱셈에 닫혀있고, 뺄셈도있긴한데 다름

나누기연산은 안됨 (6/3)%3 이 그 예

10403문제

빼기예제 (6-5)%3 = 1

파이썬에서는 1나오는데

C++ 이나 java는 -2가 나옴

그래서 각자나머지한거에서 나누는수 한번 더 해주면 성립

페르마의소정리

(a/b) %c

= (a x b^(c-2) ) % c

(단 c는 소수, a 와 b는 서로소)

2. 최대공약수

정답이 분수형태일때 기약분수 나타낼때

GCD

int g = 1;

for(int i = 2; i<=min(a,b) ; i++){

if(a%i == 0 && b % i ==0 ) {

g = i ;

}

시간복잡도 O(N)

유클리드 호제법이 더좋음

GCD(a,b) = GCD(b,a%b)

재귀쓸때

int gcd(int a, int b){

if(b==0){

return a;

} else{

return gcd(b,a%b);

}

유클리드호제법 시간복잡도 O(log N)

안쓸대

int gcd(int a, int b) {

while(b!=0){

int r = a%b;

a =b;

b =r;

}

return a;

}

이것도 시간복잡도 O(log N)

GCD(a,b,c) = GCD(GCD(a,b),c)

최소공배수

3. 소수

약수가 1이랑 자기자신

1) 어떤수가 소수이닌지 판별

2보다크고 N보다작은것들로 나눠

2보다크고 N/2보다 작은것들로 나눠

2보다크고 루트N보다 작은것들로 나눠 O(루트N)

2) N보다 작거나 같은 소수 찾아내기( N까지수를 루트N으로 조지니까 O(N루트N)

에라토스테네스의 체

2~100까지는 2 3 5 7 로 인해서 다지워짐

int prime[100];

int pn = 0;

bool check[101] ;

int n = 100;

for(int i = 2; i<=n ; i ++){

if(check[i] == false){

prime[pn++]=i;

for(int jk =i*i; j<=n; j+=i){

check[j] = true;

}

이미검사한 영역에대해서 당겨서 검사하는거 중요

시간복잡도 O(Nlog(logN))

골드바흐의 추측

2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.

위문장에 3을 더하면

5보다 큰 모든 홀수는 세소수의 합으로 표현 가능하다

진짜 추측임 10의 18승 이하에서는 참인것이 증명됨

결국 에라토스 체에서 false로 그 배열 자리에 소수인놈 저장해놨으니

수가 크면 한쪽소수 정해놓고 p+q = N 이런식으로해서 p 정해보고

N-p가 false인지 체크해보면됨

'재미있는공부이야기 > 혼자끄적' 카테고리의 다른 글

N중포문 순열사용하기 (0)	2019.02.28
브루트포스 (0)	2019.02.26

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

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

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알고리즘에대해서 알아보자.

일단 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가 존재한다.

긴문자

A

B

C

D

A

B

C

D

A

B

D

E

찾는문자

A

B

C

D

A

B

D

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

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

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

긴문자

A

B

C

D

A

B

C

D

A

B

D

E

찾는문자

A

B

C

D

A

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

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

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

이것을 방지하기위해 우리는 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의 부분배열의 갯수는 문자열의 길이와 같다.

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

A

AB

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

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

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

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

투폭네