9.14 문제 : 실험 데이터 복구하기(Python)

문제 출처 : algospot.com :: RESTORE

algospot.com :: RESTORE

---

1. 문제 분석

(1) 답의 구조 파악하기

1) 예제에서 답의 구조 확인하기

• 3번째 예제 입력에서 부분 문자열 조각 [ abrac, cadabra, dabr ]을 이용하여 만들 수 있는 문자열 중 가장 짧은 문자열은 cadabrac이다.
• 두 조각 abrac과 cadabra에서 abra가 일치하는 것을 알 수 있다.
• 부분 문자열 조각 dabr는 cadabra의 일부인 것을 알 수 있다.

 

2) 정리하기

• 어떤 문자열 조각에도 포함되지 않는 문자를 더할 일은 절대 없다.
• 연속해서 출현하는 문자열들의 접미사와 접두사를 최대한 많이 겹치게 해야 한다.
• 한 문자열 조각이 다른 문자열 조각에 포함될 경우 무시할 수 있다.
• 따라서, 조각들을 입력받자마자 문자열 중 다른 문자열에 포함된 것이 있는지 검사하고 다 지워버릴 수 있다.

 

(2) 모든 답을 만들어 보기(완전 탐색)

• 가장 좋은 방법은 먼저 문자열 조각들이 어떤 순서대로 출현할 지 정하는 것이다.
• 문자열 조각들이 특정 순서대로 출현한다고 가정하고 각 조각을 최대한 겹치게 연결한다.

 

• 1번째 예제 입력인 [ oji, oji, jing ]에 대해서 다음과 같이 탐색할 수 있다.
• [ 부분 문자열 조각의 순서 ] -> 순서에 따라 만들어질 수 있는 길이가 가장 짧은 문자열
• [ oji, jing, geo ] -> ojingeo
• [ oji, geo, jing ] -> ojigeojing
• [ geo, oji, jing ] -> geojing
• [ geo, jing, oji ] -> geojingoji
• [ jing, oji, geo ] -> jingojigeo
• [ jing, geo, oji ] -> jingeoji

 

• 이를 수학적으로 다음과 같이 표현할 수 있다.
• 단어 a 뒤에 단어 b가 등장할 때 최대 몇 글자를 겹칠 수 있는지 계산할 필요가 있다.
• 이를 계산하는 함수 overlap( )이 있다고 가정하면, k개의 문자열 조각 [ w0, w1, ..., wk-1 ] 에 대해 해당 순서대로 만들 수 있는 문자열의 길이는 다음과 같다.

 

overlap( )의 o가 0으로 보인다면 굉장히 눈이 좋은겁니다.

• '전체 문자열을 그냥 이어붙인 길이'에서 '중복이 발생하는 부분의 길이의 합'을 뺀다.

 

• 이 값을 최소화 하면 되는데 '전체 문자열을 그냥 이어붙인 길이'는 순서에 따라 상관 없다.
• 따라서, overlap( )의 합(중복이 발생하는 부분의 길이의 합)을 최대화 하는 순서를 찾아야 한다.

---

2. 점화식 유도

(1) 문제 정의

• 문자열 조각 k개의 순서를 정하는 경우의 수는 총 k! 개이다.
• 그러나 동적 계획법으로 구현하기 위해 다음과 같이 문제를 정의할 수 있다.

• restore(last, used) = 마지막에 출현한 조각 last, 지금까지 출현한 조각의 집합 used에 대해서, 나머지 조각을 추가해서 얻을 수 있는 overlap( )의 최대 합

(2) 점화식

• 문제 정의를 점화식으로 표현한다.

• restore(last, used) = max(overlap(last, next) + restore(next, used U {next} ))
• next는 used의 여집합의 원소

 

---

3. 최적해의 점수 계산

(1) overlap( ) 구현

• overlap( ) 함수는 재귀호출 시 마다 계산되어야 하므로 속도가 빨라야 한다.
• 그러나 overlap( )의 전체 계산은 k^2 번 진행되므로 사전에 미리 이를 구하고 저장하여 사용하면 더 빠르게 사용할 수 있다.
• ( 이중 반복문을 통해 i 번째 문자열 조각과 j 번째 조각에 대해 overlap( ) 함수를 실행하므로 시간 복잡도가 k^2임을 알 수 있다.)

1) overlap( ) 함수

# 두 문자열 a, b에 대해서 두 문자열이 얼마나 일치하는지를 반환
def overlapFunction(a, b):
    # a = "abcd", b = "cde"인 경우 i == 2 일때, a[2:] == b[:2] == "cd" 이므로 2를 반환한다.
    for i in range(min(len(a), len(b)), 0, -1):
        if a[len(a)-i:] == b[:i]:
            return i

2) 계산 결과를 사전에 저장

    # 입-출력 단계에서 사전에 진행되는 부분
    # 두 단어만 고려했을 때의 중복정도를 이차원 리스트 overlap에 사전 저장 
    for i in range(k):
        for j in range(k):
            overlap[i][j] = overlapFunction(words[i], words[j])

(2) restore(last, used) 구현

# 겹치는 부분 최대화 하기
# restore(last, used) : 마지막에 출현한 조각 last와 지금까지 출현한 조각의 집합 used가 주어질 때, 나머지 조각을 추가해서 얻을 수 있는 overlap()의 최대 합
def restore(last, used):
    # 기저 사례 : 모든 문자열 조각을 사용
    if used == (1<<k)-1:
        return 0

    # 메모이제이션
    if cache[last][used] != -1:
        return cache[last][used]

    cache[last][used] = 0

    for next in range(k):
        if (used & 1<<next) == 0:
            candid = overlap[last][next] + restore(next, used + (1<<next))

            cache[last][used] = max(cache[last][used], candid)

    return cache[last][used]

• cache를 2차원 리스트로 구현하는데 있어서 last는 단순히 문자열 조각 이므로 해당 문자열 조각의 인덱스를 사용할 수 있다.
• used는 문자열 조각의 사용 여부를 저장하는 집합으로서 이를 메모이제이션하기 위해 '9.11 예제(9.11 예제 : 여행하는 외판원 문제(Python)_정수 이외의 입력에 대한 메모이제이션 (tistory.com))'와 같이 비트 마스크 기법을 이용한다.
• 재귀 호출 과정을 통해 cache 테이블에 문제 분석 단계에서 기획한 것 처럼 overlap( )이 최대화 되는 값을 저장할 수 있다.

---

4. 실제 최소 길이 문자열 찾기

• restore( )함수는 각 최선의 선택의 결과를 별도로 기록해두지 않았기 때문에 다음에 다음에 나와야 할 문자열 조각이 무엇인지 직접 찾아야 한다.
• 다음에 나와야 할 문자열 조각은 used 집합에 포함되어 있지 않고, overlap( )함수의 값이 최대가 되는 것이다.
• 해당 과정에서 최적의 순서를 찾아가게 된다.

(1) reconstruct( ) 함수

# 실제 문제에서 요구하는 문자열 출력
def reconstruct(last, used):
    # 기저 사례 : 모든 문자열 조각을 사용
    if used == (1<<k)-1:
        return ""

    # 다음에 올 문자열 조각을 찾음
    for next in range(k):
        # next가 이미 사용되었다면 제외
        if used & (1<<next):
            continue

        # next를 사용했을 경우 답이 최적해와 같다면 next 사용
        ifUsed = restore(next, used + (1<<next)) + overlap[last][next]
        if restore(last, used) == ifUsed:
            return words[next][overlap[last][next]:] + reconstruct(next, used + (1<<next)) # 이 부분이 이해하기가 어려움...

    return "!@#!@#ERROR!@#!@#"

• 아래의 부분은 정확하게 이해되지 않았기에 대략적으로 이해한 것을 바탕으로 서술합니다.
• 사용하지 않은 문자열 조각을 next라고 할 때, next를 사용했다고 가정하고 restore( )함수를 계산해 그 값을 ifUsed 변수에 저장한다.
• ifUsed의 값이 restore(last, used)와 같다면, 중복되는 부분이 많아 overlap( )의 값을 최대화 할 수 있다는 의미이므로 next와 last의 중복되지 않는 부분을 문자열에 추가한다.
• reconstruct( )함수에 next를 인수로 하고 next를 사용한 것으로 하여 재귀호출한다.
• 모든 문자열 조각에 대해 재귀호출을 진행해 최종적으로 최소 길이 문자열을 반환한다.

(2) 시간 복잡도

• 문자열 조각 하나를 연결할 때 마다 reconstruct( )함수에서 O(k)의 시간이 걸리는 반복문을 수행하며, reconstruct( )함수 내에서 restore( )함수가 다시 O(k) 시간이 걸리는 반복문을 수행하므로 전체 시간 복잡도는 O(k)가 된다?
• 재귀 호출시 발생하는 반복문에 대해서는 시간 복잡도 계산을 하지 않는것인지 아니면 시간 복잡도에 영향을 크게 미치지 않기 때문인지는 잘 모르겠습니다..

---

5. 문제 입-출력

for tc in range(int(input())):
    k = int(input())
    words = []
    for _ in range(k):
        words.append(input())
    
    overlap = [[0] * 15 for _ in range(15)] # 두 문자열이 얼마나 중복되는지 저장 -> overlapFunction()에서 사전에 계산 후 저장

    # cache[last][used] : 마지막 단어가 last고 사용하지 않은 단어가 used의 여잡합일 때, used의 여집합에 있는 단어들에 대한 중복도를 저장한다. -> restore() 에서 사용
    cache = [[-1] * int(1<<15) for _ in range(15)] # 후보가 되는 모든 문자열에 대해서 발생할 수 있는 최대 중복정도를 저장

    # 어떤 문자열이 다른 문자열의 완전한 부분 문자열인지 검사
    # 완전한 부분 문자열인 경우가 발생하면 무시해도 되기 때문에 이 과정이 필요함
    while True:
        check = False # True면 어떤 문자열이 다른 문자열의 완전한 부분 문자열임을 의미한다.

        for i in range(k):
            if not check:
                for j in range(k):
                    # 서로 다른 두 문자열에 대해서 어떤 문자열이 다른 문자열의 완전한 부분 문자열인 경우
                    if i != j and words[j] in words[i]:
                        words.pop(j) # 해당 문자열을 단어 목록에서 삭제
                        k -= 1 # 전체 단어의 수를 줄임
                        check = True

        # 만일 어떤 단어가 다른 단어의 완전한 부분 문자열인 경우 한 번더 검사를 진행
        # 완전히 검사가 끝났을 때 부분 문자열이 없을 경우에만 while 반복문 종료
        if not check:
            break

    # 두 단어만 고려했을 때의 중복정도를 이차원 리스트 overlap에 사전 저장 
    for i in range(k):
        for j in range(k):
            overlap[i][j] = overlapFunction(words[i], words[j])

    print(reconstruct(k, 0))

• 맨 마지막에 reconstruct(k, 0)을 출력하도록 작성했는데, 매개변수가 (마지막으로 사용한 단어, 현재 까지 사용한 단어의 집합)이라는 의미를 가지고 있는 것으로 생각하면 '현재 까지 사용한 단어의 집합'은 아직 아무 내용물도 없는 상태이기 때문에 '마지막으로 사용한 단어'는 역시 아무런 의미를 가지고 있지 않는 단어로 생각하고 이해하고 있습니다.

---

6. 후기

  상당히 구현이 복잡한 문제였다. 문제에 접근하는 과정은 난이도가 높은 문제들에 비해서 이해하기 쉬었는데 구현 난이도는 난이도:상 정도 되는 문제들하고 비슷하다고 생각된다. 구현 과정에서 restore( )까지는 이해가 되었는데 reconstrcut( )에서 이해가 잘 안되는 부분이 있다. 그리고 문제 입-출력 단계에서 다른 문자열 조각에 완전히 종속되는 문자열 조각이 있는지 검사하는 단계에서도 꼼꼼하게 과정을 살피지 않으면 이해하기 어려운 부분이 존재한다. 불린값을 사용하여 검사 여부를 확인하는 과정에서 사용법이 굉장히 생소했기에 이 부분은 기억해두고 다른 검사 방법에 활용할 수 있을 것 같다는 생각이 들었다.

  이 문제는 접근 방법이 그래도 어렵지는 않는 편이었지만, 다른 문제들에 대해서 구현이 복잡해도 그보다 더 어려운 것이 문제를 해결하기위해 분석하고 접근하는 방법을 고안하는 과정이다. 그래도 동적 계획법 문제를 계속 보다보면 나오게 되는 패턴이 있는데, 먼저 문제를 정의하고 이를 점화식으로 표현하는 방법이 많이 해보니까 이제는 눈에 들어오긴 한다. 근데 문제 정의부터 못 하겠는데 어떻게 하지??

---

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

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies