[심화] 시간복잡도 Time Complexity

시간복잡도 활용법 in 코딩테스트

1. 시간복잡도 이해하고 외우기

2. 제한 조건 보는 법

3. 다양한 접근

 

Step 1 : 문제 이해하기 → '접근 방법'을 생각해내기위해서는 문제를 제대로 이해해야한다.

Step 2 : 접근 방법 → 제일 중요. 문제를 어떻게 풀지 '접근 방법'을 생각해내야만 코드를 구현할 수 있다.

접근방법을 생각해내기 위해서 '자료구조'와 '알고리즘'을 수박겉핥기 식으로 배우는게 아니라, 밑바닥부터 공부를 한다.

Step 3 : 코드 설계

Step 4 : 코드 구현

 

그냥 시간 복잡도는 이거다, 이렇게 하고 지나가는게 아니라, 왜 Big-O(n)인지, 왜 Big-O(1)인지 등을 하나하나 이해를 해야 나중에 접근 방법을 생각해낼때 자료구조 특성, 알고리즘 특성을 활용할 수 있다.

다양한 접근 방법을 생각해낼 수 있어야 한다.

 

 

# 제약조건

알고리즘 문제들을 풀다보면 이런 제약조건들이 있다.

문제에서 괜히 제약조건을 주는게 아니다. 제약조건의 의미를 파악하는게 중요하다.

 

시간복잡도(Big-O)에 데이터 크기(n)을 넣어서 나온 값이 100,000,000(10⁸)이 넘으면 시간제한 초과할 가능성이 있다!

 

 

 

대부분의 코딩테스트에서는 문제가 주어지면 그 문제를 효율성있게 푸는지를 중요하게 본다.

그래서 정답도출하는 방법이 다양하지만, 그 중에서 효율적인것 즉, 실행시간이 적은 것을 생각해낼 수 있는지 물어보게 된다.

즉, 실행시간이 적은 '알고리즘'을 생각해 낼 수 있는지.

실행시간이 적으려면 → 시간복잡도가 작아야한다.

 

실행시간은

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³) 이 순서대로 실행시간이 커지는데, 여기다가 n의 값이 무엇이냐에 따라서 실행시간이 달라진다.

시간복잡도가 O(n³)이지만, n이 고작 10밖에 안되면 10을 넣어 봤자 크기가 얼마 안크다.

 

그럼 숫자를 넣었을 때, 숫자 몇이 나와야 시간이 오래 걸리는걸까?

프로그램을 돌리는 CPU의 환경, 컴퓨터의 환경에 따라서 실행시간은 다 다르게 나온다.

 

 

코딩테스트에서 보통 10⁸이 넘지 않도록 맞춰놔야한다.

예를 들어, 제약 조건이 10⁵이다. 그럼 O(n³)으로 푼다면 총 10¹⁵이 된다. 따라서 O(n³)으로 풀면 안된다.

그럼 O(n²)로 풀면 될까? 그럼 10¹⁰이 되고 이것도 10⁸이 넘는다. → O(n²)로 풀면 x.

 

즉, 제약조건에서 n의 크기가 10⁵이라면, O(n²)보다 높은 시간복잡도로 풀지 말라는 것.

O(n²)보다 시간복잡도가 낮은 O(nlogn), O(n), O(logn), O(1) 이런 시간복잡도로 풀라는 문제 의도가 있다.

 

그렇다면 10⁴은 어떨까?

O(n²)도 조금 간당간당하다. O(n²)로 풀 수도 있고, 시간초과가 날 수도 있다.

되도록 10⁴인 경우에는 "O(nlogn), O(n), O(logn), O(1) 이런 시간복잡도로 풀어라" 는 뜻.

10³은? O(n²)에 넣으면 10⁶이 되므로 충분히 O(n²)로 풀 수 있다.

 

 

1 <= n <= 7

이런 제약조건이 작은 경우, n!같이 무자비하게 완전탐색을 하고, 비효율적으로 짜고 그렇게 해도 정답만 도출해낼 수 있다면 그 문제는 통과를 할 수 있다는 뜻. 그래서 이런 경우엔 정말 답을 찾는게 중요하다.

 

제약조건이 더 커질수록 효율적인 알고리즘을 생각해낼 수 있냐의 문제이다.

 

이제 진짜 문제를 보면서 Step 1 문제 이해하기의 제약조건을 우리가 어떻게 해석해야하는지 보자.

제약조건이 없는 문제는 정답만 도출해내면 되기 때문에 효율적인 알고리즘을 생각해 낼 필요는 없다.

코딩테스트에서 이런 문제도 많다. 정답만 도출해내면 되기 때문에 훨씬 쉽다.

 

효율성있는 테스트문제를 제대로 풀수만 있다면 제약조건이 없는 문제들도 충분히 풀 수 있다.

 

Step 1

 

## 제약조건 중, n 찾기

문제를 보면, 제약조건이 여러개 주어진다.

시간복잡도에 n을 집어넣어 나온 값이 10⁸을 넘으면 안된다.

 

만약 두번째 nums[i]가 n이라면, n2, nlogn, n 전부 10⁸이 넘어간다.

target이 n이어도 마찬가지로 전부 10⁸이 넘어간다.

따라서 만약 nums[i] 또는 target이 n이라면, O(1), O(logn) 알고리즘을 구상해야한다.

 

그럼 이 제약조건에서 nums.length, nums[i], target 중, 누가 n일까?

결정요인은 바로, 이 숫자가 커지면 커질수록 실행시간도 증가하는지를 보면 된다.

만약 배열 nums의 두 숫자를 더하여 14가 될 수 있는지 없는지 판별할 때, nums의 길이가 짧으면 짧을수록 금방 판별할 수 있다.

길이가 길어지면 길어질수록 일일이 더해서 다 봐야한다. nums의 요소가 100개라면 훨씬 더 오래걸린다.

 

targe의 숫자가 커져서 100, 200이 된다고 해도 target의 숫자가 커진다고 실행시간이 더 오래 걸리지는 않는다.

nums[i] : 원소 하나하나의 크기가 클수록 두 원소를 더하는 시간이 길어지지는 않는다.

따라서, nums.length, 즉 원소의 개수가 n이 된다.

 

 

## 시간복잡도에 따른 알고리즘

제약조건이 10⁴까지이므로, O(n²) 이하의 풀이방법을 떠올리면 문제를 풀 수 있다.

O(n²)는 조금 간당간당해서 만약 문제를 풀 때 O(n2)의 문제풀이방법만 떠오른다면 어쩔 수 없이 이 방법으로 풀어야하지만, 그렇지 않으면 O(nlogn), O(n)으로 풀 수 있는게 없는지 생각해봐야한다.

 

그래서 step1 문제 이해하기에서 최대한 많은 정보를 뽑아내야한다.

input 중 어떤걸 n으로 설정할 수 있는지, 어떤 경우에는 n 하나만 있는 것이 아니라, 시간복잡도를 결정짓는 것 중, O(n+m) 이렇게 M이 하나 더있는 경우도 있다.

input에서 어떤 정보가 실행시간을 더 늘릴 것인지에 대한 판별을 해야한다.

그리고 제약조건이 주어져있으면 그것대로 시간복잡도가 무엇인 알고리즘을 생각해내야하는지 결정할 수 있다.

 

이런 것이 바로 코딩테스트를 위한 시간복잡도!

 

 

**출처 : 모든 내용은 인프런의 '코딩테스트 [ALL IN ONE]'강의를 기반으로 작성하였습니다.