자바 알고리즘 | 코딩테스트에서 필수적인 시간 복잡도 개념과 활용 방법

 

최근 자바 공부를 다시 시작하면서 알고리즘 문제를 해결하려고 노력하고 있다.

그러나 여러 문제에서 런타임 에러가 발생하는데, 특히 중첩 for문을 사용하는 경우에 많이 발생한다.

이러한 문제를 해결하기 위해서는 시간 복잡도를 공부하고, 효율적인 알고리즘을 설계하는 방법을 배워야 한다.

시간 복잡도를 이해하면, 같은 문제를 더 효율적으로 해결할 수 있다.

 

✅ 시간 복잡도

알고리즘이 처리하는 입력 크기와 실행 시간 간의 상관관계를 나타낸다. 

알고리즘이 입력 크기에 따라 처리하는 데 걸리는 시간의 증가율을 나타내는 지표이다. 

입력 크기와 실행 시간 간의 상관관계를 분석하여 알고리즘의 성능을 평가할 수 있다.

이를 통해 더 효율적인 알고리즘을 설계하고, 불필요한 자원 낭비를 방지할 수 있다.

 

💡 시간 복잡도 조건

최선, 평균, 최악의 경우 모두를 고려해야 한다.

• 알고리즘의 성능을 정확하게 예측할 수 있도록 도와준다.

 

입력값의 크기를 고려해야 한다.

• 일반적으로 입력값이 크면 클수록 알고리즘의 실행 시간은 증가한다.

 

기본 연산의 실행 횟수를 계산해야 한다.

• 기본 연산이란 알고리즘이 수행하는 가장 기본적인 연산을 말한다.
• 배열에서 최솟값을 찾는 알고리즘이 있다면, 기본 연산은 배열에서 값을 비교하는 연산이다.

 

대상이 되는 입력값의 범위를 고려해야 한다.

• 입력값이 항상 양의 정수인 경우와 음의 정수가 포함된 경우의 시간 복잡도는 다를 수 있다.

 

💡 시간 복잡도 표기 유형

알고리즘의 실행 시간을 분석하고 비교하는 데에는 빅-오(O), 빅-오메가(Ω), 빅-세타(Θ)와 같은 표기법이 사용된다.

 

• 빅-오메가(Ω)는 알고리즘이 최선일 때의 연산 횟수를 나타내며, 입력값이 가장 이상적인 경우에 알고리즘이 얼마나 효율적인지를 나타낸다.
• 빅-세타(Θ)는 알고리즘이 보통일 때의 연산 횟수를 나타내며, 입력값이 평균적인 경우에 알고리즘이 얼마나 효율적인지를 나타낸다.
• 빅-오(O)는 알고리즘이 최악일 때의 연산 횟수를 나타내며, 입력값이 가장 안 좋은 경우에 알고리즘이 얼마나 비효율적인지를 나타낸다.

 

빅-오(O) 표기법은 알고리즘의 성능을 분석하고 비교하는 데에 매우 유용하다.
입력 크기가 커질수록 알고리즘의 실행 시간은 기하급수적으로 증가하기 때문에, 대규모 입력에 대한 예측이 필요하다.

따라서 빅-오(O) 표기법을 사용하여 알고리즘의 실행 시간을 분석하고 비교하는 것이 중요하다. 

단일 테스트 케이스의 실행 결과로 성능을 판단하면 안 되며, 대규모 입력에 대한 예측이 필요하다.

 

💡 시간 복잡도 계산 과정

1. 알고리즘의 기본 연산을 찾는다.
2. 기본 연산이 실행되는 횟수를 입력 크기에 대한 함수로 나타낸다.
3. 입력 크기에 대한 함수를 단순화한다.
4. 단순화된 함수에서 가장 높은 차수의 항만을 남기고, 계수를 제외한다.
5. 최종적으로 남은 항이 시간 복잡도이다.

 

코딩테스트에서는 대체로 시간제한이 1초 이하인 경우가 많기 때문에 이를 고려하여 설계하고 계산하는 것이 중요하다.

따라서 1억 번의 실행 횟수를 1초로 계산하는 것은 유용하다.

이를 기준으로 시간 복잡도를 계산하면 어느 정도 수행 시간을 예측할 수 있다.

가장 많이 사용되는 시간 복잡도는 O(1), O(log n), O(n), O(n log n), O(n^2)이다.

• O(1)
  • 입력값의 크기에 상관없이 일정한 실행 시간을 가지므로 가장 빠른 시간 복잡도이다.
  • 배열에서 특정 인덱스에 접근하는 경우이다.
• O(log n)
  • 입력값이 2배씩 증가할 때마다 실행 시간이 1배씩 증가한다.
  • 이진 탐색과 같은 알고리즘의 경우이다.
• O(n)
  • 입력값의 크기에 비례하여 실행 시간이 증가한다.
  • 배열의 모든 요소를 순회하면서 처리하는 경우이다.
• O(n log n)
  • 입력값이 커질수록 실행 시간이 증가하지만 O(n^2)보다는 빠른 실행 시간을 가진다.
  • 대부분의 퀵 정렬과 병합 정렬과 같은 정렬 알고리즘의 경우이다.
• O(n^2)
  • 입력값의 제곱에 비례하여 실행 시간이 증가한다.
  • 이중 반복문을 사용하여 이차원 배열을 처리하는 경우이다.

 

💡 예시

 0부터 99까지의 숫자 중에서 무작위로 하나를 선택하고, 선택된 숫자를 찾을 때까지 0부터 99까지의 숫자를 하나씩 증가시키는 코드이다.

 

• 선택된 숫자가 0이라면, 코드는 한 번만 실행되며 숫자를 찾았을 때 바로 반복문을 빠져나가기 때문에 최선의 경우(best case)의 시간 복잡도는 O(1)이다.
• 선택된 숫자가 99라면, 모든 숫자를 다 검색해야 하기 때문에 최악의 경우(worst case)의 시간 복잡도는 O(100)이다.

선택된 숫자는 무작위로 선택되기 때문에 중간 정도의 시간 복잡도를 가진다.

 

public class Main {
    public static void main(String[] args) {
        int findNumber = (int) (Math.random() * 100); // 0부터 99까지의 숫자 중 무작위로 선택
        for (int i = 0; i < 100; i++) {
            if (i == findNumber) { // 선택된 숫자를 찾았을 경우
                System.out.println(i); // 숫자 출력
                break; // 반복문 종료
            }
        }
    }
}

 

💡 코딩테스트 활용

코딩테스트에서 시간 복잡도를 활용하는 방법은 크게 두 가지이다.

 

문제의 제한 시간 파악하기

• 코딩테스트에서는 주어진 시간 내에 정확한 결과를 출력해야 한다. 
• 문제에서 제한된 시간을 파악한다. 
• 해당 시간 복잡도 내에 문제를 해결할 수 있는 알고리즘을 구현한다.
• 코딩테스트에서는 보통 1초 내 처리할 수 있는 입력의 크기가 정해져 있다.
• 입력의 크기가 10,000일 때
  • O(N^2)인 알고리즘은 1초 내에 처리할 수 없다.
  •  O(NlogN)이나 O(N) 알고리즘은 1초 내 처리할 수 있다.

 

다양한 알고리즘 비교하기

• 코딩테스트에서는 정확한 결과를 출력하는 것뿐만 아니라 최적의 알고리즘을 사용하여 시간과 메모리를 최적화하는 것이 중요하다. 
• 시간 복잡도를 고려하여 다양한 알고리즘을 비교하고 최적의 알고리즘을 선택해야 한다.