알고리즘을 풀 때 항상 생각해봐야 하는 것 - 복잡도

안녕하세요 Dibrary입니다.

 

개발자라면 항상 습관적으로 알고리즘을 풀곤 하죠.

주로 파이썬이 '생각'을 구현하는데 편해서 많이들 사용하는데 생각보다 파이썬은 느린 언어죠.

따라서 알고리즘문제를 풀 때 반드시 조심해야 하는 것 2가지가 있습니다.

 

1. 시간복잡도

네 시간복잡도는 말 그대로 코드로 해답을 구하는데 '시간'이 얼마나 걸리느냐 입니다.

백준 알고리즘을 예로 들어보겠습니다.

이렇게 입력값의 범위가 주어지면 숫자가 얼마나 큰지 감이 오시나요? 아주 어마어마하죠.

문제는, 이렇게 큰 범위 값이 항상 주어지는 것은 아니지만, 전부가 주어질 수도 있다는 겁니다.

그렇기에 파이썬으로 해당 문제를 풀기 전에 시간을 먼저 구해보는 습관을 들이면 좋습니다.

위 코드는 임의로 제가 10의 100제곱만큼의 범위를 가진 리스트를 생성하는데 얼마나 시간이 걸리는지 보고자 만든 코드입니다.

출력은 1분이 넘도록 나오지 않을 정도로 시간이 오래 걸립니다. 

 

따라서 이렇게 주어진 값의 극한을 임의로 설정하고 시간을 계산 해 본 후에, 시간이 오래 걸린다면, 좀 더 효율적인 방법으로 코드를 작성할 수 없는지 생각해 보아야 합니다.

 

백준에서 만일 시간을 아무리 확인하고, 계산해도 조건에 맞출 수 없다면? 채점 현황을 한 번 살펴보시는걸 권합니다.

네 제한이 2초로 되어있는데, 제출한 파이썬 코드의 시간이? 2초가 넘네요. 즉, 언어마다 시간제한 기준이 조금 다를 수 있습니다. 이런 내용은 문제에 언급되어 있지 않을 수 있으니 이상하다 싶으면 확인 해 보는 것도 좋은 습관입니다.

 

 

2. 메모리 사용량

두 번째는 메모리 사용량입니다.

모든 백준 문제들은 이렇게 메모리 제한이 언급되어 있습니다.

위의 조건의 경우에는 그나마 좀 널럴한 편인겁니다.

이렇게 되면 말 그대로 생각을 반드시 하고 코드를 작성해야 합니다. 

메모리 사용량은 sys라이브러리를 사용해서 알 수 있습니다.

똑같은 숫자 범위의 값이 들어갑니다. arr은 단순히 list로 만든것이고, arr2는 generator로 만들었습니다.

메모리 크기 차이는 얼마나 될까요?

어마어마한 차이를 보입니다.

위 코드를 통해 알 수 있는 내용은, 만일 굉장히 큰 list를 for문으로 순회해야 한다면 list로 만들지 말고, generator로 만들어서 사용하시면 메모리 사용량을 줄일 수 있다는 것입니다.

물론 generator는 하나의 사례입니다. 반드시 이것만 방법이 되는 것은 아닙니다.

 

 

항상 알고리즘 문제를 풀 때, 시간과 메모리를 생각해 보면 10번 틀릴거 5번 이내로 줄일 수 있을 겁니다.

(아참. 누구나 아는 내용인데 굳이 왜 쓰냐구요? 아쉽게도... 비전공자였던 저는 이런 내용을 알지 못한 채로 알고리즘을 도전했었거든요.)