현대차 소프티어 8, 9번 바이러스 및 수퍼바이러스 문제 해설 코드 (파이썬)

 현대차 소프티어 바이러스, 수퍼바이러스 문제 해설 링크

 

소프티어에서 8번문제랑 9번문제는 각각 바이러스, 수퍼바이러스이다. 물론 소프티어에서 직접 번호를 붙인건 아니지만 번호가 있는게 더..뭐랄까 언급하기가 편해서 아래에서부터 그냥 세서 번호를 붙이고 있다. 아무튼 두 문제가 붙어있고 9번문제가 '수퍼'바이러스인데다가 난이도도 더 어려워서 일단 바이러스 문제부터 풀려고 했다. 결론적으로 말하자면, 바이러스 문제를 푼 코드를 그대로 수퍼바이러스 문제에 적용해봤는데 똑같이 잘 풀린다 (??...) 이유는 모르겠음. 일단 해설 갑니다

 

위 내용은 '수퍼바이러스' 문제 내용이고, '바이러스' 문제에서는 N의 범위가 10^6까지로 더 작고 또 바이러스가 0.1초마다 증식하는게 아니라 1초마다 증식하게 된다. 일단 문제를 보면 알겠지만 기초 계산은 간단하다.

답은 (처음 바이러스의 수 K * (증가율 P ^ 총 시간 N))이다.

가령 처음 바이러스의 수가 2마리에다가 매 1초마다 3배가 된다면, 4초 뒤에는 2 * (3 ^ 4) 가 간단한 답이 된다. 다만 이번 문제에서는 숫자가 엄청나게 크기때문에 두개의 계산스킬?이 필요하다. 첫번째는 파이썬의 계산범위를 넘어나지 않게 하는 방법을 찾아내야하고 두번째는 제곱 횟수가 너무 많기 때문에 그 횟수를 줄여서 시간을 줄이는 방법을 찾아내야 한다.

 

첫번째는 나머지의 성질을 잘 활용하면 된다. 곱셈이 분배법칙이 되듯 나머지도 분배법칙이 된다. 가령 (5*5)%3 = 25%3 = 1인데 이건 사실 ((5%3) * (5%3))%3 = (2 * 2)%3 = 4%3 = 1 으로 나머지값끼리 계산을 해도 같은 값이 나오게 된다. 이걸 활용하면 큰 수 계산이 나오더라도 먼저 1000000007로 나눠서 파이썬의 계산범위 내에서 계산을 할 수 있게 되고 오버플로를 방지할 수 있다.

 

두번째 문제는 분할 정복을 활용하면 해결할 수 있다. 몇만번 몇백만번 제곱을 하면 큰 수가 나오는것도 문제지만 그 횟수만큼 계산하는것 만으로도 엄청나게 많은 시간을 소요하게 된다. 하지만 제곱의 기본적인 성질을 활용하면 시간복잡도를 log2N으로 줄일 수 있다. 가령 2^7은 (2^3)^2 * 2와 같다. 2의 50제곱은 2의 25제곱의 제곱이고, 2의 25제곱은 2의 12제곱의 제곱이다. 이렇게 하면 계산을 반씩 줄일 수 있고 2의 50제곱을 계산할 때 50번이 아니라 대략 log2(50)회의 계산으로 답을 낼 수 있다. 

 

수퍼 바이러스 결과

바이러스 결과

수퍼바이러스 코드에서 내가 N*10을 한 부분도 있고 예제 전반에서 숫자 크기가 꽤 크게 차이날거라고 생각하는데 실행시간이나 메모리면에서 큰 차이가 없다. 이..이게 log의 위력? ㅋㅋㅋㅋㅋ  아무튼 이렇게..쉽게 잘 풀리게 된다. 

 

당연하게도, 바이러스문제가 더 쉬울거라고 생각을 했고 바이러스문제를 푼 다음 조금 수정을 해서 수퍼바이러스 문제를 푸는거라고 생각을 했다. 그래서 바이러스 문제를 먼저 풀었는데 솔직히 나는 처음에 파이썬 범위를 벗어나게되면 문자열로 일일히 변경해서 계산해야되는 줄 알고 엄청난 뻘짓을 했었다. 아무튼 그렇게 해도 안 되서 이게 뭐지? 싶어서 다른 방식으로 문제를 풀게 됐다. 그런데.. 너무 똑같은 방식으로 수퍼바이러스도 풀려버려서 음.. 조금 이게 뭐지 싶다 ㅋㅋㅋ. 왜냐면 내가 지금 위에 애기한것 처럼 이 문제의 핵심은 나머지 정리, 분할정복이다. 혹시 바이러스 문제는 둘중에 하나만 활용해도 되나 싶어서 조금씩 이렇게 ..변주를 줘서 제출을 해봤는데 안 풀린다... 뭘까?ㅋㅋㅋ 나중에 혹시라도 현대차에 입사하게 된다면, 가능하면 예제를 꼭 확인해보고싶다.