[Algorithm] WEEK2) Homework

그린·2023년 3월 14일

2023년1학기-알고리즘

목록 보기
2/5

문제

  1. Solve the problems 34 in chapter 1
  2. Apply sorting algorithms to the birthday dataset.

1. Problems 34 in chapter 1

1) 시간 복잡도 추정한 것

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class chap01_34_practice {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        double i = n;
        int l1_complex = 0;
        int l2_complex;
        while (i >= 1) {
            System.out.println("loop1 : " + ++l1_complex);
            l2_complex = 0;
            double j = i;
            while (j <= n) {
                System.out.println("+--loop2 : " + ++l2_complex);
                j = 2 * j;
            }
            i = Math.floor(i / 2);
        }
    }
}

자바 코드로 옮겨 찍어 보았을 때 아래와 같은 결과가 나왔다.

16
loop1 : 1
+--loop2 : 1
loop1 : 2
+--loop2 : 1
+--loop2 : 2
loop1 : 3
+--loop2 : 1
+--loop2 : 2
+--loop2 : 3
loop1 : 4
+--loop2 : 1
+--loop2 : 2
+--loop2 : 3
+--loop2 : 4
loop1 : 5
+--loop2 : 1
+--loop2 : 2
+--loop2 : 3
+--loop2 : 4
+--loop2 : 5

Process finished with exit code 0

Loop1에서는 loop 반복 시 i가 * 1/2 씩 곱해지며 감소한다.

Loop2에서는 loop 반복 시 j가 * 2 씩 곱해지며 증가한다.

따라서 다음과 같이 시간 복잡도를 구할 수 있다.)

1) Loop1

2) Loop2

따라서 T(N) = logN * logN = (logN)^2 = O(logN^2)이라고 생각했다.

2) Solution

정답은 아래와 같다.

결과 O(logN^2)인 것은 같았지만

중간 과정을 내가 잘못 생각한 것 같다.

3) 내 답변과 정답 solution과의 차이점

while문 loop 2개만 생각하지 말고 그 외의 부분도 판단해야 하는 것이라 생각한다.

먼저 (logN)^2 는 while문 2개가 중첩되어 있는 부분을 의미하고,

logN 은 두 번째 while문 안에서 가 (1)의 시간 복잡도가 걸린다고 나와 있지만, 이 두 번째 while문이 총 logN번 반복되므로 logN을 더해주는 것이라 생각한다.

그리고 이 둘을 더한 값을 2로 나눠주는 부분은, floor(i/2) 에서 i가 /2 되어 절반씩 줄어들기 때문에 2를 나눠준다고 생각한다.

(다음주에 내가 생각한 게 맞는지 확인해야 겠다.)

2. Apply sorting algorithms to the birthday dataset

0. csv파일 읽어오기

package week2;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CSVReader {
    public List<List<String>> readCSV() {
        List<List<String>> csvList = new ArrayList<List<String>>();
        File csv = new File("D:\\Github\\Algorithm-2023-01\\practice\\src\\week2\\Algorithms - Birthday Data.csv");
        BufferedReader br = null;
        String line = "";

        try {
            br = new BufferedReader(new FileReader(csv));
            while ((line = br.readLine()) != null) {
                List<String> aLine = new ArrayList<>();
                String[] lineArr = line.split(","); // 파일의 한 줄을 ,로 나누어 배열에 저장 후 리스트로 변환
                aLine = Arrays.asList(lineArr);
                csvList.add(aLine);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            try {
                if (br != null) {
                    br.close();
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        return csvList;
    }
}

1. 버블 정렬

package week2;

import java.util.List;

public class homework2_bubbleSort {
    public static void main(String[] args) {
        CSVReader csvReader = new CSVReader();
        List<List<String>> list = csvReader.readCSV();

        long startTime = System.currentTimeMillis(); // 정렬 시작 시각
        bubbleSort(list, list.size()); // 버블 정렬
        long endTime = System.currentTimeMillis(); // 코드 끝난 시각
        long durationTimeSec = endTime - startTime;

        System.out.println("<버블 정렬>");
        System.out.println("1. 실행 시간 : " + durationTimeSec + "m/s"); // 밀리세컨드 출력

        System.out.println("\n2. 정렬 결과");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i)+"\n");
        }
        System.out.println(sb);
    }

    // a[idx1]과 a[idx2]의 값을 바꾸는 함수
    static void swap(List<List<String>> a, int idx1, int idx2) {
        List<String> t = a.get(idx1);
        a.add(idx1, a.get(idx2));
        a.remove(idx1+1);
        a.add(idx2, t);
        a.remove(idx2 + 1);
    }

    // 버블 정렬
    static void bubbleSort(List<List<String>> a, int n) {
        int k = 0; // a[k]보다 앞쪽은 정렬을 마친 상태
        while (k < n - 1) {
            int last = n - 1; // 마지막으로 요소를 교환한 위치
            for (int j = n - 1; j > k; j--)
                if (Double.parseDouble(a.get(j-1).get(2)) > Double.parseDouble(a.get(j).get(2))) {
                    swap(a, j-1, j);
                    last = j;
                }
            k = last;
        }
    }
}

실행 결과

<버블 정렬>
1. 실행 시간 : 26m/s

2. 정렬 결과
[ㅁㅁㅁ, ******70, 01.01]
[ㅁㅁㅁ, ******05, 01.09]
[ㅁㅁㅁ, ******27, 01.12]
[ㅁㅁㅁ, ******14, 01.14]
[ㅁㅁㅁ, ******43, 01.15]
[ㅁㅁㅁ, ******21, 01.17]
[ㅁㅁㅁ, ******53, 01.19]
[ㅁㅁㅁ, ******51, 01.19]
[ㅁㅁㅁ, ******42, 01.20]
[ㅁㅁㅁ, ******01, 01.20]
[ㅁㅁㅁ, ******05, 01.27]
[ㅁㅁㅁ, ******60, 01.28]
[ㅁㅁㅁ, ******89, 01.30]
[ㅁㅁㅁ, ******14, 02.02]
[ㅁㅁㅁ, ******38, 02.07]
[ㅁㅁㅁ, ******07, 02.07]
...
(생략)

추가로 5번 돌렸을 때의 결과

  1. 26(단위 : m/s) → 위의 결과

  2. 32

  3. 35

  4. 22

  5. 29

평균 실행 시간 : (26 + 32 + 35 + 22 + 29) / 5 = 144 / 5 = 28.8m/s

2. 선택 정렬

package week2;

import java.util.List;

public class homework2_SelectionSort {
    public static void main(String[] args) {
        CSVReader csvReader = new CSVReader();
        List<List<String>> list = csvReader.readCSV();

        long startTime = System.currentTimeMillis(); // 정렬 시작 시각
        selectionSort(list, list.size()); // 선택 정렬
        long endTime = System.currentTimeMillis(); // 코드 끝난 시각
        long durationTimeSec = endTime - startTime;

        System.out.println("<선택 정렬>");
        System.out.println("1. 실행 시간 : " + durationTimeSec + "m/s"); // 밀리세컨드 출력

        System.out.println("\n2. 정렬 결과");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i)+"\n");
        }
        System.out.println(sb);
    }

    // a[idx1]과 a[idx2]의 값을 바꾸는 함수
    static void swap(List<List<String>> a, int idx1, int idx2) {
        List<String> t = a.get(idx1);
        a.add(idx1, a.get(idx2));
        a.remove(idx1+1);
        a.add(idx2, t);
        a.remove(idx2 + 1);
    }

    // 선택 정렬
    static void selectionSort(List<List<String>> a, int n) {
        for (int i = 0; i < n - 1; i++) {
            int min = i;      // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 기록
            for (int j = i + 1; j < n; j++)
                if (Double.parseDouble(a.get(j).get(2)) < Double.parseDouble(a.get(min).get(2)))
                    min = j;
            swap(a, i, min);  // 아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환
        }
    }
}

실행 결과

<선택 정렬>
1. 실행 시간 : 22m/s

2. 정렬 결과
[ㅁㅁㅁ, ******70, 01.01]
[ㅁㅁㅁ, ******05, 01.09]
[ㅁㅁㅁ, ******27, 01.12]
[ㅁㅁㅁ, ******14, 01.14]
[ㅁㅁㅁ, ******43, 01.15]
[ㅁㅁㅁ, ******21, 01.17]
[ㅁㅁㅁ, ******53, 01.19]
[ㅁㅁㅁ, ******51, 01.19]
[ㅁㅁㅁ, ******42, 01.20]
[ㅁㅁㅁ, ******01, 01.20]
[ㅁㅁㅁ, ******05, 01.27]
[ㅁㅁㅁ, ******60, 01.28]
[ㅁㅁㅁ, ******89, 01.30]
[ㅁㅁㅁ, ******14, 02.02]
[ㅁㅁㅁ, ******38, 02.07]
[ㅁㅁㅁ, ******07, 02.07]
...
(생략)

추가로 5번 돌렸을 때의 결과

  1. 22(단위 : m/s) → 위의 결과

  2. 28

  3. 23

  4. 24

  5. 27

평균 실행 시간 : (22 + 28 + 23 + 24 + 27) / 5 = 124 / 5 = 24.8m/s

3. 삽입 정렬

package week2;

import java.util.List;

public class homework2_InsertionSort {
    public static void main(String[] args) {
        CSVReader csvReader = new CSVReader();
        List<List<String>> list = csvReader.readCSV();

        long startTime = System.currentTimeMillis(); // 정렬 시작 시각
        insertionSort(list, list.size()); // 삽입 정렬
        long endTime = System.currentTimeMillis(); // 코드 끝난 시각
        long durationTimeSec = endTime - startTime;

        System.out.println("<삽입 정렬>");
        System.out.println("1. 실행 시간 : " + durationTimeSec + "m/s"); // 밀리세컨드 출력

        System.out.println("\n2. 정렬 결과");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i)+"\n");
        }
        System.out.println(sb);
    }

    // 삽입 정렬
    static void insertionSort(List<List<String>> a, int n) {
        for (int i = 1; i < n; i++) {
            int j = i;
            List<String> tmp = a.remove(i);
            while (j > 0 && Double.parseDouble(a.get(j-1).get(2)) > Double.parseDouble(tmp.get(2)))
                j--;

            a.add(j, tmp);
        }
    }
}

실행 결과

<삽입 정렬>
1. 실행 시간 : 18m/s

2. 정렬 결과
[ㅁㅁㅁ, ******70, 01.01]
[ㅁㅁㅁ, ******05, 01.09]
[ㅁㅁㅁ, ******27, 01.12]
[ㅁㅁㅁ, ******14, 01.14]
[ㅁㅁㅁ, ******43, 01.15]
[ㅁㅁㅁ, ******21, 01.17]
[ㅁㅁㅁ, ******53, 01.19]
[ㅁㅁㅁ, ******51, 01.19]
[ㅁㅁㅁ, ******42, 01.20]
[ㅁㅁㅁ, ******01, 01.20]
[ㅁㅁㅁ, ******05, 01.27]
[ㅁㅁㅁ, ******60, 01.28]
[ㅁㅁㅁ, ******89, 01.30]
[ㅁㅁㅁ, ******14, 02.02]
[ㅁㅁㅁ, ******38, 02.07]
[ㅁㅁㅁ, ******07, 02.07]
...
(생략)

추가로 5번 돌렸을 때의 결과

  1. 18(단위 : m/s) → 위의 결과

  2. 24

  3. 36

  4. 22

  5. 21

평균 실행 시간 : (18 + 24 + 36 + 22 + 21) / 5 = 121 / 5 = 24.2m/s

4. 퀵 정렬

package week2;

import java.util.List;

public class homework2_QuickSort {
    public static void main(String[] args) {
        CSVReader csvReader = new CSVReader();
        List<List<String>> list = csvReader.readCSV();

        long startTime = System.currentTimeMillis(); // 정렬 시작 시각
        quickSort(list, 0, list.size() - 1); // 퀵 정렬
        long endTime = System.currentTimeMillis(); // 코드 끝난 시각
        long durationTimeSec = endTime - startTime;

        System.out.println("<퀵 정렬>");
        System.out.println("1. 실행 시간 : " + durationTimeSec + "m/s"); // 밀리세컨드 출력

        System.out.println("\n2. 정렬 결과");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i)+"\n");
        }
        System.out.println(sb);
    }

    // a[idx1]과 a[idx2]의 값을 바꾸는 함수
    static void swap(List<List<String>> a, int idx1, int idx2) {
        List<String> t = a.get(idx1);
        a.add(idx1, a.get(idx2));
        a.remove(idx1+1);
        a.add(idx2, t);
        a.remove(idx2 + 1);
    }

    // 퀵 정렬
    static void quickSort(List<List<String>> a, int left, int right) {
        int pl = left;            // 왼쪽 커서
        int pr = right;           // 오른쪽 커서
        List<String> x = a.get((pl + pr) / 2); // 피벗

        do {
            while (Double.parseDouble(a.get(pl).get(2)) < Double.parseDouble(x.get(2))) pl++;
            while (Double.parseDouble(a.get(pr).get(2)) > Double.parseDouble(x.get(2))) pr--;

            if (pl <= pr)
                swap(a, pl++, pr--);
        } while (pl <= pr);

        if (left < pr) quickSort(a, left, pr);
        if (pl < right) quickSort(a, pl, right);
    }
}

실행 결과

<퀵 정렬>
1. 실행 시간 : 6m/s

2. 정렬 결과
[ㅁㅁㅁ, ******70, 01.01]
[ㅁㅁㅁ, ******05, 01.09]
[ㅁㅁㅁ, ******27, 01.12]
[ㅁㅁㅁ, ******14, 01.14]
[ㅁㅁㅁ, ******43, 01.15]
[ㅁㅁㅁ, ******21, 01.17]
[ㅁㅁㅁ, ******53, 01.19]
[ㅁㅁㅁ, ******51, 01.19]
[ㅁㅁㅁ, ******42, 01.20]
[ㅁㅁㅁ, ******01, 01.20]
[ㅁㅁㅁ, ******05, 01.27]
[ㅁㅁㅁ, ******60, 01.28]
[ㅁㅁㅁ, ******89, 01.30]
[ㅁㅁㅁ, ******14, 02.02]
[ㅁㅁㅁ, ******38, 02.07]
[ㅁㅁㅁ, ******07, 02.07]
...
(생략)

추가로 5번 돌렸을 때의 결과

  1. 6(단위 : m/s) → 위의 결과

  2. 7

  3. 7

  4. 9

  5. 8

평균 실행 시간 : (6 + 7 + 7 + 9 + 8) / 5 = 37 / 5 = 7.4m/s

알고리즘 성능 비교

  • 버블 정렬 : 28.8m/s
  • 선택 정렬 : 24.8m/s
  • 삽입 정렬 : 24.2m/s
  • 퀵 정렬 : 7.4m/s

결과

퀵 정렬 : 7.4m/s < 삽입 정렬 : 24.2m/s < 선택 정렬 : 24.8m/s < 버블 정렬 : 28.8m/s

이론적인 시간 복잡도 비교

퀵 정렬 : 최악 - O(N^2) , 평균 - O(NlogN)

삽입 정렬 : 최악 - O(N^2) , 평균 - O(N^2)

선택 정렬 : 최악 - O(N^2) , 평균 - O(N^2)

버블 정렬 : 최악 - O(N^2) , 평균 - O(N^2)

참고 출처

https://yoongrammer.tistory.com/79

https://www.quora.com/Difference-between-log-2-n-log-log-n-and-log-n-2

https://medium.com/humanscape-tech/코드의-시간-복잡도-계산하기-b67dd8625966

https://blog.naver.com/freewheel3/220853009691

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=archslave&logNo=221036748838

https://yabmoons.tistory.com/250

profile
그린
기록하자
이전 포스트

[Algorithm] WEEK1) Birthday Problem

다음 포스트

[Algorithm] WEEK3) Homework

0개의 댓글