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


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


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);
    
}
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 << "안존재";
}
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;
}
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;
}


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++;
    }
}
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

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

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

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


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


거품(bubble) 정렬.

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

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

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

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


1
2
3
4
5
6
7
8
9
10
11
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;
               }
}
cs
이경우 클수록 제일 큰 인덱스로 넣는 코드를 보여준다.


선택(selection) 정렬

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
    }
}
 
cs

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

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


삽입(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;
}
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

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;
}
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

+ Recent posts

티스토리툴바