7.6 문제 : 팬미팅(Python)

문제 출처 : algospot.com :: FANMEETING

algospot.com :: FANMEETING

---

1. 문제 해결을 위한 사고 과정

(1) 무식하게 풀기

• 팬의 수 N, 멤버의 수 M이라할 때 팬미팅 과정을 하나하나 시뮬레이션하는 방법
• 대략 O(M(N-M)) = O(NM_M^2)의 시간을 필요로 함
• 그러나 N과 M이 최대 200,000인 경우를 생각하면 제한 시간 안에 해결하기 어려움

 

(2) 곱셈으로 변형하기

1) 대략적인 생각

• 팬과 멤버들을 길이가 N과 M인 정수 배열로 생각하면 가능하지 않을까?
• 팬과 멤버에 대해서 남자는 1, 여자는 0으로 바꿔서 표현
• 각 배열의 자리에 대한 곱의 값이 1이면 남성 팬과 남성 멤버가 악수를 하는 것으로 간주
• 반대로 0(남-여, 여-여)이면 포옹을 하는 것으로 간주
• 모두 0인 결과가 나오면 경우의 수를 누적할 수 있다!
• 또한, 자리 올림이 발생하지 않기 때문에 normalize() 생략 가능

 

2) 구체화

• 문제의 조건에서 팬의 수는 항상 멤버의 수보다 커야 한다.
• 만일 멤버의 수가 3명이고 팬의 수가 6명인 경우를 생각해보자
• 각 자리에 1과 0으로 성별 정보를 담은 멤버에 대한 길이 3인 배열 A와 팬의 대한 길이 6인 배열 B로 표현할 수 있다.
• 이를 카라츠바 알고리즘의 경우 처럼 곱셈으로 표현하면 Ci에 대해 다음과 같이 표현 가능하다.

• Ci는 A의 연속된 값(0, 1, 2)과 B의 i부터 A크기 만큼의 연속된 값을 역순으로(i, i-1, i-2) 곱한 형태를 띄게 된다.
• 그러나 문제를 해결하기 위해서는 A와 B는 같은 순서로 비교해야 한다.
• 이는 B의 순서를 뒤집어서 곱하면 Ci에 대해서 A와 B를 같은 순서로 곱한 값을 얻어 낼 수 있다.

• 이를 응용하여 코드를 구현하면 문제를 해결할 수 있다.

---

2. 카라츠바 알고리즘을 이용한 구현

(1) 코드 1 : 두 큰 수를 곱하는 O(n^2) 시간 알고리즘 변형

def multiply(a, b):
    # c = [0] * (len(a) + len(b) + 1)
    c = [0] * (len(a) + len(b) - 1)

    for i in range(len(a)):
        for j in range(len(b)):
            c[i+j] += a[i] * b[j]
            
    # normalize(c) 사용하지 않음!
    return c

• 기존 예제의 코드에서 자리 올림(normalize())을 사용하지 않는다.
• c[i+j]에 단순히 a[i]과 b[j]를 곱한 결과를 저장한다. (c[i+j]에 저장하는 이유는 이전 예제에서 확인)

 

(2) 코드 2 : 카라츠바 알고리즘

def addTo(a, b, k):
    # 자리수 맞추기
    newsize = max(len(a), len(b) + k)

    # 동일한 자리수가 되도록 0추가
    while (len(a) != newsize):
        a.append(0)

    while (len(b) != newsize):
        b.append(0)

    # b의 최소 자리수부터 부터 더함
    for i in range(k, newsize):
        a[i] = a[i] + b[i - k]
        
    # normalize(a) 사용 안함!
        
 def subFrom(a, b):
    for i in range(len(b)):
        a[i] -= b[i]
        
    # normalize(a) 사용 안함!
        
def karatsuba(a, b):
    an = len(a)
    bn = len(b)

    # a가 b보다 짧은 경우 교체
    if an < bn:
        return karatsuba(b, a)

    # 기저 사례 1 : a나 b가 빈 리스트인 경우
    if an == 0 or bn == 0:
        return []

    # 기저 사례 2 : a가 비교적 짧은 경우 O(n^2) 곱셈으로 변경
    if an <= 2:
        return multiply(a, b)

    half = an // 2

    a0 = a[:half]
    a1 = a[half:]
    b0 = b[:min(bn, half)]
    b1 = b[min(bn, half):]

    z0 = karatsuba(a0, b0)
    z2 = karatsuba(a1, b1)

    addTo(a0, a1, 0)
    addTo(b0, b1, 0)

    z1 = karatsuba(a0, b0)

    subFrom(z1, z0)
    subFrom(z1, z2)

    result = []
    addTo(result, z0, 0)
    addTo(result, z1, half)
    addTo(result, z2, 2*half)

    return result

 

(3) 코드 3 : 모두 포옹하는 경우의 수 구하기

def hug(members, fans):
    n = len(members)
    m = len(fans)

    a = [0] * n
    b = [0] * m
    
    for i in range(n):
        if members[i] == 'M':
            a[i] = 1

    for i in range(m):
        if fans[i] == 'M':
            b[m-1-i] = 1

    c = karatsuba(a, b)

    allHugs = 0
    for i in range(n-1, m):
        if c[i] == 0:
            allHugs += 1

    return allHugs

• Ci에 대해서 0이 나오는 횟수가 바로 정답이다.
• 팬에 대한 배열인 b에 대해서 b[m-i-1]부터 배열을 채워 나가면 순서를 뒤집는 형태가 된다.
• 따라서 결과적으로 A와 B는 같은 순서대로 값을 곱하고 그 결과를 확인할 수 있다.

---

3. 시간 복잡도 분석

시간 복잡도는 두 수의 곱셈에 의해 좌우되므로 카라츠바 알고리즘과 동일한 O(n^log3)이다.

---

4. 후기

  문제를 처음 접했을 때 풀이를 보기 전 까지는 감히 카라츠바의 알고리즘을 응용한다는 생각을 할 수가 없었다. 이 문제를 만든 사람이나 해결한 사람이나 정말 미친 사람이 아닐까 하는 생각이 들었다. 항상 문제를 보면서 느끼는 건데 문제 풀이는 이해가 되는데 어떻게 해결 방법을 생각할 수 있을까 하는 의구심이 생긴다. 아마 풀이를 보지 않는다면 나는 몇 년이 지나도록 풀지 못했을 것 같다.

  그래도 이번 문제를 통해 이전 예제에서 두루 뭉실하게 넘어갔던 곱셉 방식을 카라츠바 알고리즘으로 옮기는 과정의 일부분을 명쾌하게 이해할 수 있었다. 역시 단순히 읽고 넘어가기 보다는 손으로 공책에 따라 쓰면서 그 과정을 이해하면 보다 명확하게 머릿속에 들어온다. 사실 배열 하나를 뒤집는 이유를 이해하지 못해서 거의 한 시간동안 머리를 싸매고 고민했었다. 책에서는 내 기준으로 짧게 설명하고 넘어가는 부분이라 배열을 뒤집어야 하는 이유를 당장 이해하지 못 했었다. 그러나 차근차근 그 과정을 손으로 적어보고 Ci에 대한 값이 어떻게 들어가야 문제가 해결되는지를 생각해보니 곧장 이해할 수 있었다.

---

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

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies