[URECA] Day 16 | 알고리즘

 알고리즘

- 문제를 해결하기 위해 수행해야 하는 절차나 방법

- APS (Algorithm Problem Solving) : 알고리즘 문제 풀이

 

알고리즘의 필요성

예를 들어, 1부터 100까지의 합을 구하는 문제를 생각해 보자

문제를 푸는 방식에 따라 작업량이나 소요시간 등이 달라질 수 있다

 

고려 사항

1) 정확성 : 얼마나 정확하게 동작하는가

2) 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가

3) 메모리 사용량 : 얼마나 적은 메모리를 사용하는가

4) 단순성 : 다른 사람이 이해하기 쉬운가

5) 최적성 : 더 이상 개선할 여지없이 최적화되었는가

 

알고리즘을 표현하는 두 가지 방법

1)의사코드 <- 자기만의 표현방법을 의미! 엉터리 코드란 읎다!

2)순서도

시간복잡도 : 알고리즘의 효율성을 평가하는 지표중 하나

실제 수행 시간이나 실행되는 명령문의 개수를 계산

 

빅오 표기법

- 시간복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시

- 계수(Coefficient)는 생략하여 표시

 

예

Big O 시간 복잡도는 요소 수(n)이 증가함에 따라 다음과 같은 연산수의 증가를 보인다

1은 1

 

시간 복잡도에 따른 n의 가용 범위

시간 복잡도	n의 가용 범위
O(n!)	10
O(2^n)	20~25
O(n^3)	200~300
O(n^2)	3000~5000
O(nlogN)	100만
O(n)	1000만~2000만
O(logN)	10억

 

n에 따른 실제 실행 시간

자료 구조와 APS의 관계

- 정의 : 데이터를 효율적으로 다루는(CRUD) 방법을 정의한 것

- 프로그램의 목적에 따라 활용할 수 있는 자료구조가 다양함 ex) Array, List, Stack, Queue, Tree...

- 효율적인 일고리즘을 구현하기 위해서는 효율적인 자료구조 선택이 필수

 

알고리즘 이론 - 정렬

1) 버블 정렬 (Bubble Sort)

- 인접한 두 개의 원소를 비교한 후 교환하는 과정을 반복하여 데이터를 정렬하는 방식
- 정렬 과정
1> 첫 번째 원소부터 인접한 원소와 비교하여 자리를 교환해가면서 마지막 자리까지 이동한다
2> 기준(오름차순)한 사이클이 끝나면 가장 큰 원소가 마지막 자리로 위치하게 된다
3> 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 한다
- 시간복잡도 : O(n^2)   n이 5000이하일 때 사용하도록 하자

 

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {55,7,78,12,42};
        int n = arr.length;

        for (int i = n - 1; i > 0; i--) { //i값이 j의 비교 기준이 되기 위해 배열length부터 시작해서 0으로 감소하는 반복이 유리하다
            for (int j = 0; j < i; j++) { //현재 행(i)의 끝 열(j)이 i값보다 작을 때 까지만 반복하면 된다
                if (arr[j] > arr[j + 1]) { // 뒤에 있는 숫자보다 내가 크면
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp; // 내가 뒤로 간다
                }
            }
        }

        // Arrays.toString()을 사용하여 출력
        System.out.println(Arrays.toString(arr));
    }
}

 

2. 선택 정렬 (Selection Sort) -> 정말 작은 값부터 세운다.

- 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업
- 정렬 과정 (ex. 주어진 자료들 중 세 번째로 작은 값 찾기)
1> 주어진 자료들 중 최소값을 찾는다
2> 그 값을 리스트의 맨 앞에 위치한 값과 교환한다
3> 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다
- 시간복잡도 : O(n^2)

//주어진 자료들 중 세 번째로 작은 값 찾기
import java.util.Arrays;

public class ThirdSmallestExample {
    public static void main(String[] args) {
        int[] nums = {64, 25, 10, 22, 11}; // 정렬할 배열
        int n = nums.length; // 배열의 길이

        // 선택 정렬을 사용하기 위해
        int[] sortedNums = Arrays.copyOf(nums, n); // 원본 배열을 복사. 나중에 원본배열의 인덱스로 답을 내야 하므로
        for (int i = 0; i < n - 1; i++) {
        //맨 앞을 빼고 돌면되니 n-1
            int minIdx = i; // 현재 인덱스의 값을 최소값으로 가정
            for (int j = i + 1; j < n; j++) { // 그 옆의 값들을 순회하면서
                if (sortedNums[minIdx] > sortedNums[j]) {//가정한 값과 비교해서
                    minIdx = j; // 더 작은 값의 인덱스를 찾음
                }
            }
            // 최소값이 현재 인덱스와 다르면 스와프
            if (minIdx != i) {
                int temp = sortedNums[i];
                sortedNums[i] = sortedNums[minIdx];
                sortedNums[minIdx] = temp;
            }
        } // 이 for문을 마치면 sortedNums 배열은 오름차순 정렬 완성

        
        int thirdSmallest = sortedNums[2];// 세 번째로 작은 수를 찾아서

        // 원본 배열에서 세 번째로 작은 수의 인덱스 찾기
        // 요구사항이 세 번째로 작은 값을 출력하는 게 아니라 세 번째로 작은 값의 인덱스를 원본 배열에서 알아내는 것이므로.
        int indexOfThirdSmallest = -1; // 답이 될 인덱스 초기화 (배열의 인덱스가 될 수 없는 값으로 초기화하는 게 좋음)
        for (int i = 0; i < n; i++) {
            if (nums[i] == thirdSmallest) {//원본 배열을 순회하며 thirdSmallest값을 찾아서
                indexOfThirdSmallest = i; // 찾은 인덱스를 저장
                break; // 찾았다면 그만 돌자
            }
        }

        // 결과 출력
        System.out.println("세 번째로 작은 수: " + thirdSmallest);
        System.out.println("세 번째로 작은 수의 원본 배열 인덱스: " + indexOfThirdSmallest);
    }
}

위와　같은　문제에　자바　ＡＰＩ를　활용한다면？

import java.util.Arrays;
import java.util.HashMap;

public class ThirdSmallestIndexExample {
    public static void main(String[] args) {
        int[] nums = {64, 25, 10, 22, 11}; // 정렬할 배열
        int n = nums.length; // 배열의 길이

        // 원본 배열의 인덱스를 저장할 HashMap
        HashMap<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indexMap.put(nums[i], i); // 값과 인덱스를 저장 ( 배열은 인덱스가 키가 되는데 비해 값을 키로 삼아서 해당 값의 인덱스를 찾으려는 아이디어. 중복값이 없다는 조건이 필요함.)
        }

        // 배열 정렬
        Arrays.sort(nums); //O(nlogn)으로 돌아간다

        // 세 번째로 작은 수
        int thirdSmallest = nums[2];

        // 원본 배열에서 세 번째로 작은 수의 인덱스 찾기
        int indexOfThirdSmallest = indexMap.get(thirdSmallest);

        // 결과 출력
        System.out.println("세 번째로 작은 수: " + thirdSmallest);
        System.out.println("세 번째로 작은 수의 원본 배열 인덱스: " + indexOfThirdSmallest);
    }
}

＝＝＞　선택　정렬은　두　개의　중첩된　루프를　사용하여　모든　요소를　비교하기　때문에　시간복잡도는　Ｏ（ｎ＾２）이지만

두번째　코드는　Ａｒｒａｙｓ．ｓｏｒｔ（）가　ｍｅｒｇｅ　혹은　ｔｉｍ　정렬을　사용하여　Ｏ（ｎｌｏｇn）이므로　두번째　코드의　효율성이　훨씬　좋다．

 

3) 삽입 정렬(Insertion Sort)

- 정렬할　요소를　뒤에　있는　요소와　비교한　뒤　스왑이　일어났다면　앞에　있는　모든　요소와도　비교를　하는　방식
- 정렬 과정 
1> 배열의　첫　번째　요소는　이미　정렬된　상태라고　가정
2> 배열의　두　번째　요소（ｋｅｙ）부터　시작하여　앞　칸의　요소가　더　크면　스왑
3> 이것을　맨　앞　요소까지 반복한다
４＞　２～３번　반복
- 시간목잡도 : O(n^2)

package algo;

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        
        int[] arr = {23, 1, 10, 5, 2}; // 정렬할 배열 초기화

        // 배열의 두 번째 요소부터 시작
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i]; // 현재 비교할 요소(기준)
            int j = i - 1; // 앞쪽 정렬된 부분의 마지막 인덱스

            // key(기준)보다 큰 요소들을 오른쪽으로 이동
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j]; // 요소를 오른쪽으로 이동
                j--;
            }
            arr[j + 1] = key; // key를 적절한 위치에 삽입
        }
        
        System.out.println(Arrays.toString(arr)); 
    }
}

 

4)카운팅 정렬 (Counting Sort)

－　요소가　몇　번씩　등장하는지　세는　방법으로　정렬하는　알고리즘

－　정렬방법

１＞　원본　배열에서　요소가　몇번　등장하는지를　ｃｏｕｎｔｉｎｇ배열이라는　새로운　배열에　저장한다．　이때　원본배열의　요소가　카운팅　배열의　인덱스가　되게　한다．

２＞　카운팅　배열을　가지고　누적합을　계산한다．

３＞　완성된　누적합　배열을　가지고　결과　배열을　생성한다．

－　시간복잡도　：　Ｏ（ｎ）

 

import java.util.Arrays;

public class CountingSortExample {
    public static void main(String[] args) {
        int[] arr = {7, 2, 3, 5, 7, 1, 4, 6, 7, 5, 0, 1};
        int max = 7; // 배열의 최대값
        int[] count = new int[max + 1];
        int[] result = new int[arr.length];

        // 각 숫자의 개수를 세기
        for (int num : arr) {
            count[num]++;
        }

        // 누적합을 구하여 count 배열을 수정하기
        for (int i = 1; i <= max; i++) {
            count[i] += count[i - 1];
        }

        // 결과 배열에 정렬된 값 넣기
        for (int i = arr.length - 1; i >= 0; i--) {
            result[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }

        // 결과 출력
        System.out.println(Arrays.toString(result));
    }
}

시간복잡도가　획기적임에도　많이　쓰이지　않는　이유는？

－　요소의　값이　크면　ｃｏｕｎｔｉｎｇ배열의　크기도　커지므로　메모리　낭비가　심할　수　있음