동기: 프로그래머스 코테중 효율성 이슈
프로그래머스에서 알고리즘 1d 1p를 하는도중 답은 맞지만 효율성에서 문제가 생겼다.
문제점을 찾아보니 max와 min함수는 O(n)의 시간이 들면서 시간복잡도에 대한 설명이 나왔다.
Level1까지는 답만 맞으면 됐지만 level2에서부터는 효율문제도 같이 봐야했다.
시간 복잡도(Time Complexity)
알고리즘 수행시간 분석시 시간복잡도를 사용한다.
수행시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행시간을 평가한다.
기본연산
-
데이터 입출력 - copy, move...
-
산술 연산 - add, multiply ...
-
제어 연산 - if, while ...
> ### 종류
- O(Big-O): 최악의 시간 복잡도
- Ω(Omega): 최선의 시간 복잡도
- Θ(Theta): 평균 정도의 시간 복잡도
여기서 우리가 흔히 말하는 "이 코드의 시간 복잡도는 얼마에요?" 라는 물음에 답을 할 때는 Big-O(빅오) 표기법을 사용한 시간 복잡도를 말한다.
왜냐, Big-O 표기법은 최악의 경우를 고려하는 것이므로 프로그램 실행 과정 중 최악의 시간까지 미리 생각해 볼 수 있기 때문이다.
> ### Big-O 시간 복잡도는 다음과 같은 방법으로 적당히 알고리즘을 평가한다.
- 최악의 상황만 가정한다
- 운 좋게 암산하기 좋은 숫자가 나오는 최선의 상황(Big-omega)은 가정하지 않는다.
- 평균적인 상황(Big-Theta)이 어떤지도 계산하지 않는다. 곱셈의 '평균적인 상황'을 정의하기 쉽지 않기 때문이다. - 연산의 횟수가 적을수록 효율적인 알고리즘으로 본다. 다른 변수(하드웨어 성능 등)는 무시한다.
연산의 횟수도 정확하게 세는게 아니라 대충 어림짐작한다.
시간 복잡도는 어디까지나 '정확히'가 아니라 '적당히' 계산한다는 점을 잊어선 안된다. 실제 소프트웨어의 성능에 영향을 미치는 수많은 요소(하드웨어 성능, 메모리 계층구조의 적절한 사용, 캐싱 여부 등)를 모두 무시한다. 중요하지 않아서가 아니라 계산하기 어려워서이다.
시간 복잡도를 계산해보자
연산 카운팅 기준
- 대입
- 사칙연산
계산해보자!
O(1)
// 1번 코드
int sum = (x+1)*x/2;2번 코드 같은 경우 '(x+1)'이 한 번, '*x'가 한 번, '/2'가 한 번 계산된 값을 sum에 대입할 때 한 번 이렇게 총 네 번이므로 4가 되지만, Big-O 표기법으로는 O(1)이 된다.
O(1)
// 2번 코드
int sum = 0;
for(int i = 0; i<n; i++){
sum+=i;
}1번 코드는 'sum=0' 한 번, 'int i = 0'이 한 번, 'i++'이 n번,'sum+=i'가 n번 합쳐서 총 2n+2번의 연산이 수행된다.
Big-O 표기법에서는 최대 차항만 계수없이 표기하기 때문에 O(1)이 된다.
O(n²)
// 3번 코드
int sum = 0;
for(int i = 0; i<n; i++){
for(int j = 0; j<i;j++){
sum+=j;
}
}3번 코드의 바깥쪽 반복문은 n번, 안쪽 반복문은 i의 값에 따라 반복합니다.
i는 0부터 n-1까지 변하고, 안쪽 반복문은 해당하는 i만큼 반복하므로 0+1+2+...+(n-1) = n*(n-1)/2번(등차수열의 합 공식) 반복합니다.
이 역시 최대 차항만 계수없이 표기하게되면 O(n²)이 됩니다.
O(N)<logN번 반복>
// 4번 코드 int sum = 0; for(int i = n; i>0; i/=2){ for(int j = 0; j<i; j++){ sum+=j; } }
4번 코드는 바깥쪽 반복문이 logN번 반복, 안쪽 반복문은 i값에 따라 반복 횟수가 달라집니다.
(💡 logN번 반복인 이유는 i/=2이기 때문)
i는 n부터 1까지 변하고, 안쪽 반복문은 해당하는 i만큼 반복하므로 n+(n/2)+(n/4)+..+1 = 2n번 반복하므로 O(N)이 됩니다.
시간복잡도를 고려하는 이유
시간복잡도는 다양한 풀이법(알고리즘) 중에 어느 것이 더 효율적인지를 판별하기 위해 만든 것이다.
ex) 우리나라 인구 5000만명중에서 한 사람을 조회하는 알고리즘 2개가 있다.
A알고리즘: O(log n)
B알고리즘: O(n^2)
->A알고리즘은 25번, B알고리즘은 2500000000000000번의 연산을 수행한다.
->A알고리즘은 1초도 안되는 시간이 걸린다.
->B알고리즘은 120일 정도 걸린다..
그럼에도 우리는 시간이란 소중한 자원을 낭비하지 않기 위해서 언제나 시간복잡도를 낮추기 위한 노력을 한다.
이러한 노력을 최적화라고 부른다.
Tip
추가로 알고리즘 문제를 풀 때 시간복잡도를 대략적으로 맞추는 방법을 소개하려 한다.
(백준,swea를 이제 막 풀기 시작한 분들을 위해서 쓴 글입니다! 참고해주세요ㅎㅎ)
여기서 시간제한 1초가 의미하는 것은, 내 코드를 실행했을 때 실행시간이 1초 내여야한다는 것을 뜻한다.
대부분의 환경에서 1억번 연산이 1초 정도 걸리기 때문에,
내 코드에 제일 큰 테스트케이스를 돌려도 연산이 1억번 내여야만 통과가 된다는 것이다.
그러므로, 문제를 풀기 전에 시간 제한과 입력 데이터의 수를 확인하고 나서
어느정도의 시간복잡도로 코드를 짜야겠다고 계획을 하고 코딩을 하는 것이 좋다.
아래 링크에 시간복잡도를 문제에서 어떻게 활용하는가 잘 나와있음.
팁링크
팁요약
1. 시간 제한, 최대 입력 데이터의 크기를 확인하고 내가 짜야하는 코드의 시간복잡도를 생각한다.
2.그에 맞춰서 코딩을 한다
3.가장 큰 테스트 케이스를 넣어본다.
4.출력 시간을 체감해본다 or 프로파일링 기능을 사용해서 측정해본다 or <time.h>를 추가해서 시간을 출력해본다
--------------------------------------------------------------
> ## 정리 즉 Big-O 표기법을 간단하게 정리하면 1) 연산의 개수를 세어본다. 2) 가장 높은 차수만 남긴다. ex) O(n²+n) => O(n²) 3) 계수 및 상수는 과감하게 버린다. ex) O(2n+3) => O(n) cf) 내장함수에 대한 시간복잡도는 공식문서에 있다.
효율성 통과시키는 방법
1.런타임 에러
- 재귀함수 이용 줄이기
- 내장함수의 파라미터 개수 줄이기 (스택 사이즈 초과)
2. 시간 초과
- 사용된 내장함수 수행시간 확인 후, 다른 방법으로 대체하기
- 알고리즘 문제
결론: 알고리즘 새로 짜기
노마드 코더 행님의 레전드 설명: https://www.youtube.com/watch?v=BEVnxbxBqi8
닥터스트레인지 사진 출처: https://www.4flix.co.kr/board/free/66520?sfl=mb_id%2C1&stx=admin&sst=wr_good&sod=asc&sop=and&page=240
