코딩테스트의 핵심은 주어진 문제에 시간복잡도를 얼마나 잘 고려하여 알고리즘을 선택하는지가 중요하다.
이번 포스팅에서는 시간복잡도에 대한 개념과 이를 문제에 어떻게 활용할 수 있는지에 대해 작성하고자 한다.
시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.
실제 시간복잡도는 크게 3가지 표기법으로 나타내어 지고는 한다.
만약 n^2기준이라면 각각의 시간 복잡도는 아래와 같은 의미를 가지거나 최소 만족해야 한다.
💡코딩테스트에서는 빅-오 표기법을 기준으로 수행시간을 계산하는 것이 좋다.
우리는 해결할 문제에 대해 다양한 테스트 케이스를 수행하게 되고, 모든 케이스에 통과해야만 합격을 할 수 있으므로, 시간복잡도를 판단할 때는 최악의 상황(빅-오)을 염두에 둬야 한다.
시간복잡도는 데이터가 적을 때는 수행 시간에 큰 차이가 없다.
하지만 데이터 양이 많아질수록 시간복잡도에 차이는 기하급수적으로 커진다.
따라서 어떤 시간복잡도를 염두에 두고 문제를 풀어가는가에 따라 수행시간이 매우 다를 수 있다는 것을 알 수 있다.
다음은 시간복잡도를 코딩테스트에서 어떻게 적용해야 할 지에 대해 알아보고자 한다.
우리는 주어진 시간과 데이터 크기를 바탕으로 어떤 알고리즘을 사용할 지 판단해야 한다.
📍 연산 횟수 계산 방법
연산 횟수 = 알고리즘 시간복잡도 n값에 데이터의 최대 크기를 대입하여 도출
위 연산 횟수를 구하는 공식을 이용하여 어떤 알고리즘이 문제에 적합한 지 판단할 수 있다.
예를 들어, 버블 정렬의 경우 O(n^2)의 빅오 표기법의 시간복잡도를 가진다.
만약 주어진 문제가 1<= N <= 1,000,000의 범위에서 구하라고 주어졌으면 n에 1,000,000을 대입하여 연산 횟수를 도출할 수 있다.
버블 정렬은 그러면 1,000,000,000,000의 연산 횟수를 가지게 되고, 만약 문제에서 연산 횟수 40,000,000번 안에 원하는 답을 구해야 하는 상황이라면 버블 정렬을 이용해 문제를 푸는 것은 적절하지 않다는 것이다.
따라서 연산 횟수 계산을 통해 적절한 알고리즘을 선택해 문제를 풀어야 한다.
시간복잡도는 작성한 코드의 비효율적인 로직을 개선하는데 활용할 수 있어야 한다.
이를 위해 먼저 코드의 시간복잡도를 도출할 수 있어야 한다.
📍시간복잡도 도출 기준
- 상수는 시간복잡도 계산에서 제외
N = 1000 cnt = 1 for i in range(N): print("연산횟수: " + str(cnt)) cnt += 1
위 코드에 대한 예상 연산 횟수는 최악의 기준으로 N번일 것이다.
N = 1000 cnt = 1 for i in range(N): print("연산횟수: " + str(cnt)) cnt += 1 for i in range(N): print("연산횟수: " + str(cnt)) cnt += 1
위 코드에 대한 예상 연산 횟수는 반복문이 두 번이므로 2N번일 것이다.
각각의 코드에 대한 연산 횟수는 N, 2N번으로 2배 정도 차이날 수 있지만, 코딩테스트에서는 일반적으로 상수를 무시하므로 두 코드에 대한 시간복잡도는 모두 O(N)이라 할 수 있다.
- 가장 많이 중첩된 반복문의 수행 횟수가 시간복잡도의 기준
N = 1000 cnt = 1 for i in range(N): for j in range(N): print("연산횟수: " + str(cnt)) cnt += 1
다음과 같이 이중 for문인 중첩된 반복문을 가진 코드가 있다.
시간복잡도는 가장 많이 중첩된 반복문을 기준으로 수행 횟수가 결정된다. 따라서 위 코드에서는 이중for문이 전체 시간복잡도의 기준이 되므로 O(n^2)의 시간복잡도를 가지게 된다.
만약 중첩되지 않은 다른 일반 for문이 100개 있다고 하더라도 이중for문 혹은 더 중첩된 반복문이 있다면 100개의 일반 for문은 시간복잡도에 영향을 주지 않게 된다.
만약 코딩테스트를 수행하다 시간 초과가 발생했다면 이 원리를 바탕으로 코드에서 문제가 되는 부분을 도출해낼 수 있어야 한다.
문제가 되는 부분을 효율적인 구조로 수행하는 작업을 통해 문제를 해결할 수 있을 것이다.
[Algorithm] 시간복잡도 개념 정리 및 활용
코딩테스트의 핵심은 주어진 문제에 시간복잡도를 얼마나 잘 고려하여 알고리즘을 선택하는지가 중요하다.
이번 포스팅에서는 시간복잡도에 대한 개념과 이를 문제에 어떻게 활용할 수 있는지에 대해 작성하고자 한다.
시간복잡도
시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.
실제 시간복잡도는 크게 3가지 표기법으로 나타내어 지고는 한다.
만약 n^2기준이라면 각각의 시간 복잡도는 아래와 같은 의미를 가지거나 최소 만족해야 한다.
💡코딩테스트에서는 빅-오 표기법을 기준으로 수행시간을 계산하는 것이 좋다.
우리는 해결할 문제에 대해 다양한 테스트 케이스를 수행하게 되고, 모든 케이스에 통과해야만 합격을 할 수 있으므로, 시간복잡도를 판단할 때는 최악의 상황(빅-오)을 염두에 둬야 한다.
시간복잡도는 데이터가 적을 때는 수행 시간에 큰 차이가 없다.
하지만 데이터 양이 많아질수록 시간복잡도에 차이는 기하급수적으로 커진다.
따라서 어떤 시간복잡도를 염두에 두고 문제를 풀어가는가에 따라 수행시간이 매우 다를 수 있다는 것을 알 수 있다.
시간복잡도 활용
다음은 시간복잡도를 코딩테스트에서 어떻게 적용해야 할 지에 대해 알아보고자 한다.
1️⃣ 알고리즘 선택 기준으로 시간복잡도를 활용해라
우리는 주어진 시간과 데이터 크기를 바탕으로 어떤 알고리즘을 사용할 지 판단해야 한다.
📍 연산 횟수 계산 방법
연산 횟수 = 알고리즘 시간복잡도 n값에 데이터의 최대 크기를 대입하여 도출
위 연산 횟수를 구하는 공식을 이용하여 어떤 알고리즘이 문제에 적합한 지 판단할 수 있다.
예를 들어, 버블 정렬의 경우 O(n^2)의 빅오 표기법의 시간복잡도를 가진다.
만약 주어진 문제가 1<= N <= 1,000,000의 범위에서 구하라고 주어졌으면 n에 1,000,000을 대입하여 연산 횟수를 도출할 수 있다.
버블 정렬은 그러면 1,000,000,000,000의 연산 횟수를 가지게 되고, 만약 문제에서 연산 횟수 40,000,000번 안에 원하는 답을 구해야 하는 상황이라면 버블 정렬을 이용해 문제를 푸는 것은 적절하지 않다는 것이다.
따라서 연산 횟수 계산을 통해 적절한 알고리즘을 선택해 문제를 풀어야 한다.
2️⃣ 코드 로직 개선에 시간복잡도를 활용해라
시간복잡도는 작성한 코드의 비효율적인 로직을 개선하는데 활용할 수 있어야 한다.
이를 위해 먼저 코드의 시간복잡도를 도출할 수 있어야 한다.
📍시간복잡도 도출 기준
- 상수는 시간복잡도 계산에서 제외
위 코드에 대한 예상 연산 횟수는 최악의 기준으로 N번일 것이다.
위 코드에 대한 예상 연산 횟수는 반복문이 두 번이므로 2N번일 것이다.
각각의 코드에 대한 연산 횟수는 N, 2N번으로 2배 정도 차이날 수 있지만, 코딩테스트에서는 일반적으로 상수를 무시하므로 두 코드에 대한 시간복잡도는 모두 O(N)이라 할 수 있다.
- 가장 많이 중첩된 반복문의 수행 횟수가 시간복잡도의 기준
다음과 같이 이중 for문인 중첩된 반복문을 가진 코드가 있다.
시간복잡도는 가장 많이 중첩된 반복문을 기준으로 수행 횟수가 결정된다. 따라서 위 코드에서는 이중for문이 전체 시간복잡도의 기준이 되므로 O(n^2)의 시간복잡도를 가지게 된다.
만약 중첩되지 않은 다른 일반 for문이 100개 있다고 하더라도 이중for문 혹은 더 중첩된 반복문이 있다면 100개의 일반 for문은 시간복잡도에 영향을 주지 않게 된다.
만약 코딩테스트를 수행하다 시간 초과가 발생했다면 이 원리를 바탕으로 코드에서 문제가 되는 부분을 도출해낼 수 있어야 한다.
문제가 되는 부분을 효율적인 구조로 수행하는 작업을 통해 문제를 해결할 수 있을 것이다.
'Algorithm > 개념정리' 카테고리의 다른 글