인프런 커뮤니티 질문&답변

안녕하세요, 인프런 AI 인턴입니다. 우주사막님.

시간 복잡도 계산에 관하여 문의하셨군요.

코딩 테스트에서 시간 복잡도는 알고리즘이 문제를 해결하기 위해 얼마나 많은 연산을 수행하는지를 나타내는 척도입니다.

Big O 표기법은 알고리즘의 최악의 경우를 기준으로 연산 횟수의 증가 추세를 나타내며, n의 값이 커질 때 연산 횟수가 어느 정도로 증가하는지를 대략적으로 표현합니다.

일반적으로 코딩 테스트에서 1초당 대략 (10^8) 연산을 처리할 수 있다고 가정합니다. 따라서 제약 조건에 따라 n의 값을 대입했을 때의 연산 횟수가 (10^8)을 넘지 않아야 시간 내에 문제를 해결할 수 있습니다.

예를 들어, n이 (10^4)이고 알고리즘의 시간 복잡도가 (O(n^2))라면 실제 연산 횟수는 ( (10^4)^2 = 10^8 )이 됩니다. 이 경우 연산 횟수가 (10^8)에 근접하기 때문에 시간 제한에 걸리지 않을 가능성이 있지만, 여유가 없는 상황이라고 볼 수 있습니다.

알고리즘 문제에서 제약 조건은 보통 n의 최댓값을 나타내는데, 이를 통해 문제가 요구하는 알고리즘의 시간 복잡도를 추정할 수 있습니다. 즉, n의 최댓값을 시간 복잡도 표현식에 대입했을 때 (10^8)을 넘지 않아야 합니다.

중첩 반복문의 경우 외부 반복문과 내부 반복문의 각각의 반복 횟수를 곱한 것이 전체 연산 횟수가 되며, 이를 통해 시간 복잡도를 계산하시는 것이 맞습니다.

제약 조건에서 고려해야 하는 n은 문제에서 주어진 입력 크기나 조건 등에 따라 다양할 수 있으며, 문제마다 각각의 최적의 알고리즘이 존재하니 문제의 맥락을 잘 파악하셔야 합니다.

복잡도 계산이 어렵다면, 먼저 기초적인 알고리즘과 그에 대한 시간 복잡도를 정리하고 예제 문제를 통해 연습을 많이 하시길 권합니다. 그 과정에서 각 알고리즘의 조건과 연산 횟수에 대한 감을 잡을 수 있을 겁니다.

코딩 테스트를 준비하시는 과정에서 좀 더 자세한 도움이 필요하시면 언제든 문의해주세요. 화이팅입니다!

안녕하세요 우주사막님.

시간복잡도 개념이 처음 접하면 조금 생소하고 어려울 수 있어요!

제가 질문 주신 부분 답변을 드려볼게요.

twosum 문제에서 nums = [1,2,3,4,5,6,7,8,9,10, ... , 100] 이렇게 숫자가 있을 때, 두 숫자를 더해서 197이 되는 숫자를 찾는 문제라면 일일이 다 더해보는 방법으로 구현하려면

1+2

1+3

1+4

...

1+ 100

( 99 번 실행)

2+3

2+4

2+5

...

2+100

(98번 실행)

3+4

3+5

...

3+100

(97번 실행)

(96번 실행)

...

(5번 실행)

96+97

96+98

96+99

96+100

(4번 실행)

97 + 98

97 + 99

97 + 100 => 정답 찾음

(3번 실행) 할필요 없음 위에서 정답을 찾아서

(2번 실행)

(1번 실행)

이런식으로 실행이 될거에요.

물론 중간에 일찍 정답을 찾으면 실행횟수가 줄겠지만, 우리는 보수적으로 접근해서 총 몇번 실행될지를 예상해봐야돼요. 그래야 최악의 상황에서도 통과할 수 있는 프로그램을 작성할 수 있기 때문이죠!

그럼 최악의 경우라면 (이 상황에서는 두 수를 더해서 199를 찾는 경우) 총 몇번 연산을 실행 해야할까요

99 + 98 + 97 + ... 3 + 2 + 1 = 100 *99 / 2 가 나와요. (등차수열의 총 합을 구하는 방식)

즉. nums라는 리스트의 원소의 개수가 10개라면 총 10*9/2 번 실행해야 답을 구할 수 있을거고

원소의 개수가 100000개라면 총 100000*99999/2 번 실행해야 답을 구할 수 있을거에요.

즉 원소의 개수가 n개 일떄 실행횟수는 n(n-1)/2번 해야되고, 실행횟수가 늘어난다는건 프로그램의 실행시간이 늘어난다는 뜻이에요.

즉 코드를 몇번 실행하냐(연산을 몇번 진행하냐)에 따라서 시간이 늘어나기도 하고 줄어나기도 합니다.

그러면 우리가 작성한 프로그램이 어떤거에 의해서 실행시간이 좌지우지 되는지 알아야 대략적인 시간을 예상할 수 있겠죠.

nums의 원소의 값이 클 수록 시간이 늘어날까요? [1000, 45543, 3463, 432523, 3454523] 이렇게 큰 숫자가 적혀있어도, 연산의 횟수는 영향이 없어서 실행시간에는 영향을 미치지 않는다고 볼 수 있어요.

그럼 nums의 원소의 개수가 많아지면 많아질수록 실행시간이 늘어날까요? 네 맞죠.

원소의 개수가 n개라면 n(n-1)/2 = (n^2 -n)/2번 실행해야 답을 구할 수 있잖아요.

그럼 어떤 비율로 시간이 늘어날까요.

n의 크기가 커질수록 (n^2 -n)/2 에 비례해서 실행시간이 늘어날거에요.

그런데 이렇게 항상 수식이 복잡하면 사용하기가 어렵겠죠. 그리고 이렇게 계산한것도 사실은 상황에 따라서 많이 달라지기도 하고, 정확한 값도 아니에요. 그냥 추세를 볼 뿐이죠.

그래서 그냥 핵심적인 비율만 떼고, 다 버리는거에요.

(n^2 -n)/2 를 그냥 n^2의 비율이라고 퉁치는거죠. 그게 Big-O 의 개념이에요.

즉, 위에서 제시한 문제 twosum문제를 제가 제시한 방법으로 풀게되면 O(n^2)의 시간복잡도가 걸리게 돼요.

해당 방법을 코드로 구현해보면

for i in range(len(nums)):
    for j in range(i+1, len(nums)):
        if nums[i] = nums[j]:
            print("찾았다!")

이런식으로 구현이 될 거에요. 실제로 실행해보면 제가 위에서 일일이 나열한대로 최대 (n^2 -n)/2번 실행이 될거에요

그럼 다시 질문으로 돌아가볼게요.

어떤 문제를 딱 보고, 아 이건 이렇게 풀어야겠다 라고 생각이들었어요. 그방법을 썼을 때 실행횟수는 어떻게되는지 미리 계산할 수 있으면 정확한 시간은 아니더라도 오래걸릴지 아닐지 정도는 판단할 수 있겠죠.

twosum문제를 해결하기 위해 구현한 코드가 위와 같을 때, 원소의 개수 n = 100일때는 최대 시행횟수 대략 100*99/2번 실행된다고했는데, 너무 이렇게 계산하면 번거롭잖아요. 당연 정확도는 높겠지만, 모든 문제에 대해서 정확한 실행횟수는 구하기 쉽지 않아요. 그래서 그냥 우리가 아까 구한 O(n^2)라는 시간복잡도에다가 n=100을 넣어서 나온 값으로 얼마나 오래걸릴지를 판단하고자해요.

그러면 대략 100^2 = 10,000 의 실행횟수가 나오겠네요. 물론 정확하진 않지만, 감을 잡기에는 충분해요.

그러면 우리가 기준이 있어야 하잖아요.

코테에서는 실행횟수가 어느정도를 넘어서면 시간초과가 날까요?

시험장마다, 코딩테스트 채점 서버마다, 기준은 달라서 획일적으로 제가 말씀드리긴 쉽지 않아요.

하지만 위험수치? 정도는 제안을 드릴 수 있어요.

시간복잡도에 값을 넣어서 나온값이 10^8을 넘어서면 시간초과가 날 가능성이 꽤 있다, 정도의 가이드 라인을 드릴 수 있습니다.

그럼 다시 twosum문제로 가서 , nums의 원소의 개수 를 n이라고 할 때, 2<=n <10^5 라고 가정해보면

n은 10^5이라는 엄청 긴 경우도 있잖아요. 그러면 그 상황에서 우리가 코드를 O(n^2)로 구현하게 된다면 n^2에 n의 최대값을 넣어서 나온 값 10^10승이 되고 이건 10^8을 한참넘죠! 그러면 음.. 이방식으로 코드를 구현하면 시간초과가 날 가능성이 굉장히 높구나..! 라고 생각하시면 돼요.

혹시 이해가 가셨을까요!?

추가적으로 제가 도움드릴 게 있다면 질문 주세요~

화이팅!