8.2 문제 : 와일드카드(Python)

문제 출처 : algospot.com :: WILDCARD

algospot.com :: WILDCARD

참고 자료 : [알고리즘2] 08.02 와일드 카드 문제 (WILDCARD) in 알고리즘 문제해결전략 (종만북) - YouTube

---

1. 문제 분석

• ? : 어떤 글자와도 대응
• * : 어떤 문자열에도 대응

 

• 여기서 문제를 해결하는데 *를 어떻게 처리하는지에 대한 어려움이 발생한다.
• *가 m번 발생하면 문자열을 m+1개의 조각으로 분해할 수 있다!
• ex. t*l?*o*r?ng*s -> [t*, l?*, o*, r?ng*, s] (4개의 * 패턴이 존재해 문자열을 5개로 분해)
• 파일명이 주어질 때, 몇 글자가 첫 번째 조각에 대응될지 찾아내기 위해 모든 경우의 수를 다 시도해본다.
• n개의 글자가 대응된다고 하면, 나머지 문자열이 나머지 조각에 대응되는지 여부를 재귀 호출로 파악

---

2. 완전 탐색으로 구현

• 와일드카드 w가 파일명 s에 대응되는지 반환하는 함수 설계하기
• w와 s를 앞에서부터 한 글자씩 대응해 나가며 *를 만나거나 둘 중 한 문자열이 끝날 때 반복을 멈춘다.

(1) 코드

def match(w, s):
    pos = 0

    # while이 끝나는 경우
    # 1. w[pos] != s[pos] : 무조건 대응 실패
    # 2. pos가 w의 끝에 도달 : 패턴에 *가 없는 경우
    # 3. pos가 s의 끝에 도달 : w에는 패턴이 남았지만 s는 끝남
    #                         w의 남은 패턴이 모두 *일때만 참, 나머지는 거짓 -> 4의 사례에서 재귀호출로 해결
    # 4. w[pos] == * : match(w', s')로 재귀호출 하여 하나라도 참이면 답은 참
    #                  w' : w의 pos+1 부터의 문자열
    #                  s' : s + skip 이후의 문자열 (skip은 0부터 증가하는 인덱스 변수)
    while(pos < len(w) and pos < len(s) and (w[pos] == "?" or w[pos] == s[pos])):
        pos += 1

    # 왜 while문이 종료되었는지 검사
    # 2의 사례 : w의 끝에서 종료하면 s역시 종료했는지 검사
    if pos == len(w):
        return pos == len(s) # True를 반환하면 대응 가능, False면 대응 불가능

    # 4의 사례 : *에 몇 글자를 대응해야 할지 재귀 호출로 확인
    if w[pos] == '*':
        skip = 0
        while (pos + skip <= len(s)):
            if match(w[pos+1:], s[pos+skip:]): # match(w', s')
                return True # 하나라도 참이면 두 문자열은 대응
            skip += 1

    return False # 이 외의 경우는 모두 대응되지 않는 것으로 간주

(2) 완전 탐색 알고리즘을 통한 구현 시 발생하는 문제점

• 시간이 너무 오래 걸릴 수 있다.
• ******a 와 aaaaaab의 경우 결과적으로 불일치하지만 완전 탐색은 어째꺼나 모두 검사한다.

---

3. 동적 계획법으로 구현

• 재귀 호출 과정에서 입력으로 주어질 수 있는 와일드 카드와 파일명에서 떼어진 접미사(위 코드에서 w[pos+1:]과 s[pos+skip:]에 해당)는 최대 101개밖에 없다.
• 왜 101개냐? 앞에서 0개의 문자를 지운 경우(접미사는 원 문자열 전체) 부터 해서 100개의 문자를 지운 경우(접미사는 빈 문자열)를 생각하면 와일드카드와 파일명의 접미사의 개수는 각각 101개가 된다.
• 만약, match()가 101 * 101 = 10201번 이상 호출되었다면 이는 비둘기집의 원리에 따라 어떤 부분 문제가 중복되어 계산된다는 것을 의미한다.
• 이를 통해 101*101 크기의 캐시에 계산 결과를 저장하는 메모이제이션 방식을 통해 문제를 해결할 수 있다.

 

• 비둘기집의 원리 : n+1개의 물건을 n개의 상자에 넣을 때, 적어도 한 상자에는 2개 이상의 물건이 들어있다는 원리

(1) 코드

# 메모이제이션을 통한 동적 계획법 알고리즘(cache 사용)
# w와 s의 인덱스를 가리키기 위한 매개변수 wi, si를 사용
# 패턴과 문자열의 길이가 모두 n인 경우 부분문제의 개수는 n^2
# 한 번 호출시 최대 n번의 재귀 호출
# 시간 복잡도 : O(n^3)
def matchMemoized(w, s, wi, si, cache):
    # 기존의 계산된 결과인 경우 그 결과값을 반환
    if cache[wi][si] != -1:
        return cache[wi][si]

    while(si < len(s) and wi < len(w) and (w[wi] == "?" or w[wi] == s[si])):
        wi += 1
        si += 1

    # while문이 왜 종료되었는지 검사
    if wi == len(w):
        if si == len(s):
            cache[wi][si] = 1
        else:
            cache[wi][si] = 0

        return cache[wi][si]

    if w[wi] == '*':
        skip = 0
        while (si + skip <= len(s)):
            if matchMemoized(w, s, wi+1, si+skip, cache):
                return 1

    return 0

(2) 코드 해설

• 문자열이 아닌 문자열의 시작 위치 인덱스를 인자로 넘기는 것에 유의해야 한다.
• 또한 True / False의 Bool 자료형이 아닌 이에 대응하는 1 / 0을 사용하고, 캐시는 맨 처음 -1로 초기화 해야 한다.(문제 입력 부분에서 처리)
• 이를 통해 매번 문자열 객체를 생성하는 수고를 덜 수 있다.
• 메모이제이션 기법이 추가된 것을 제외 하면 완전 탐색 알고리즘과 같다.

(3) 시간 복잡도 분석

• 와일드카드와 문자열의 길이가 모두 n이라고 할 때, 부분 문제의 개수는 n^2이다.
• 또한 재귀 호출 과정에서 한 함수 내에서 최대 n번의 재귀 호출이 발생한다.
• 이전 도입 단계에서 주먹구구식 시간 복잡도 분석 방법인 (부분 문제 수) * (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)에 대입해보면
• 대략적으로 O(n^3)의 시간 복잡도가 나타난다.

---

4. 시간 복잡도를 O(n^2)으로 바꾸기

• 재귀 호출 시 함수 내의 반복문을 없앨경우 O(n^2)의 시간 복잡도를 갖도록 변형할 수 있다.
• 반복문을 재귀 호출로 변경한다면 n^2 * 1의 형태가 되어 결과적으로 O(n^2)의 시간 복잡도를 갖는다.

(1) 코드

def matchMemoized2(w, s, wi, si, cache):
    if cache[wi][si] != -1:
        return cache[wi][si]

    # while 반복문으로 없애고 if를 통해 재귀 호출
    if (wi < len(w) and si < len(s) and (w[wi] == "?" or w[wi] == s[si])):
        cache[wi][si] = matchMemoized2(w, s, wi + 1, si + 1, cache)
        return cache[wi][si]

    if wi == len(w):
        if si == len(s):
            cache[wi][si] = 1
        else:
            cache[wi][si] = 0

        return cache[wi][si]
    
    if w[wi] == '*':
        if matchMemoized2(w, s, wi+1, si, cache) or (si < len(s) and matchMemoized2(w, s, wi, si+1, cache)):
            return 1

    return 0

(2) 해설

• 기존에는 반복문의 조건에 따라 인덱스를 증가시키며 함수 내에서 검사했다면 이 방법은 조건문을 만족하면 인자로 넘겨주는 인덱스를 증가시켜 다시 재귀 호출을 반복하게 된다.
• 재귀 호출 중간 조건문을 만족하지 못하고 와일드카드의 *를 만나게 되었다면, 다시 반복문이 아니라 조건문을 통해 두 개의 경우로 나누어 다시금 재귀 호출을 진행한다.

---

5. 문제 입-출력

for tc in range(int(input())):
    w = input() # 와일드카드

    n = int(input())
    matched = []

    for _ in range(n):
        s = input() # 파일명

        # -1 : 아직 답이 계산되지 않음
        # 1 : 해당 입력이 서로 대응됨(True)
        # 0 : 해당 입력이 서로 대응되지 않음(False)
        cache = [[-1] * (len(s) + 1) for _ in range(len(w) + 1)] # 문자열의 길이는 최대 100으로 조각으로 나누면 최대 101개로 나뉜다. (101 * 101)
        if matchMemoized2(w, s, 0, 0, cache) == 1:
            matched.append(s)

    matched.sort()
    for i in range(len(matched)):
        print(matched[i])

---

6. 후기

  이 책을 공부하면서 점점 느끼는 부분이 있다. 문제를 어떻게 설계하는지가 가장 어렵다는 점이다. 정말 설계에 비하면 완성된 코드를 이해하는 건 정말 어렵지도 않은 일이다. 보통의 코딩 테스트가 어떻게 이뤄지는지 잘 알지는 못하지만 만일 제한 시간이 1~2시간이라면 절대 통과는 불가능하지 않을까 하는 상상을 한다. 아마 설계하는데만 시간을 다 잡아먹고 말거 같다. 심지어 이 문제는 난이도가 중인점에 특히 주목하고 싶다. 체감상 난이도가 상인 7단원의 마지막 문제인 팬미팅 문제보다 어렵게 느껴졌다. 그래도 오늘도 아마 꾸역꾸역 이 책을 다 끝내고 나면 백준이나 프로그래머스에 있는 문제들이 비교적 쉽게 느껴지지 않을까 하는 상상을 하며 자기 위안을 해본다.

---

github : Algorithmic_Problem_Soving_Strategies/q1_0.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies