이 전의 기초 알고리즘 책을 끝내고, 좀 더 심화내용이 담겨있는 책으로 공부를 시작했다.
시간 복잡도, 버블/병합정렬, 자료구조등에 대한 기본적인 지식이 있다는 가정 하에 알고리즘시리즈를 이어나가자.
이 책은 '백준 온라인 저지'를 활용해서 작성된 책이기에 누구나 백준에 접속해서 테스트 할 수 있다.
수 정렬하기 - 백준 2750
N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.
입력 │←
1번째 줄에 수의 개수 N(1 <= N <= 1,000,000), 2번째 줄부터는 N개의 줄에 숫자가 주어진다. 이 수는 절대값이 1,000,000보다 작거나 같은 정수이고, 각각의 수는 중복되지 않는다.
출력 │→
1번째 줄부터 N개의 줄에 오름차순 정렬한 결과를 1줄에 1개씩 출력한다.
조건
시간 제한 : 2초
참고
이 포스트에서는 해당 문제에 대한 정답 코드를 작성하지 않습니다.
그저 분석과 알고리즘 선택등을 배웁니다.
분석
시간 제한이 2초라는 뜻은 이 조건을 만족하려면 2억 번 이하의 연산 횟수로 문제를 해결해야 한다. 따라서 문제에서 주어진 시간 제한과 데이터 크기를 바탕으로 우리는 어떤 정렬 알고리즘을 사용할 수 있는지 생각해 봐야한다.
- 연산 횟수는 1초에 1억 번 연산하는 것을 기준으로 생각한다.
제한 시간 1초 = 1억 번, 제한 시간 5초 = 5억 번
- 시간 복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클 때를 기준으로 하자.
연산 횟수 계산해보기
우리가 기본적으로 사용하는 정렬은 여러가지가 있기에 이들의 시간 복잡도를 활용해서 총 몇 번의 연산이 실행되는지 예측해 볼 수 있겠다.
사용 할 알고리즘의 시간 복잡도 x 데이터의 최대 크기 = 최대 연산 횟수
버블 정렬
정렬을 처음 배울때 알게되는 '버블 정렬'은 정렬 중에서도 매우 쉽게 구현이 가능하나, 최악의 성능을 가지고 있다.
시간 복잡도는 O(n^2)로 알려져 있다.
따라서 위 문제의 최대 데이터 크기인 1,000,000이고 이를 제곱해 보자.
1,000,000² = 1,000,000,000,000(1조) > 200,000,000 → 제한 시간을 아득히 넘는다.
병합 정렬
보통 버블 정렬 다음에 배우게 되는 병합 정렬은 구현하기 조금 복잡해 지지만 성능은 획기적으로 단축시킬 수 있는 정렬이다.
시간 복잡도는 O(n log n)으로 알려져 있다.
1,000,000log(1,000,000) = 약 20,000,000 < 200,000,000 → 제한 시간내 연산 가능.
결론
위 결과들을 바탕으로 이 문제에서는 '병합 정렬'을 사용해야 함을 알 수 있다.
이와 같은 일련의 분석으로 문제에서 사용할 수 있는 알고리즘을 적절히 사용해야한다.
"병합 정렬이 성능이 좋으니 무조건 버블 정렬은 버려야해" 라는 생각은 좋지 않다. 최대 데이터의 수가 20개정도 되는 데이터를 정렬하는데 병합 정렬을 사용할 필요는 없지 않은가.
시간 복잡도를 바탕으로 코드 로직 개선하기
시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로 사용할 수 있다. 이 부분을 활용하려면 가장 먼저 코드의 시간 복잡도를 도출할 수 있어야하고 도출 하려면 다음 2가지 기준을 고려해야 한다.
- 상수는 시간 복잡도 계산에서 제외
- 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 됨.
연산 횟수가 N인 경우,
int N = 100000;
int cnt = 0;
for (int i = 0; i < N; i++) {
System.out.println("연산 횟수:" + cnt++);
}연산 횟수가 3N인 경우,
int N = 100000;
int cnt = 0;
for (int i = 0; i < N * 3; i++) {
System.out.println("연산 횟수:" + cnt++);
}두 예제의 경우 연산 횟수는 각각 100,000과 300,000으로 3배나 차이난다!
하지만 컴퓨터는 이정도 연산은 우리가 인지하기도 전에 끝내기 때문에 보통 상수는 무시한다.
따라서 두 코드 모두 시간복잡도는 그저 n에 비례한 것이라 O(n)으로 같다.
그렇다면 아래 경우는 어떨까?
연산 횟수가 N²인 경우,
int N = 100000;
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.println("연산 횟수:" + cnt++);
}
}
for (int i = 0; i < N; i++) {
System.out.println("연산 횟수:" + cnt++);
}
for (int i = 0; i < N; i++) {
System.out.println("연산 횟수:" + cnt++);
}
for (int i = 0; i < N; i++) {
System.out.println("연산 횟수:" + cnt++);
}위 코드의 경우 총 연산이 100,000²번 + 300,000번 일어나고 이런 경우
기준 2번에 의해 가장 많이 중첩된 이중 for문이 기준이 된다. 따라서 일반 for문이 100개가 더 있다고 하더라도, 위 코드의 시간 복잡도는 O(n²)가 되는것.
실제로 10,000,000,000 + 300,000에서 300,000이 무슨 의미가 있을까 생각하면 상수 부분이나, 일반 for문이 복잡도에서 제외되는 이유를 짐작할 수 있을것.
