Fanmeeting 문제 시간 초과 나네요...

  • Jaekwan
    Jaekwan

    안녕하세요. 알고리즘 해결 전략보면서 하나 하나 풀고 있는데
    막히는 부분이 있어서 질문 합니다.

    Fanmeeting 문제를 푸는데 풀이에 나온 카리츠바 방식으론 풀지 않았고,
    남자 여자를 바이너리 값으로 바꾸어 logical OR로 포옹을 하였는지 검사했습니다.

    아래 코드가 왜 시간 초과가 나는지 잘 모르겠습니다. 카리츠바랑 비슷할 것 같은데요..

    (물론 맘에 걸리는 부분은 2**(singer_num) 부분이 약간... )

    #!/usr/bin/env python

def convertToBin(vals):
    for i in xrange(len(vals)):
        if vals[i] == 'F':
            vals[i]='1'
        else:
            vals[i]='0'
    return
def solve(singer, fan):

    singer_num = len(singer)
    fan_num = len(fan)

    if singer_num > fan_num:
        return 0

    # convert them into binary
    convertToBin(singer)
    convertToBin(fan)

    singer_bin = int(''.join(singer),2)
    # this may take time a lost if num > 10000
    answer = 2**(singer_num) -1

    count = 0
    for i in xrange(fan_num - singer_num +1):
        temp = fan[i:i+singer_num]
        fan_bin = int(''.join(temp),2)

        temp_answer = singer_bin| fan_bin
        if temp_answer == answer:
            count +=1

    return count

testCount = eval(raw_input())

for test in xrange(1, testCount+1):

    singers = raw_input();
    fans = raw_input();

    print solve(list(singers), list(fans))


    10년 전
8개의 댓글이 있습니다.
  • 꿀호떡
    꿀호떡

    생각하신 대로 그 부분이 문제가 맞습니다.

    일반적으로 컴퓨터가 빠르게 처리할 수 있는 숫자의 범위는 매우 제한적입니다. 대부분의 경우 컴퓨터가 한 번에 처리할 수 있는 숫자의 범위는 2^64 정도이고, 그 이상의 큰 숫자끼리 덧셈/뺄셈/곱셈/나눗셈을 하려면 좀 더 복잡한 과정을 많이 거쳐야 합니다. 그리고 이 과정에 드는 시간은 숫자의 자리수(길이)에 비례하게 됩니다.

    이 문제의 경우 데이터의 크기가 100,000까지 늘어날 수 있으므로 2^100000 스케일의 숫자를 여러 번 계산하게 됩니다. Python에선 편하게 2**singer_num 한 줄로 보이지만, 실제로는 100,000에 비례하는 무거운 연산을 하게 됩니다. temp_answer, singer_bin, fan_bin 등등 다 마찬가지에요.

    그러니까 시간복잡도를 계산하실 때, 이 연산에 드는 부분또한 고려해서 생각하셔야 합니다. 이 경우엔 for i ... 루프가 N에 비례하고, 그 안에서의 연산 (fan_bin 계산, temp_answer 계산, temp_answer와 answer의 비교) 이 모두 또 N에 비례하니까 결과적으로 N의 제곱에 비례하는 알고리즘이 된 셈입니다. 그러니까 시간초과일 수밖에 없지요.


    10년 전 link
  • 꿀호떡
    꿀호떡

    100,000이 아니라 원 문제는 200,000이군요. 여튼... =3=3


    10년 전 link
  • Being
    Being

    꿀호떡님이 잘 설명해 주셨습니다. 우리가 시간 복잡도를 고려할 때, 사실은 어떤 계산 모델 위에서 생각하는 것입니다. 예를 들면, 임의의 덧셈, 곱셈, 나눗셈 등이 모두 O(1)의 연산이라고 가정하는 것이지요.

    물론 사실은 그렇지 않습니다. 오늘날 사용되는 많은 시스템에서 32비트나 64비트 값들은 O(1) 연산이라고 할 수 있겠지만, n비트짜리 값 두 개를 더하는 것은 O(N) 연산이라 보아야 합당하겠지요.


    10년 전 link
  • Jaekwan
    Jaekwan

    자세한 설명 감사합니다. 비교 연산까지 모두 N에 비례하는지는 정말 생각도 못했네요!

    저도 이 연산이 너무 오래 걸리지 않을까 걱정을 해서 한번 돌려봤어요

    결과는 

    >>> timeit.timeit('2**200000')
0.030827999114990234
>>> timeit.timeit('2**200000')
0.020811080932617188
>>> timeit.timeit('2**200000')
0.02303290367126465
>>> timeit.timeit('2**200000')
0.030150890350341797

    최대치인 200,000의 경우 <=0.03s정도가 걸리는데(i5 코어) 이것도 오래 걸린다고 봐야 하나요?


    10년 전 link
  • Being
    Being

    저 값을 사용해 계속해서 추가적인 연산을 하는 것이 문제가 되죠. 저 값 자체가 문제가 아니라요.


    10년 전 link
  • VOCList
    VOCList 
        for i in xrange(fan_num - singer_num +1):
        temp = fan[i:i+singer_num]
        fan_bin = int(''.join(temp),2)

        temp_answer = singer_bin| fan_bin
        if temp_answer == answer:
            count +=1

    위 코드는 O(N^2)의 복잡도를 가집니다.


    10년 전 link
  • Jaekwan
    Jaekwan

    좀 변형 시켜 보았습니다..

    시간이 걸리는 부분을 지워 버리고 순수 루프로 돌렸어요.

    N이 팬수 M이 아이돌 수라 하면, O(NM)이지만, 실제로 안되는 경우에 innerloop에서 빠져 나오기 때문에 좀 더 빠를것이라 예상하는데..

    다시 시간초과 나버리네요..

    def solve(singer, fan):

    singer_num = len(singer)
    fan_num = len(fan)

    if singer_num > fan_num:
        return 0

    count = 0
    for i in xrange(fan_num - singer_num +1):
        temp = fan[i:i+singer_num]

        canHug = True
        for j in xrange(singer_num):
            if temp[j] == 'M':
                if singer[j] == 'M':
                    canHug = False
                    break

        if canHug:
            count +=1

    return count

testCount = eval(raw_input())


    10년 전 link
  • 꿀호떡
    꿀호떡

    마찬가지입니다. 중간에 빠져나오니 좀 더 빠를 거라고 하셨지만, 보통 시간복잡도는 "좋은 경우"가 아니라 "최악의 경우"를 가정하고 구해야 합니다. 특히 이 문제처럼 최악의 경우를 만들기 쉬운 문제에서는 더더욱 그렇습니다. 예를 들어, 모든 팬과 모든 아이돌이 전부 여자라면 어떻게 될까요? 한 번도 break 되지 않을 테고, 꼼짝없이 O(NM) 전체를 수행하게 될 것입니다.


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.