알고리즘 스터디 Week4

알고리즘 문재해결전략 리뷰

20. 문자열

문자열의 검색

짚더미(haystack) 문자열 $H$가 바늘(needle) 문자열 $N$을 부분 문자열로 가지는 부분 문자열 $N$의 $H$에서의 시작위치들을 찾아내는 것을 문자열의 검색 문제라고 한다.

가장 먼저 생각나는 방법은 $H$의 모든 위치에서 $N$을 비교하는 방법이다.

std::vector<int> NaiveSearch(const std::string& H, const std::string& N) {
	std::vector<int> found;
    for (int begin = 0; begin + N.size() <= H.size(); begin++) {
    	bool matched = true;
        for (int i = 0; i < N.size(); i++) {
        	if (H[begin + i] != N[i]) {
            	matched = false;
                break;
            }
        }
        if (mathced) {
        	found.push_back(begin);
        }
    }
    return found;
}

위의 방법은 $O(M * N)$의 시간복잡도를 가진다. std::string::find() 함수가 위의 방법으로 탐색한다고 하는데, https://stackoverflow.com/questions/8869605/c-stringfind-complexity 를 확인해도 맞는 것 같다. string 검색을 최적화하기 위해서는 뒤에 나올 내용으로 최적화를 하는게 좋을 것 같다.

이제 위의 검색방법보다 효율적인 알고리즘 하나를 소개하려고 한다. KMP 알고리즘인데, 위의 Naive한 방식에서 버려지는 부분을 활용해서 빨라졌다고 생각하면 왜 빨라졌는지 직관적으로 이해할 수 있다. 위의 Naive한 방식에서는 이전 $begin$ 위치의 비교에서 몇개의 문자를 비교했어도 $begin + 1$에서는 $N$의 0번째 위치부터 비교한다. 하지만 앞에서 비교한 정보를 활용해서 진행을 이어갈 수 있다면, 중복을 줄일 수 있을 것이다. 그리고 KMP 알고리즘은 확실하게 줄여준다.

아이디어는 "비교의 중복을 없애자"가 아이디어였을텐데, 이 알고리즘은 단계로 나누어 아이디어 진행과정을 이해하기 어렵고 이 방법이면 이렇게 되네?! 이런 식으로 느껴진다. 일단 이 알고리즘이 어떤 알고리즘인지, 왜 빠른지, 그리고 왜 답을 보장하는지를 설명해보려고 한다.

일단 알고리즘을 말로 요약하면, 어떤 $begin$에서 매칭에 성공한 $N$의 부분문자열이 다음 문자에서 매칭에 실패했을 때 그 부분문자열의 접미어가 $N$의 접두어와 같다면 내가 틀렸을 때 복구될 수 있는 위치는 그 접두어부터 비교를 이어나가는 것이다.

 

https://m.blog.naver.com/kks227/220917078260

 

방법에 대한 것들은 좋은 레퍼런스들이 많아 생략하고, 왜 탐색부분이 $O(N)$에 작동하는지에 집중하려 한다. (

 

Week3 문제 풀이

https://codeforces.com/problemset/problem/234/G

풀이 정리

- $N$번으로는 항상 풀 수 있다. 첫 팀에 한 명씩 $N$번으로 가능.

- 채워야하는 선수간의 승부의 총 개수는 ${{N(N-1)} \over 2}$이다.

- 1번의 방법은 한 반복에 $N-1$개의 승부를 채울 수 있다. 그렇다면 일단 한 반복당 최대의 승부 개수를 만드는 것이 이득이지 않을까? => $(N-K)K$가 승부의 개수이므로 최대일 때는 $K$가 $[ {N \over 2} ]$일 때이다.
- 그러면 일단, 절반($[ {N \over 2} ])으로 나누는 방법으로 생각을 진행해보자. Merge sort의 형태가 그려지는데 이걸로 가능할까?

- "오늘의 팀의 절반은 내일의 적이다" 풀이법으로 $log_2 N$이나 $log_2 N + 1$의 반복으로 해결할 수 있을 것 같다. 이게 최선의 답인지 어떻게 증명할까? (위 풀이법 이름은 내가 붙인 이름이다. 각 반복마다 같은 팀을 반으로 나누어서 다시 양 팀에 배정시킨다.)

-  느낌은 최선인데.. 귀류법? 귀납법? 일단 승부의 개수만으로 생각했을 때는 4~5번이 최소 횟수이긴 하다. 하지만 반복없이 매칭시킨다는 것은 불가능하다. 느낌이 두 팀으로 나누어 승부시켰을 때 그 다음 최소한의 중복으로 반복시키는 방법이고 풀이법 같다. 이 방법이 최선인 이유는 각 팀간의 선수들은 서로의 승부가 끝났기 때문에 최선이지 않을까 생각이 든다. 두 팀이 붙었으면, 이제 각 팀 선수들 간에 승부는 중복일 뿐이다. 그렇다면 각 반복에서 최선의 선택은 각 팀 내부에서 최대의 승부 횟수를 만드는 것이다. 하지만 증명이 안 된다.

- 이 문제를 다른 시각에서 보면 증명이 가능해진다.
 일단 팀의 이름을 왼쪽팀, 오른쪽팀라고 붙이자. 그러면 첫 번째 승부에 왼쪽 팀이였던 선수들은 L, 오른쪽 팀이였던 선수들은 R이라는 문자를 받는다. 그러면 8명의 선수들이 있다고하고 3명, 5명으로 나눴을 때, $[L, L, L, R, R, R, R, R]$이라고 할 수 있다. 또 1, 3, 5, 6 선수를 골라 왼쪽 팀에 배정하면, $[LL, LR, LL, RR, RL, RL, RR, RR]$로 표현할 수 있다.

 그리고 여기서 우리는 서로 상대하지 않은 선수들이 있는가라는 질문을 할 때, 질문의 의미를 바꿔볼 수도 있다. 선수쌍에 대해, "서로 한 번도 상대하지 않았다"라는 의미는 "항상 같은 팀이였다"와 필요충분으로 같다. 그러면, 어떤 선수들이 같은 문자를 갖는다면 "항상 같은 팀이였다" => "서로 한 번도 상대하지 않았다"라는 의미로 해석할 수 있다. 그러면 위에서의 문자들로 표현했을 때, 같은 문자가 없다면 모든 선수들은 "모든 선수가 서로 한 번 이상 상대했다" => "서로 한번도 상대하지 않은 선수 쌍이 없다" 라고 할 수 있다. (대신에, 매번 모두가 훈련에 참여한다하고 문자열의 길이가 전부 같아야 한다. 예를 들어, 훈련에 참여하지 않은 선수들이 있어서 LL과 LLR이 있다면 이 둘은 서로 상대한게 아니다.)

 Left와 Right로 표현한 문자열들을 봤을 때 가장 먼저 생각나는 것이 있다. 바로 이진트리의 최하단 Leaf 노드들이 생각난다. 그러면 이제 최소 레벨에 Leaf 노드의 개수가 N개가 될 수 있는 방법을 생각해보는 거다. 이는 완전 이진트리(Complete Binary Tree)로 이어지면 최선의 답임이 자명하다. 이 아이디어로 문제를 풀 것이다. (생략한 것들이 있는데 모든 과정에서 필요충분조건으로 과정을 넘어오게 되고, 최소 경기횟수 = 문자열의 길이 = 이진트리의 레벨, 선수들의 경기이력 = Left와 Right팀으로 경기한 이력의 문자열임을 생각하면 마지막의 이진트리의 Leaf 노드 배정 중 최소 레벨을 구하는 문제와 같은 문제이다.)

 추가로 출력을 어떻게 하는지 아이디어가 필요하다. 일단 레벨을 정하고 이들을 0부터 N-1까지 그냥 숫자에 넣고 레벨별 비트 연산으로 0인 선수를 출력하면 된다. 최대 레벨이 5이라 하고 배정하면, LLLLL => 0, LLLLR =>1 ... RLRRL => 22 이다.

 코드포스 input, output에 파일 형식도 있는 줄 처음 알았다... 계속 제출에서 타임아웃 나길래 최대값으로 로컬에서 테스트해도 6ms 걸려서 이상하다 싶었다. 알고보니까 파일 입출력으로 풀었어야 했다.

#include <cstdio>
 
int main() {
    FILE *rfp = fopen("input.txt", "r");
    FILE *wfp = fopen("output.txt", "w");

    int n;

    fscanf(rfp, "%d", &n);
 
    int max_level = 0;
    while (n > (1 << max_level)) {
        max_level++;
    }
 
    fprintf(wfp, "%d\n", max_level);
    for (int i=max_level - 1; i >= 0; i--) {
        int left_num = 0;
        int mask = (1 << i);
        for (int j=0; j<n; j++) {
            if ((j & mask) == 0) {
                left_num++;
            }
        }
        fprintf(wfp, "%d", left_num);
        for (int j=0; j<n; j++) {
            if ((j & mask) == 0) {
                fprintf(wfp, " %d", j + 1);
            }
        }
        fprintf(wfp, "\n");
    }

    fclose(rfp);
    fclose(wfp);
    return 0;
}

https://algospot.com/judge/problem/read/ITES

Queue를 직접 구현하여 풀었다. 연속 숫자의 합이 $K$보다 클 때는 숫자를 더 더하는 것이 의미가 없으므로, queue에 넣었다가 빼면서 진행하면 된다.

#include <cstdio>
#include <cstdint>
#include <exception>

class InputGenerator {
public:
    InputGenerator() = default;
    ~InputGenerator() = default;
    
    int64_t GetInput() {
        const static int64_t kDivisor = (1LL << 32);
        if (input_ < 0) {
            input_ = 1983;
            return input_;
        }
        input_ = (input_ * 214013 + 2531011) % kDivisor;
        return input_ % 10000 + 1;
    }
    
private:
    int64_t input_ = -1;
};

template <typename T>
class MyQueue {
public:
    MyQueue() {
        array_ = new T[capacity_];
    }
    ~MyQueue() {
        delete array_;
    }

    void Reserve(size_t n) {
        if (n < size_) {
            throw std::exception();
        }
        ResizeAndMove(n);
    }

    void Push(T data) {
        if (size_ == capacity_) {
            ResizeAndMove(capacity_ * 2);
        }
        array_[(head_ + size_++) % capacity_] = data;
    }

    T Front() {
        if (size_ == 0) {
            throw std::exception();
        }
        return array_[head_];
    }

    void Pop() {
        if (size_ == 0) {
            throw std::exception();
        }
        size_--;
        head_ = (head_ + 1) % capacity_;
    }

    bool Empty() {
        return size_ == 0;
    }

private:
    void ResizeAndMove(size_t new_capacity) {
        if (new_capacity < size_) {
            size_ = new_capacity;
        }

        T *new_array = new T[new_capacity];
        for(int i=0; i<size_; i++) {
            new_array[i] = array_[(head_ + i) % capacity_];
        }
        head_ = 0;
        capacity_ = new_capacity;
        delete array_;
        array_ = new_array;
    }

    int capacity_ = 1;
    int size_ = 0;
    int head_ = 0;

    T *array_;
};

int main() {
    int c;
    scanf("%d", &c);

    while(c--) {
        int k, n;
        scanf("%d %d", &k, &n);

        InputGenerator gen;
        MyQueue<int64_t> queue;

        int64_t sum = 0;
        int result = 0;
        for (int i=0; i<n; i++) {
            int64_t input = gen.GetInput();
            sum += input;
            queue.Push(input);
            while (sum >= k && !queue.Empty()) {
                if (sum == k) {
                    result++;
                }
                sum -= queue.Front();
                queue.Pop();
            }
        }
        printf("%d\n", result);
    }
    return 0;
}

 

출처: 알고리즘 문제해결전략 2