시간 복잡도 활용
시간 복잡도란?
시간 복잡도(Time complexity)는 주어진 문제를 해결하기 위해 필요한 연산의 횟수를 의미하며, 보통 1억번의 연산을 수행시간 1초로 간주
시간 복잡도는 문제를 해결하기 위해 사용하는 알고리즘을 선택하는 기준
시간 복잡도 유형
- Big-Omega : 최선인 경우의 연산 횟수를 나타내는 표기법으로 𝛺(n)은 최대 n번의 연산이 필요함을 의미
- Big-Theta : 보통인 경우의 연산 횟수를 나타내는 표기법으로 𝛩(n)은 거의 n번의 연산이 필요함을 의미
- Big-O : 최악인 경우의 연산 횟수를 나타내는 표기법으로 O(n)은 최소 n번의 연산이 필요함을 의미
가장 많이 사용되는 것은 Big-O 표기법
시간 복잡도 활용하기
알고리즘 선택하기
주어진 데이터의 개수(n)를 구현한 알고리즘의 시간 복잡도(Big-O 표기법)에 대입하여 대략적인 연산 횟수를 계산
주어진 제한 시간을 이용하여 허용된 연산 횟수를 계산하여 앞서 구한 연산 횟수와 비교
비교 결과에 따라 알맞은 알고리즘을 선택
Example :
1≤N≤1,000,000인 수를 정렬할 때, 시간 제한이 2초라면 허용된 연산 횟수는 2억번이다.
버블 정렬은 O(n^2)이므로 연산 횟수는 (1,000,000)^2 = 1조번, 병합 정렬은 O(nlogn)이므로 연산 횟수는 약 2백만번
따라서 위의 조건에 따라 문제를 해결하기 위해서는 병합 정렬 알고리즘을 사용해야 한다.
코드 로직 개선하기
자신의 코드에 대한 시간 복잡도를 계산
- 상수는 시간 복잡도 계산에서 제외(시행 횟수에 곱해지거나 더해지는 상수는 실제로 수행 시간에 큰 영향을 주지 않음)
- 가장 중첩이 많이 일어난 반복문의 시행 횟수를 시간 복잡도의 기준으로 설정
Example :
특정 작업을 N번 수행하는 for문이 1개 존재하면 시간 복잡도는 O(n)
특정 작업을 N번 수행하는 for문이 4개 존재하면 시간 복잡도는 O(4n) -> O(n)
특정 작업을 N번 수행하는 for문이 3개 존재하고 마지막에 더하기 연산을 5번 시행하면 시간 복잡도는 O(3n+5) -> O(3n) -> O(n)
특정 작업을 N번 수행하는 for문 안에 특정 작업을 N번 수행하는 for문이 중첩되어 있다면 시간 복잡도는 O(n^2)
위의 방법으로 불필요한 중첩 반복문을 줄이는 과정으로 시간 복잡도를 감소
디버깅 활용
디버깅이란?
디버깅(Debugging)은 프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정을 의미
문법 오류는 컴파일러가 찾아서 컴파일 에러를 발생시키지만, 논리 오류는 프로그램이 실행되는 동안에 런타임 에러를 발생시키거나 프로그램의 의도와 다르게 동작하게 만드는 문제 발생
디버깅 방법
디버깅을 진행하고자 하는 코드에 break point를 설정하고 IDE의 디버깅 기능을 실행
IDE의 디버깅 기능을 실행하면 한 줄씩만 코드를 실행하거나 다음 중단점까지만 코드를 실행할 수 있으며, 추적할 변수를 지정하면 변수가 변하는 과정을 파악 가능
위의 과정을 통해 변수가 의도한 대로 변하는지, 의도한 흐름대로 코드가 동작하는지 파악, 특히 변수 초기화, 반복문의 범위 지정, 변수 타입 오류 등을 주의