백준5015 ls

작성일 | In

문제 링크

  • http://icpc.me/5015

문제 출처

  • 2011 NCPC E번

사용 알고리즘

  • DP

시간복잡도

  • O(N2)

풀이

완전 탐색

완전 탐색 코드를 먼저 짜봅시다.
함수 match(p, s)를 패턴 p와 문자열 s가 매칭 가능한지 판단하는 함수로 정의합시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool match(string &p, string &s){
  int idx = 0;
  //애스터리스크 나오기 전까지 p[idx]와 s[idx]를 매칭한다.
  while(idx < p.size() && idx < s.size() && p[idx] == s[idx]) idx++;
  //더 이상 매칭이 불가능하다면?

  //패턴의 끝까지 매칭이 되었다면 s도 끝까지 매칭이 되어야 한다.
  if(pos == p.size()) return pos == s.size();

  //애스터리스크를 만나서 종료된 경우에는 어디에 대응시킬지 결정
  if(p[idx] == '*'){
    for(int k=0; idx+k<=s.size(); k++){
      if(match(p.substr(idx+1), s.substr(idx+k))) return 1;
    }
  }

  //나머지는 false
  return 0;
}
중복되는 부분문제?

완전 탐색을 돌면서 중복으로 계산되는 문제가 존재하면 DP를 이용해 복잡도를 줄일 수 있습니다.
완전 탐색 코드를 보면 계속해서 앞 부분을 떼어내고 있습니다. suffix를 만들고 있죠.
p와 s는 각각 100글자이므로 suffix는 각각 101개 존재합니다.
match가 101 * 101번 이상 호출이 된다면, 비둘기집 원리에 의해 중복해서 계산하는 경우가 항상 존재합니다. 메모이제이션을 해봅시다.

O(N3) DP

위에서 작성한 완전 탐색 알고리즘을 약간 변형해 매모이제이션을 적용시켜봅시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int dp[111][111];
string p;

bool match(int i, int j, string &s){
  int &ret = dp[i][j];
  if(ret != -1) return ret;
  while(j < s.size() && i < p.size() && p[i] == s[j]){
    i++, j++;
  }
  if(i == p.size()) return ret = j == s.size();

  if(p[i] == '*'){
    for(int k=0; j+k<=s.size(); k++){
      if(match(i+1, j+k)) return ret = 1;
    }
  }
  return ret = 0;
}

N = |p|, M = |s|라고 한다면 상태공간은 O(NM)개이며, 각 상태 공간에 대해 해를 구하는데 O(M)이 소요됩니다.
N == M이라고 본다면 O(N3)

O(N2) DP

각 상태 공간에 대해 해를 구하는데 O(N)이 소요된 것은 재귀 함수 안에 루프가 있기 때문입니다.
루프르 없앨 수 있다면 O(N2)으로 복잡도를 줄일 수 있습니다.

1
2
3
while(j < s.size() && i < p.size() && p[i] == s[j]){
  i++, j++;
}

이 while문은 if(j < s.size() && i < p.size() && p[i] == s[j]) ret = match(i+1, j+1, s); 와 같이 바꿀 수 있습니다.

이제 애스터리스크를 처리할 때 사용되는 for문을 없애봅시다.
for문을 사용한 이유는 애스터리스크에 몇 글자를 대응시킬지 정하기 위해 사용했습니다.
그러나 그 작업은 현재 상태에서 한 글자를 더 대응시킬지, 그만 대응시킬지 두 가지의 케이스로 나눌 수 있습니다. 그러므로 아래와 같이 코드를 작성하면 됩니다.

1
2
3
if(p[i] == '*'){
  return ret = (match(i+1, j, s) || match(i, j+1, s));
}

전체 코드는 아래를 참고해주세요.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

string p;
int n;
vector<string> v;

int dp[111][111];

bool match(int i, int j, string &s){ //p idx, s idx, s
	int &ret = dp[i][j];
	if(ret != -1) return ret;
	if(i >= p.size()) return ret = (j == s.size());
	if(p[i] == s[j]) return ret = match(i+1, j+1, s);
	if(p[i] == '*'){
		return ret = (match(i+1, j, s) || match(i, j+1, s));
	}
	return ret = 0;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> p >> n; v.resize(n);
	for(int i=0; i<n; i++) cin >> v[i];

	for(int i=0; i<n; i++){
		memset(dp, -1, sizeof dp);
		if(match(0, 0, v[i])) cout << v[i] << "\n";
	}
}