[2025 1학기 알고리즘 스터디] 1주차 박건민

벌금을 피하고 싶어서 급하게 작성한 글입니다.

1주차의 주제 정렬 알고리즘!

 

정렬이란 무엇인가...

그래서 정렬 알고리즘에 대해 찾아봣습니다.

 

 

1. 정렬 알고리즘  종류

(1) 선택 정렬 (Selection Sort)

• 설명: 데이터 집합에서 최소값을 찾아 첫 번째 위치와 교환하고, 그 다음 최소값을 찾아 두 번째 위치와 교환하는 방식으로 정렬을 수행합니다. 이러한 과정을 반복하여 전체를 정렬합니다.
• 특징: 구현이 간단하지만, 시간 복잡도가 O(n²)로 비효율적입니다. 안정성을 보장하지 않습니다.

(2) 삽입 정렬 (Insertion Sort)

• 설명: 데이터 집합을 순회하면서 각 요소를 적절한 위치에 삽입하여 정렬을 수행합니다. 이미 정렬된 부분과 비교하여 새로운 요소를 삽입하는 방식입니다.
• 특징: 대부분의 요소가 이미 정렬되어 있는 경우 효율적이며, 최선의 경우 O(n)의 시간 복잡도를 가집니다. 안정성을 보장합니다.

(3) 버블 정렬 (Bubble Sort)

• 설명: 인접한 두 요소를 비교하여 필요에 따라 위치를 교환하며 정렬을 수행합니다. 이러한 과정을 반복하여 가장 큰 값이 맨 끝으로 이동하게 됩니다.
• 특징: 구현이 간단하지만, 시간 복잡도가 O(n²)로 비효율적입니다. 안정성을 보장합니다.

(4) 병합 정렬 (Merge Sort)

• 설명: 분할 정복(divide and conquer) 방식을 사용하여 배열을 반으로 나누고, 각각을 재귀적으로 정렬한 후 병합하여 전체를 정렬합니다.
• 특징: 시간 복잡도가 O(n log n)으로 안정적이며, 안정성을 보장합니다. 그러나 추가적인 메모리 공간이 필요합니다.

(5) 퀵 정렬 (Quick Sort)

• 설명: 피벗(pivot)을 선택하여 이를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 배치하고, 이러한 과정을 재귀적으로 수행하여 정렬합니다.
• 특징: 평균적으로 O(n log n)의 시간 복잡도를 가지며, 추가 메모리 공간이 거의 필요하지 않습니다. 그러나 최악의 경우 O(n²)의 시간 복잡도를 가질 수 있으며, 일반적으로 안정성을 보장하지 않습니다.

(6) 힙 정렬 (Heap Sort)

• 설명: 최대 힙(max heap) 또는 최소 힙(min heap)을 구성하여 최댓값 또는 최솟값을 추출하고, 이를 반복하여 정렬을 수행합니다.
• 특징: 시간 복잡도가 O(n log n)이며, 추가 메모리 공간이 거의 필요하지 않습니다. 그러나 일반적으로 안정성을 보장하지 않습니다.

(7) 계수 정렬 (Counting Sort)

• 설명: 데이터의 범위를 기준으로 각 값의 개수를 세어 정렬을 수행합니다. 주로 데이터의 범위가 제한적인 경우에 사용됩니다.
• 특징: 시간 복잡도가 O(n + k)로 매우 효율적이지만, 데이터의 범위가 클 경우 메모리 사용량이 많아질 수 있습니다. 안정성을 보장합니다.

 

2. 정렬 알고리즘 선택 시 고려사항

 

정렬 알고리즘을 선택할 때는 다음과 같은 요소를 고려해야 합니당

1. 데이터의 크기: 데이터의 양이 많을수록 O(n log n)의 시간 복잡도를 가지는 알고리즘이 유리합니다.
2. 데이터의 정렬 상태: 이미 정렬된 데이터에 가까울 경우 삽입 정렬이 효율적일 수 있습니다.
3. 메모리 사용량: 추가적인 메모리 사용이 제한적인 경우 힙 정렬이나 퀵 정렬이 적합합니다.
4. 안정성: 동일한 키 값을 가진 요소들의 순서를 유지해야 하는 경우 안정적인 정렬 알고리즘을 선택해야 합니다.

 

3. 정렬 알고리즘 실전 적용 예제

이제 위에서 정리한 정렬 개념을 실제 알고리즘 문제에 어떻게 적용할 수 있는지 3개의 문제를 통해 알아보자~

• 좌표 압축: 정렬을 통해 상대적인 위치(순위)를 계산하는 문제
• 카드: Map과 정렬을 조합하여 가장 빈도 높은 값을 찾는 문제
• 수 정렬하기 3: 계수 정렬을 활용해 메모리와 시간을 모두 절약하는 정렬 최적화 문제

 

(1) 좌표 압축

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        /*
        입력이 많을 때 Scanner는 매우 느림
        내부적으로 정규표현식을 사용해서 속도가 느리고
        많은 양의 입력을 처리할 때 시간 초과가 날 수 있음
        그래서 BufferedReader를 사용함
        BufferedReader는 입력을 버퍼에 쌓아서 한 번에 처리하기 때문에 매우 빠름
        */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] a = new int[n];
        int[] b = new int[n];

        /*
        BufferedReader는 한 줄 전체를 문자열로 받기 때문에
        공백으로 구분된 숫자들을 나누려면 별도의 처리가 필요함
        StringTokenizer는 split()보다 속도도 빠르고 메모리 사용도 적음
        대량의 숫자를 처리할 때 StringTokenizer가 효율적임
        */
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
            b[i] = a[i];
        }

        /*
        좌표 압축을 하기 위해 정렬을 사용함
        정렬된 배열에서 중복을 제거하고 그 값을 기준으로 인덱스를 부여함
        */
        Arrays.sort(b);

        /*
        Map을 사용해서 각 숫자에 대해 압축된 인덱스를 저장함
        중복된 숫자는 한 번만 처리하도록 containsKey로 체크함
        */
        Map<Integer, Integer> m = new HashMap<>();
        int idx = 0;
        for (int x : b) {
            if (!m.containsKey(x)) {
                m.put(x, idx++);
            }
        }

        /*
        출력도 Scanner처럼 반복적으로 System.out.print를 쓰면 매우 느림
        StringBuilder를 사용해서 결과를 모두 문자열로 만들어 놓고
        마지막에 한 번만 출력하면 성능이 훨씬 좋아짐
        */
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(m.get(a[i])).append(" ");
        }

        System.out.println(sb.toString().trim());
    }
}

 

이 문제는 정수들이 주어졌을 때 각각의 수를 정렬했을 때의 상대적인 위치(0부터 시작하는 순서)로 바꾸는 문제다.

예를 들어 [1000, 999, 1000, 1001]이 주어졌다면 이를 압축하면 [1, 0, 1, 2]가 되어야 한다.

중복된 값은 같은 순위로 처리되기 때문에 중복 제거가 핵심!

 

처음엔 단순히 정렬만 하면 되는 줄 알았는데 문제는 값의 상대적인 순위를 출력하는 거라 단순 정렬로는 해결이 되지 않았다.

그래서 다음과 같은 흐름으로 접근했다.

1. 원본 배열을 복사해서 정렬한다.
2. 정렬된 배열에서 중복을 제거하고, 각 값을 몇 번째인지 Map에 저장한다.
3. 원래 배열에서 각 값을 Map에서 찾아서 순위(압축된 값)를 출력한다.

Map을 사용한 이유는 빠르게 특정 값의 순위를 찾아야 했기 때문

 

주의했던 점

• 입력이 많기 때문에 입출력을 반드시 최적화해야 했다. Scanner와 print를 사용하면 시간 초과가 났다.
• 중복을 제거하지 않으면 동일한 값이 다른 순위를 갖게 돼 정답이 틀릴 수 있다.
• 출력은 반드시 입력 순서를 유지해야 하므로 Map에 저장한 뒤 원래 배열 순서대로 출력해야 했다.

 

 

(2) 카드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 빠른 입력 처리 (Scanner는 느리므로 BufferedReader 사용)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Map<Long, Integer> m = new HashMap<>();

        // 숫자 카드의 범위가 2^62보다 작다 했으므로 long 타입 사용
        for (int i = 0; i < n; i++) {
            long x = Long.parseLong(br.readLine());
            m.put(x, m.getOrDefault(x, 0) + 1);
        }

        /*
        Map의 keySet을 list로 변환 후 정렬하는 이유
        1. 가장 많이 나온 숫자를 찾아야 함
        2. 동점인 경우 작은 수를 출력해야 함
        그래서 정렬을 먼저 하면 가장 작은 수부터 탐색 가능
        이후 count가 가장 큰 것을 찾아내면, 자동으로 조건을 만족함

        sort를 먼저 하면 동일 빈도면 작은 수라는 조건을 손쉽게 처리 가능
        */
        List<Long> keyList = new ArrayList<>(m.keySet());
        Collections.sort(keyList); // 오름차순 정렬 (기본)

        long ans = 0;
        int max = 0;

        for (long k : keyList) {
            int cnt = m.get(k);
            if (cnt > max) {
                max = cnt;
                ans = k;
            }
            // cnt == max 인 경우는 무시, 이미 정렬되어 있어서 작은 수가 먼저 나옴
        }

        System.out.println(ans);
    }
}

 

이 문제는 입력된 숫자 카드 중 가장 많이 나온 숫자를 찾는 문제다.

단, 같은 횟수로 나온 숫자가 여러 개일 경우에는 더 작은 숫자를 출력해야 한다.

 

처음엔 배열을 정렬하고 앞에서부터 빈도를 세는 방식으로 접근했지만 동점 처리와 속도 면에서 만족스럽지 않았다.

그래서 다음과 같이 바꿨다.

1. Map을 사용해 숫자별 등장 횟수를 저장한다.
2. keySet을 리스트로 만들어 정렬한다. (정렬하면 작은 수가 앞에 오게 됨)
3. 리스트를 순회하면서 가장 빈도 높은 숫자를 찾는다. 동점일 경우 첫 번째 나온 수를 유지하면 조건을 만족하게 된다.

주의했던 점

• 수의 범위가 매우 크므로 int가 아닌 long을 사용해야 했다.
• 동점 처리에서 정렬을 하지 않으면, 더 큰 수가 출력될 수 있기 때문에 반드시 key 정렬이 필요하다.
• 역시 입력 수가 많기 때문에 입출력 최적화가 필수였다.

 

 

 

(3) 수 정렬하기 3

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        //Scanner 쓰면 시간 초과
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        // 숫자의 최대 범위가 10,000 미만이므로 배열로 카운트 가능
        // 각 숫자가 몇 번 나왔는지 배열에 저장
        int[] cnt = new int[10001];

        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(br.readLine());
            cnt[x]++;
        }

        //StringBuilder로 문자열 한 번에 출력
        StringBuilder sb = new StringBuilder();

        /*
        등장한 숫자를 오름차순으로 탐색하면서 그 수가 몇 번 나왔는지를 기반으로 출력
        시간복잡도는 O(N + K), 여기서는 거의 O(N)으로 동작
        */
        for (int i = 1; i < 10001; i++) {
            while (cnt[i]-- > 0) {
                sb.append(i).append('\n');
            }
        }

        System.out.print(sb);
    }
}

 

이 문제는 단순한 오름차순 정렬 문제인데 입력 수가 무려 1,000만 개까지 주어질 수 있다는 점이 핵심

일반적인 정렬 알고리즘을 사용하면 시간 초과가 발생할 수밖에 없는 상황

 

문제의 조건을 유심히 보니 값의 범위가 1 이상 10,000 미만이었다.

값의 종류는 적지만 개수는 매우 많다는 특성이 있어서 계수 정렬 방식으로 접근했다.

1. 값의 개수를 저장할 배열을 선언한다. (크기는 10001)
2. 입력으로 받은 숫자들의 개수를 배열에 기록한다.
3. 배열을 순회하면서 등장한 횟수만큼 해당 숫자를 출력한다.

주의했던 점

• Scanner나 System.out.println()을 사용하면 절대 시간 안에 못 끝난다. BufferedReader와 StringBuilder는 필수다.
• 배열 크기를 실수하지 않도록 값의 최대값 + 1까지 선언해야 한다.
• 계수 정렬은 값의 범위가 크면 쓸 수 없지만, 이 문제처럼 범위가 작을 땐 최고의 선택이다.

 

4. 후기

아 집가고싶다.