[2018 KAKAO] 다트게임

제출일 : 2020-08-28

문제 풀이 시간 : 30M

---

link : https://programmers.co.kr/learn/courses/30/lessons/17682

문제 설명

카카오톡에 뜬 네 번째 별! 심심할 땐? 카카오톡 게임별~

카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다.
갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다.

1. 다트 게임은 총 3번의 기회로 구성된다.
2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다.
4. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
5. 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고)
6. 스타상(*)의 효과는 다른 스타상(*)의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다. (예제 4번 참고)
7. 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
8. Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
9. 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.

0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.

입력 형식

점수|보너스|[옵션]으로 이루어진 문자열 3세트.
예) 1S2D*3T

• 점수는 0에서 10 사이의 정수이다.
• 보너스는 S, D, T 중 하나이다.
• 옵선은 *이나 # 중 하나이며, 없을 수도 있다.

출력 형식

3번의 기회에서 얻은 점수 합계에 해당하는 정수값을 출력한다.
예) 37

입출력 예제

문제 풀이 접근

입력으로 주어진 문자열을 점수|보너스|[옵션]의 형식으로 쪼개기만 하면 쉽게 문제를 해결할 수 있습니다.

저는 3개의 세트가 입력으로 들어오기 때문에 for문을 이용하여 3번 반복을 하였고 i값을 인덱스로 사용하였습니다.

문제를 풀며 주의해야하는 부분은 점수가 0~10점까지 주어지기 때문에 2개의 자리수가 점수일 경우를 고려해야 합니다.

코드

언어 : JAVA

package Programmers.kakao;
import java.util.Arrays;

public class kakao2018_2_다트게임 {
    public static void main(String[] args) {
        System.out.println(solution("1S2D*3T")); // 37
        System.out.println(solution("1D2S#10S")); // 9
        System.out.println(solution("1D2S0T")); // 3
        System.out.println(solution("1S*2T*3S")); // 23
        System.out.println(solution("1D#2S*3S")); // 5
        System.out.println(solution("1T2D3D#")); // -4
        System.out.println(solution("1D2S3T*")); // 59
    }

    public static int solution(String dartResult) {
        int[] score = new int[3];
        char[] bonus = new char[3];
        char[] option = new char[3];

        int i = 0;
        for (int k = 0; k < 3; k++) {
            // 각 기회마다 얻을 수 있는 점수는 0~10
            score[k] = dartResult.charAt(i++) - '0';
            if (dartResult.charAt(i) == '0') {
                score[k] *= 10;
                i++;
            }

            // 보너스는 SDT 중 하나
            bonus[k] = dartResult.charAt(i++);

            // 옵선은 *이나 # 중 하나이며, 없을 수도 있다.
            if (i < dartResult.length() && (dartResult.charAt(i) == '*' || dartResult.charAt(i) == '#')) {
                option[k] = dartResult.charAt(i++);
            }
        }

        for (int k = 0; k < 3; k++) {
            if (bonus[k] == 'D')
                score[k] = score[k] * score[k];
            else if (bonus[k] == 'T')
                score[k] = score[k] * score[k] * score[k];

            if (option[k] == '*') {
                score[k] *= 2;
                if (k > 0)
                    score[k - 1] *= 2;
            } else if (option[k] == '#') {
                score[k] *= -1;
            }
        }
        return score[0] + score[1] + score[2];
    }
}

[2018 KAKAO] 비밀지도

제출일 : 2020-08-28

문제 풀이 시간 : 30M

---

link : https://programmers.co.kr/learn/courses/30/lessons/17681

문제 설명

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ) 또는벽(#") 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도 1과 지도 2라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
3. 지도 1과 지도 2는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

입력 형식

입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.

• 1 ≦ n ≦ 16
• arr1, arr2는 길이 n인 정수 배열로 주어진다.
• 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다.

출력 형식

원래의 비밀지도를 해독하여 '#', 공백으로 구성된 문자열 배열로 출력하라.

입출력 예제

문제 풀이 접근

주어진 배열을 비트연산하고 값을 2진수로 변환하여 1을 #으로 0을 공백으로 변환하여 값을 리턴하여 문제를 해결하였습니다.

반환해야 하는 String 배열을 생성하고 입력받은 배열을 OR(|)연산을 수행한 후에 Integer.toBinaryString()를 이용아여 2진수 형식으로 바꾸어 주었습니다. 또 변환된 값의 길이가 n보다 작을 수 있기 때문에 String.format()를 이용하여 자리수를 고정하고 replaceAll()을 이용하여 문자를 치환하여 문제를 해결하였습니다.

비트연산으로 문제를 해결해야 한다는 접근은 어렵지 않았으나 Integer.toBinaryString()과 String.fomat(), replaceAll()등 사용빈도가 적은 함수들을 사용해 보았다면 더욱 쉽게 문제를 해결할 수 있을 것이라 생각합니다.

코드

언어 : JAVA

package Programmers.kakao;
import java.util.Arrays;

public class kakao2018_1_비밀지도 {
    public static void main(String[] args) {
        System.out.println(
                Arrays.toString(solution(5, new int[] { 9, 20, 28, 18, 11 }, new int[] { 30, 1, 21, 17, 28 })));
        System.out.println(Arrays
                .toString(solution(6, new int[] { 46, 33, 33, 22, 31, 50 }, new int[] { 27, 56, 19, 14, 14, 10 })));
    }

    public static String[] solution(int n, int[] arr1, int[] arr2) {
        String[] result = new String[n];
        for (int i = 0; i < n; i++) {
            result[i] = Integer.toBinaryString(arr1[i] | arr2[i]);
        }

        for (int i = 0; i < n; i++) {
            result[i] = String.format("%" + n + "s", result[i]);
            result[i] = result[i].replaceAll("1", "#");
            result[i] = result[i].replaceAll("0", " ");
        }

        return result;
    }
}

키패드 누르기

제출일 : 2020-07-27

문제 풀이 시간 : 30M

---

:link: 문제 link

문제 설명

스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.

이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.

1. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
2. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
3. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
4. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
   4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• numbers 배열의 크기는 1 이상 1,000 이하입니다.

• numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.

• hand는

  "left"

또는

  "right"

입니다.

• "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.

• 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.

입출력 예

입출력 예에 대한 설명

입출력 예 #1

순서대로 눌러야 할 번호가 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5]이고, 오른손잡이입니다.

따라서 "LRLLLRLLRRL"를 return 합니다.

입출력 예 #2

왼손잡이가 [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2]를 순서대로 누르면 사용한 손은 "LRLLRRLLLRR"이 됩니다.

입출력 예 #3

오른손잡이가 [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]를 순서대로 누르면 사용한 손은 "LLRLLRLLRL"이 됩니다.

문제 풀이 접근

배열을 정렬하는 방법을 재정의 하여 문제를 해결하였다.

만약 3과 30이란 값이 들어오게 된다면

3+30과 30+3을 비교하여 정렬하게 되는데 이때는 330이 303보다 크기 때문에 3은 30 보다 큰 수가 되는 것이다. 값을 내름차순으로 정렬하여 앞에서 부터 문자열을 이어 붙여주면 정답이 된다.

문제 풀이 접근

문제에서 주어진 조건을 읽고 로직을 구현하는 문제로 처음 왼쪽과 오른쪽 손의 위치가 주어지고 위치에서

1. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
2. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
3. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
   4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

좌표의 위치를 Point배열을 이용하여 저장하고 가운데 2,5,8,0의 숫자를 입력할때 Math.abs(R.x - nums[num].x) + Math.abs(R.y - nums[num].y); 와 같이 거리를 구하고 가까운쪽의 손가락으로 누르게 된다. 만약 갚이 같다면 주어진hand의 손으로 누르게 되며

이를 StringBuilder에 추가해 결과를 출력하였습니다.

코드

언어 : JAVA

package Programmers;

import java.awt.Point;

public class Kakao2020_키패드누르기 {
    public static void main(String[] args) {
        System.out.println(solution(new int[] { 1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5 }, "right"));
        System.out.println(solution(new int[] { 7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2 }, "left"));
        System.out.println(solution(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }, "right"));
    }

    private static String solution(int[] numbers, String hand) {
        Point[] nums = new Point[10];
        nums[0] = new Point(3, 1);
        nums[1] = new Point(0, 0);
        nums[2] = new Point(0, 1);
        nums[3] = new Point(0, 2);
        nums[4] = new Point(1, 0);
        nums[5] = new Point(1, 1);
        nums[6] = new Point(1, 2);
        nums[7] = new Point(2, 0);
        nums[8] = new Point(2, 1);
        nums[9] = new Point(2, 2);
        Point L = new Point(3, 0);
        Point R = new Point(3, 2);

        StringBuilder sb = new StringBuilder();
        for (int num : numbers) {
            if (num == 1 || num == 4 || num == 7) {
                L.x = nums[num].x;
                L.y = nums[num].y;
                sb.append("L");
            } else if (num == 3 || num == 6 || num == 9) {
                R.x = nums[num].x;
                R.y = nums[num].y;
                sb.append("R");
            } else {
                int disL = Math.abs(L.x - nums[num].x) + Math.abs(L.y - nums[num].y);
                int disR = Math.abs(R.x - nums[num].x) + Math.abs(R.y - nums[num].y);
                if (disL == disR) {
                    if (hand.equals("right")) {
                        R.x = nums[num].x;
                        R.y = nums[num].y;
                        sb.append("R");
                    } else {
                        L.x = nums[num].x;
                        L.y = nums[num].y;
                        sb.append("L");
                    }
                } else {
                    System.out.println(disL + " " + disR);
                    if (disR < disL) {
                        R.x = nums[num].x;
                        R.y = nums[num].y;
                        sb.append("R");
                    } else {
                        L.x = nums[num].x;
                        L.y = nums[num].y;
                        sb.append("L");
                    }
                }
            }
        }
        return sb.toString();
    }
}

기수정렬(Ridix Sort)

개념

Radix Sort란 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 기수 정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다.

로직

1. 데이터 중 가장 큰 자리수를 구합니다.
2. 가장 작은 자리수부터 가장 큰 자리수까지 해당 자리수만을 보고 Conting Sort를 진행합니다.

위 GIF 이미지는 Queue를 사용한 방식을 더 잘 표현하는 것 같다.

코드

RadixSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class RadixSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        radixSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void radixSort(int[] arr) {
        // 최대값 구하기
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i])
                max = arr[i];
        }

        // Counting Sort를 사용하여 해당 자리 정렬하기.
        for (int digit = 1; digit <= max; digit *= 10) {
            countingSort(arr, digit);
        }
    }

    private static void countingSort(int[] arr, int digit) {
        int[] temp = new int[N]; // 임시로 사용할 공간
        int[] counting = new int[10]; // 카운팅 배열

        for (int i = 0; i < N; i++) {
            int num = (arr[i] / digit) % 10; // 해당 자리수의 숫자 추출
            counting[num]++;
        }

        // 누적합 배열로 만들기
        for (int i = 1; i < counting.length; i++) {
            counting[i] += counting[i - 1];
        }

        // 뒤에서 부터 시작 >> 값이 큰것이 뒤로 가야하기 때문
        for (int i = 0; i < N; i++) {
            int num = (arr[i] / digit) % 10;
            int index = counting[num];

            temp[index - 1] = arr[i];
            counting[num]--;
        }

        // 복사
        for (int i = 0; i < N; i++) {
            arr[i] = temp[i];
        }
    }

}

console

정렬 전: [40, 58, 27, 29, 95, 33, 76, 93, 39, 36]
정렬 후: [29, 27, 39, 36, 33, 40, 58, 76, 95, 93]

시간복잡도

배열에서 가장 큰 자리수의 값만큼 Counting Sort를 수행한다. 만약 배열의 최대 원소의 값이 1350이라면 총 4번을 수행하게 됩니다.

한번의 Counting Sort는 $O(n+k)$의 시간복잡도를 같으며 $k=10$으로 $O(n)$으로 표현이 가능합니다.

따라서 정렬할 숫자의 자릿수를 $d$라고 하면 시간 복잡도는 $O(dn)$으로 표현 할 수 있습니다.

기수 정렬은 비교 연산을 하지 않으며, 무엇보다도 전체 시간 복잡도 역시 $O(dn)$이어서, 정수와 같은 자료의 정렬 속도가 매우 빠릅니다.

데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 가능할 때에는 매우 좋은 알고리즘이다.

장점

1. 자리수를 비교해 정렬하기때문에 문자열도 정렬이 가능하다.
2. $O(dn)$의 빠른시간으로 정렬이 가능
3. 안정 정렬 이다.

단점

1. 자릿수가 없는 것은 정렬이 불가능 하다.
2. 추가적인 메모리 공간이 필요하다.

계수정렬(Counting Sort)

개념

Counting Sort는 숫자들간 비교를 하지 않고 정렬을 하는 알고리즘이다. 각 숫자가 몇개 있는지 개수를 세어 저장한 후에 정렬하는 방식이다.

로직

1. 정렬하고자 하는 배열의 최대값을 구한다.
2. 최대값 크기의 배열에 각 원소를 순회하며 해당 값이 몇개인지 저장한다.
3. 저장된 데이터를 순서대로 출력한다.

코드

CountingSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class CountingSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        countingSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void countingSort(int[] arr) {
        // 최대값 구하기
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i])
                max = arr[i];
        }

        int[] counting = new int[max + 1]; // 카운팅 배열

        for (int i = 0; i < N; i++) {
            counting[arr[i]]++;
        }

        int index = 0;
        for (int i = 0; i < counting.length; i++) {
            while (counting[i]-- > 0) {
                arr[index++] = i;
            }
        }
    }
}

console

정렬 전: [71, 89, 39, 93, 92, 27, 19, 15, 74, 76]
정렬 후: [15, 19, 27, 39, 71, 74, 76, 89, 92, 93]

시간복잡도

$O(N+K)$ : 이때, $K$는 배열의 최대값이다.

장점

1. $O(N)$의 매우 빠른 속도로 정렬이 가능하다.

단점

1. 음수나 실수는 정렬할 수 없다.
2. 추가적인 메모리 공간이 필요하며 값의 분포의 따라 메모리 낭비가 심할 수 있다.

힙 정렬(Heap Sort)

개념

Heap Sort는 Heap를 이용한 정렬 방법입니다.

Heap

Heap는 최대값 또는 최소값을 빠르게 찾기 위해 고안된 완전이진트리를 기본으로한 자료구조입니다.

Heap의 종류로 최대힙과 최소힙이 있습니다.

최대힙이라면 부모노트의 키값보다 자식노드의 키값이 작다는 특징이 있습니다.

로직

최대 힙이나 최소 힙을 구성하여 정렬을 하는 방법

1. 정렬해야 할 n개의 데이터를 최대 힙또는 최소힙으로 구성
2. 힙의 root노드에서 값을 순서대로 추출한다.
   • root노드의 값을 heap을 구성하는 마지막 노드와 교환한뒤 힙의 크기를 1만큼 줄이는 방식

코드

HeapSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class HeapSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void heapSort(int[] arr) {
        int n = arr.length;

        // maxHeap을 구성
        // n/2-1 : 부모노드의 인덱스를 기준으로 왼쪽(i*2+1) 오른쪽(i*2+2)
        // 즉 자식노드를 갖는 노트의 최대 개수부터
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i); // 일반 배열을 힙으로 구성
        }

        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0); // 요소를 제거한 뒤 다시 최대힙을 구성
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        int p = i;
        int l = i * 2 + 1;
        int r = i * 2 + 2;

        // 왼쪽 자식노드
        if (l < n && arr[p] < arr[l])
            p = l;
        // 오른쪽 자식노드
        if (r < n && arr[p] < arr[r])
            p = r;

        // 부모노드 < 자식노드
        if (i != p) {
            swap(arr, p, i);
            heapify(arr, n, p);
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

console

정렬 전: [65, 83, 96, 81, 38, 48, 29, 45, 89, 51]
정렬 후: [29, 38, 45, 48, 51, 65, 81, 83, 89, 96]

시간복잡도

힙생성(heapify) 알고리즘의 시간 복잡도는 $O(logN)$

장점

1. 추가적인 메모리를 필요로 하지 않으면서 항상 $O(NlogN)$으로 빠른 편이다.

단점

1. 불안정 정렬이다.

병합정렬(Merge sort)

개념

정렬할 배열을 반으로 나누어 좌측과 우측 배열을 계속하여 분할해 나간 후 각 배열내에서 정렬 후 병합하는 과정을 통해 정렬하는 알고리즘입니다.

분할 정복

큰 문제를 작은 문제 단위로 쪼개면서 해결해 나가는 방식

로직

데이터의 크기를 계속 반으로 나누고 이를 정렬하면서 다시 합치는 방법

Merge Sort는 배열의 길이가 1이하이면 이미 정렬된 것으로 본다.

정렬되지 않은 경우에

1. 분할(Divide) : 배열을 반으로 나눈다.
2. 정복(conquer) : 나누어진 배열이 여전히 분할이 가능하다면 분할을 수행한다. 그렇지 않으면 결합하여 정렬을 수행한다.
3. 결합 (combine): 두 부분의 배열을 다시 하나의 정렬된 리스트로 병합한다. 이때 결과는 임시배열에 저장된다.
4. 복사(copy) : 임시배열에 저장된 결과를 원래 배열에 복사한다.

와 같은 과정을 통해 정렬한다.

코드

MergeSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class MergeSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        mergeSort(0, N - 1, arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    // divide
    private static void mergeSort(int start, int end, int[] arr) {
        if (start >= end)
            return;

        int mid = (start + end) / 2;
        mergeSort(start, mid, arr); // left
        mergeSort(mid + 1, end, arr); // right

        merge(start, mid, end, arr);
    }

    // conquer
    private static void merge(int start, int mid, int end, int[] arr) {
        int[] temp = new int[end - start + 1];
        int i = start, j = mid + 1, k = 0;

        // combine
        while (i <= mid && j <= end) {
            if (arr[i] < arr[j])
                temp[k++] = arr[i++];
            else
                temp[k++] = arr[j++];
        }
        while (i <= mid)
            temp[k++] = arr[i++];
        while (j <= end)
            temp[k++] = arr[j++];

        // copy
        while (k-- > 0)
            arr[start + k] = temp[k];
    }
}

console

정렬 전: [1, 48, 3, 51, 19, 17, 38, 64, 72, 69]
정렬 후: [1, 3, 17, 19, 38, 48, 51, 64, 69, 72]

시간복잡도

분할하는 과정에서 $O(logN)$의 시간이 병합하는 과정에서 $O(N)$의 시간이 소요된다.

최선 최악 평균 모두 $O(NlogN)$의 시간 복잡도를 갖는다.

장점

1. Quick Sort와 달리 pivot을 설정하는 방법에 따라 성능의 차이가 없이 $O(NlogN)$의 성능을 낸다.
2. 안정 정렬이다.

단점

1. 병합하는 과정에서 데이터의 개수만큼의 추가적인 공간이 필요하다.

퀵정렬(Quick Sort)

개념

분할정복 방식으로 고안된 정렬방법으로 먼저 임의의 기준을 선택하여 그 기준보다 작은 값은 왼쪽에, 큰 값을 오른쪽에 위치시킨 후 다시 임의의 기준을 선택하여 왼쪽과 오른쪽을 반복하여 나누어 가며 정렬하는 방법

재귀호출을 사용

로직

1. 배열에서 임의의 원소 pivot을 선택한다.
2. 남아 있는 원소들은 pivot보다 큰 것과 작은 것의 두 가지로 구분된다.
3. 각 리스트는 다시 스스로를 정렬하는 메소드를 호출한다.

결론적으로 리스트는 pivot에 의해 작은 원소들과 큰 원소들로 정렬된다.

코드

QuickSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        quickSort(0, N - 1, arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void quickSort(int start, int end, int[] arr) {
        if (start >= end)
            return;

        int left = start + 1, right = end;
        int pivot = arr[start];

        while (left <= right) {
            while (left <= end && arr[left] <= pivot)
                left++;
            while (right > start && arr[right] >= pivot)
                right--;

            if (left <= right) {
                swap(arr, left, right);
            } else {
                swap(arr, start, right);
            }
        }
        quickSort(start, right - 1, arr);
        quickSort(right + 1, end, arr);
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

console

정렬 전: [34, 1, 6, 10, 42, 24, 0, 30, 10, 78]
정렬 후: [0, 1, 6, 10, 10, 24, 30, 34, 42, 78]

시간복잡도

원소들은 두 개의 리스트로 분리하는 시간 복잡도는 $O(N)$이고 각각의 재귀 호출은 각 리스트의 숫자의 절반의 횟수가 발생한다. 그래서 이 알고리즘의 시간 복잡도는 $O(NlogN)$이다. 이건 평균적인 성능이다.

최악의 경우에는 $O(N^2)$이다.

정렬하고자 하는 배열의 상태와 pivot을 결정하는 방법에 따라 재귀 호출의 횟수가 최대 $N$번이 발생할 수 있기 때문이다.

pivot을 선택하는 방법(난수 분할, 중위값 선택)에 따라 어느정도 개선은 가능하다.

장점

1. 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 $O(NlogN)$를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠릅니다.
2. 정렬을 위한 추가적인 메모리 공간을 필요로 하지 않는다.

단점

1. 불안정 정렬이다.
2. 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 $O(N^2)$의 시간복잡도를 갖는다.