6번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다.

---

● 문자열 알고리즘

§ 문자열 검색 알고리즘

- 문자열 S에서 어떤 문자열 패턴 P를 찾는 알고리즘

모든 문자열을 검사하는 방법이 있다.

시간복잡도. S의 모든 길이마다 P의 길이만큼 검사해야 하므로 O(|S|x|P|)

 

§ 라빈 카프 알고리즘

Hash를 이용하는 방법

문자열을 정수로 바꾸는 방법

문자열은 비교하는데 문자열의 길이만큼 시간이 걸리는 반면에 정수는 크고 작음을 비교하는데 걸리는 시간이 O(1)이다.

hash("문자열") -> 정수 h로 변환

같은 문자열이면 항상 같은 정수가 나온다.

보통 해쉬함수는 각 문자의 아스키 코드값을 구해서 더한다.

해쉬값을 구하긴 하는데 이전 해쉬값을 이용해서 다음 해쉬값을 구하는 방법 = 롤링 해쉬

hash("abc"_를 구하는 방법은 다음과 같다(256진법)

H1 = 97*256^2+98*256+99

hash("abc"):H1 -> hash("bcd"):H2  이렇게 변한다면

이전 해쉬값에서 앞자리 수를 빼고 256을 곱한뒤 마지막 문자의 아스키 코드값을 더하면 된다.

H2 = (H1 - 97*256^2)*256+100

☆ 라빈 카프를 구현할 때는 진법과 소수를 잘 정해서 비교가 최소로 일어나게 구현해야 한다.

시간복잡도는 

만든 해쉬함수에 따라

Best :  O(N+M) , Worst : O(N*M)

 

§ KMP

만든 사람 성이 Knuth, Morris, Prett라서 KMP

문자열이 반복되면 검사를 건너뛸 수 있다.

실패함수 fail

fail[i] = 문자열 P의 i까지의 부분 문자열에서 prefix==suffix가 될수 있는 부분 문자열 중에서 가장 긴 것의 길이

구하는 시간복잡도 O(|P|)

prefix : 시작이 가장 앞인 부분문자열

suffix : 끝이 가장 마지막인 부분문자열

 

△ 광고

문제 : 광고판의 크기는 L. 광고 문구의 길이는 M. 

광고 문구가 주어졌을 때 가능한 광고의 길이 중 가장 짧은 것 구하기

 

방법

문자열 전체 길이에서 마지막에서 실패함수의 값을 빼면 앞에서 부터 겹치는 문자열의 길이가 빠지게 된다.

답 : N-fail[N]

 

△ Cubeditor

문제 : 문자열 S가 주어졌을 때, 두 번 이상 등장하는 부분 문자열 중에서 가장 긴것의 길이를 구하는 문제

 

방법

모든 부분 문자열에 대하여 실패함수를 구하고 그중 가장 큰 값을 구하면 된다.

시간복잡도 : 실패함수 구하기 O(|S|) * 모든 부분 문자열 S = O(|S|^2)

 

§ Trie

KMP가 문자열 S에서 패턴 P를 찾는 것이라면

Trie는 문자열 N개 중에서 문자열 S를 찾는 것.

숫자 비교는 O(1)

문자열 비교는 최대 O(길이)

자동완성 기능은 prefix를 사용하는 것임. Trie는 Prefix Tree

Trie의 초기 상태는 루트만 있다.

시간복잡도는 O(|S|)

느려서 잘 쓰지 않는다는 단점이 있다. 왜냐하면 생각보다 비슷한 단어들이 많지 않기 때문이다.

 

△ 두 수 XOR

두 수를 XOR한 값이 가장 큰 것을 찾는 문제

이중 for문으로 구하는게 좋은데 i에 대하여 A[i]구하고 다시 j에 대하여 구하면... 시간초과 일어난다

 

● 그리디 알고리즘

결정해야 할 때, 그 순간에 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘

쉬운데 어렵다.

정답이 나올지 안나올지 모른다. 그 때 그 때는 최적일지도 모르지만, 최종적으로는 답이 최적이 아닐 수도 있다.

정답이 나온다면 왜 나오는지 증명을 해야한다.

 

△ 거스름돈 문제

지폐와 동전의 개수를 최소로 하는 문제

가장 큰 액면가를 가진 지폐나 동전부터 거슬러주자

이 문제는 이 방법으로 풀린다. 하지만 모든 문제가 다 그러리란 법은 없다. 안 그럴 수도 있다.

 

△ 회의실 배정

그리디는 기준을 하나 정하고 그 기준을 쭉 따라가면 된다.

기준 1. 일찍 시작하는 회의를 배정한다.

3개밖에 안됨. 반례 존재

기준 2. 최대한 짧은 회의를 먼저 배정

길이가 짧은 것들끼리 겹침. 지정을 못함

기준 3. 일찍 끝나는 회의를 먼저 배정

이러면 항상 최대가 된다.

언제 시작하는 지는 안 중요하다. 언제 시작하는지 알아도 언제 끝나는지는 모르니까

일찍 끝나면 언제 시작하는지는 안중요

 

△ ATM

문제 : 줄을 선 각 사람의 돈을 뽑는 데 걸리는 시간의 합의 최솟값

순서를 바꿀 수 있다. 이 합을 최소로 만들어라.

기다리는 사람이 짧은 순서부터 인출

맨 앞의 사람의 대기시간은 뒤의 모든 사람에게 더해지기 때문에 가장 앞에 가장 작은 수가 오는 것이 좋다.

그래서 오름차순으로 정렬하면 된다.

 

△ 행렬

브루트포스로 풀 수 있다.

0과 1중 하나

모든 연산을 사용한다와 사용하지 않는다로 나뉜다.

NxM행렬의 3x3 부분 행렬은 (N-2)x(M-2)개 있다.

시간복잡도는 2^((N-2)x(M-2))

N이 6보다 작았다면 브루트포스로 풀 수 있겠지만.... 이 문제는 무리

 

(0, 0)번째 칸은 한번 밖에 바꿀수 없다.

그 다음에 (0, 1)도 바꿀 수 있는 방법이 하나 밖에 없다.

연쇄적으로 점점 한번밖에 바꿀수 없는 칸이 나타난다.

칸의 정보를 이용해서 그 칸을 기준으로 바꿀지 말지를 결정할 수 있다.

 

△ 동전 뒤집기

각각의 칸을 바꿀 수 있는 방법은 모두 두가지다.

이 문제는 답이 절대 2보다 작아지진 않음

브루트포스 N, M≤20. 총 백만가지

바꿀 수 있는 방법을 유일하게 만든다음 가장 작아지게 만들어주면 됨.