알고리즘 공부 1 Weekly

저의 스터디 선생님과 하는 추가적인 기본 공부입니다.
다른 블로그나 정의 개념 등을 찾아 공부하고, 읽어보고 난 후 제 생각으로 적는 내용입니다.
정확하지 않을 수 있으니 참고만 부탁드립니다!

 

 

<  1.  알고리즘의 기본 개념  >

1) 알고리즘이란?

알고리즘이란, 제가 처음에 생각하기에는 문제를 풀어나가는 해설..? 메서드를 사용하는 순서를 배우는 공부 정도로 이해했습니다.

 

찾아보니 알고리즘이란 제 처음 생각과 야아아악간 비슷하게?

' 문제를 풀어나가기위한 풀이과정이며, 즉 문제 해결 방법이라고 한다. '

 

수학 좀 하면 할 수 있을 것이다. 라는 말을 이해를 못 했었는데, 
문제를 풀다보면, 수학적인 그래프나 정렬, 행렬, 연산 등이 필요할 경우가 많았다.

문제이해 자체가 어려운 경우도 많았다.

 

알고리즘이라는 말이 '문제 해결 방법'으로 보면 된다고 했는데, 
알고리즘을 공부하면서 풀고나서 '됐다!!' 가 아닌 '다른 좋은 풀이 방법이 있는가?' 하고 코드를 다시 풀어보고 하는 과정이 필요하다.

가장 효율적이고 깔끔하게 코드 작동 시간이 짧게 한 좋은 방법을 찾아가는 공부같다.

 

2) 시간 복잡도와 공간 복잡도 개념 소개

시간 복잡도 말그대로 시간이 얼마나 걸리는지의 의미입니다.

 

표기법으로는 

💫 O(1) - 상수 시간
     입력 크기(n)에 상관없이 일정한 연산을 수행하면 시간복잡도는 O(1)입니다.

 

     

💫 O(logN) - 로그 시간

      입력 크기(N)이 커질 때 연산 횟수가 logN에 비례해서 증가하면 시간 복잡도는 O(logN)입니다.

 

      for(i=1; i<=n; i*2) { ... }

      위 알고리즘은 i 값이 반복할 때마다 2배씩 증가합니다. 
      이것을 k 번 반복했을 때 다음과 같다. 

      k 는 수행 횟수 이기 때문에 시간 복잡도는 T(n) = logN 이다.

 

 

💫 O(n) - 선형 시간

      입력 크기(n)가 커질 때 연산 횟수가 n에 비례해서 증가하면 시간 복잡도는 O(n)입니다.

      연산 횟수가 선형적으로 증가하는 형태

 

      for(i=0; i < n; i++) { ... }

      위 알고리즘은 n만큼 반복문을 수행합니다.
      n에 값에 비례해서 연산수가 선형적으로 증가하기 때문에 시간 복잡도는 T(n) = O(n) 이다.

      

 

💫 O(n²) - 2차 시간

      입력 크기(n)가 커질 때 연산 횟수가 n²에 비례해서 증가하면 시간 복잡도는 O(n²) 입니다.

      for(i=0; i < n; i++) {

            for(j=0, j < n; j++) {

                  ...

            }

      }

      위 알고리즘은 for문이 중첩되어 있기 때문에 n²에 비례해서 연산수가 증가합니다.

      시간 복잡도는 T(n) = O(n²) 이다.

💫 O(2ⁿ) - 2차 시간

      입력 크기가 커질 때 연산수가 2ⁿ에 비례해서 증가하면 시간 복잡도는 O(2ⁿ) 입니다.

      int func (int n){ 

      if(n <=1)returnn;

      return func(n-1) + fun(n-2); }

      위 알고리즘은 피보나치 수를 구하는 알고리즘이다.

      한번 함수를 호출할 때마다 두 번씩 재귀로 함수를 호출하기 때문에 2ⁿ에 비례해서 연산수가 증가한다.

      시간 복잡도는 T(n) = O(2ⁿ) 이다.

 

시간복잡도가 큰 순서로 보면

O(1) < O(logN) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)

알고리즘은 시간 복잡도가 중심적이라고 합니다.

그 프로그래머스에서도 하다보면 runtime error가 뜰경우가 있는데 시간이 오래걸려서 실패하는 거라고 하더군요!...

 

 

공간 복잡도는 뭔소린가 해서 찾아보니까, 문제를 해결하는데 필요한 메모리 사용량을 분석하는 것이라고 합니다.

공간 복잡도는 보조공간과 입력공간을 합친 포괄적인 개념입니다.

보족 공간은 알고리즘이 실행되는 동안 사용하는 임시공간이라, 입력공간을 고려하지않는다.

 

 

 

 

 

<  2.  자료구조 기초  >

배열 ,   연결 리스트 ,  스택  , 큐  소개

공부하면서 찾아보니까, 

위에 있는 배열-연결 리스트-스택-큐 이 네가지는 선형 자료구조라고 하고

비선형 자료구조에는 트리-그래프가 있다고 한다.

 

선형 구조는 자료를 순차적으로 나열 시킨 형태라고 한다.

자료 간의 앞뒤 관계가 1:1로 되어있다고 하고,

 

비선형 구조는 선형 구조의 반대겠죠 ? 제 생각은 그래요!
자료들이 앞뒤 관계가 1:n or n:n 으로 구성되어있다고 합니다.

 

 

✍ 배열 
배열이란, 같은 자료형을 갖는 여러 원소를 하나의 변수이름으로 모아놓은 데이터 집합이다.

배열은 인덱스와 - 원소 값 쌍의 집합이다.

 

배열의 특징은 데이터의 논리적 순서와 저장된 물리적 순서가 동일하다는 것이다.

 

장점으로는 표현이 간편하고, 순서대로 접근이 아닌, 인덱스로 임의 접근이 가능하다는 것이다.

 

단점으로는 순차적으로 나열되기 때문에 삽입-삭제가 동적으로 일어날 경우 배열의 크기를 지정할 수 없어서 저장공간 낭비를 불러일으킬 수 있고, 오버플로를 초래한다고한다.

메모리크기가 정적이다.

데이터 재정렬 방식이 비효율적이다.

** 오버플로 : 컴퓨터 정수 연산 계산 결과가 허용범위를 초과 할때 발생하는 오류이다.

 

✍ 연결 리스트

배열의 문제점을 보완한 형태의 자료구조다.

배열은 물리적, 논리적 순서가 동일하다 했는데,

리스트 같은 경우는 물리적으로는 데이터를 기억장치 어느곳에 저장해도 되지만,

기억장치의 위치에 저장된 데이터 간의 논리적인 순서를 유지해야한다.

 

하나의 데이터를 저장할 때 논리적으로 다음 데이터가 어디에 저장되어 있는지 같이 나타내야한다.

이를 위해 데이터 필드와 링크필드로 이루어진 노드라는 저장 구조를 이용한다고 한다.

 

노드는 참조 시스템으로 작동된다.

데이터를 각 노드에 저장할 때 다음 순서의 자료가 있는 위치를 데이터에 포함시킨다.

이렇게 각 노드들은 서로 연결되어있다.

 

장점으로는 새로운 데이터들의 삽입-삭제가 용이하고 효율적이고, 논리적 순서와 물리적 순서를 반드시 일치시킬 필요가 없고,

메모리 크기가 동적이다.

대용량 데이터 처리에 적합하다.

 

단점으로는 배열보다 메모리 사용량이 많다.

특정 데이터를 찾는데 비효율 적이다. => 배열 같은 경우는 인덱스로 바로 접근이 가능하지만, 

연결 리스트는 첫 번째 데이터를 가진 노드부터 시작해서 원하는 데이터가 있는 노드까지 모든 노드들을 지나쳐와야한다.

 

 

✍ 스택

스택은 선형 리스트의 한쪽에서만 데이터의 삽입과 삭제가 발생하는 자료구조다. 

비커를 생각하면 될것같다. 비커 입구에서만 뺄 수 있고, 추가할 수있는 형태다.

 

스택은 가장 나중에 삽입된 데이터가 가장 먼저 삭제되기 때문에 '후입선출' 리스트라고도 한다.

 

삽입은 push, 삭제는 pop을 사용한다. 

 

장점은 구조가 단순해서 구현이 쉽고, 데이터 저장-읽기 속도가 빠르다.

단점은 데이터 최대 갯수를 미리 정해야한다는 것과 저장공간의 낭비가 생길 수있다.

 

 

✍ 큐

큐는 선형 리스트의 한쪽 끝에서는 삽입만 수행되고 끝에서는 삭제만 수행된다.

길다란 터널이 있는데 들어가는 입구와 나가는 입구가 반대편에 존재한다고 생각하면 쉬울 듯하다.

 

큐는 가장 먼저 삽입된 데이터가 먼저 삭제되므로 '선입선출' 리스트라고도 한다.

 

장점은 데이터의 순서가 중요한 작업에 좋다.

단점은 큐의 크기가 고정되어 있으면 데이터가 가득 찼을 경우 추가적인 삽입이 불가능해진다.

 

 

 

<  3.  기본 정렬 알고리즘  >

선택,  삽입,  버블,  합병,  퀵 정렬 소개

✍ 선택 정렬(Selection Sort)
주어진 데이터들 중 현재 위치에 맞는 데이터를 선택해 위치를 교환하는 정렬 알고리즘이다.

O(n²)의 시간복잡도를 가지고있다.

 

쉽게 생각하면,

가장 앞에 있는 값을 기준으로 배열 내에서 최소값을 찾고,

그 최소값을 가장 앞에 있던 기준으로 삼았던 값이랑 자리를 변경한다.

그리고 두번째 값을 기준으로 배열 내에서 최소값을 찾고,

그 최소값을 두번째 기준으로 잡았던 값과 자리를 변경하는 식이다. 

이런식으로 조금씩 앞으로 기준을 옮기면서 정렬을 해나간다.

 

function selectionSort(arr) {

    let indexMin;

    for (let i = 0; i < arr.length - 1; i++) {

        indexMin = i;

        for (let j = i + 1; j < arr.length; j++) {

            if (arr[j] < arr[indexMin]) {

                indexMin = j;

            }

        }

        [arr[i], arr[indexMin]] = [arr[indexMin], arr[i]];

    }

    return arr;

}

 

위에 코드를 보면,

for문을 돌려 arr의 length만큼 i를 증가시켜라라고 했는데,

indexMin 최소값을 변수에 가장 작은 값을 담아두고, 그 값들을 정렬해 나간다.

 

 

✍ 삽입 정렬(Insertion Sort)

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해서,

자신의 위치를 찾아 삽입하며 정렬을 완성하는 알고리즘이다. 

선택 정렬과 마찬가지로 O(n²)의 시간복잡도를 가지고있다.

 

쉽게 생각하면,

왼쪽에서부터 차례대로 자리를 찾아간다고 생각하면된다.

첫 번째 인덱스는 놔두고, 

두 번째 인덱스를 첫 번째랑 비교해서 크다면 다음 인덱스와 비교하고,

작다면 첫 번째 인덱스를 뒤로 한칸밀고 두번째 인덱스를 첫번째 인덱스 앞으로 삽입합니다. 

 

이런식으로 앞뒤를 비교해서 크다면 넘어가고 작다면 작은 값을 큰값 앞에 삽입하는 식이다.

 

function insertionSort(arr) {

    for (let i = 1; i < arr.length; i++) {

        let currentVal = arr[i];

        let j;

 

        for (j = i - 1; j >= 0 && arr[j] > currentVal; j--) {

            arr[j + 1] = arr[j];

        }

        arr[j + 1] = currentVal;

    }

    return arr;

}

console.log(insertionSort([4, 3, 2, 1, 5, -5, 20, 17]));

 

반복문을 돌려서 j보다 앞쪽의 인덱스값과 비교해서 삽입한다!

✍ 버블 정렬(Bubble Sort)

두 인접한 원소를 검사하여 정렬하는 방법이다.

=>(뭔가 삽입과 비슷하지요 ??)But 이거는 앞뒤를 확인해서 자리를 교체하는 방법이다.

속도가 빠르지는 않지만, 코드가 단순해서 많이 사용한다고 한다.

성능이 가장 안좋은 편에 속한다 ...

 

 

쉽게 생각해보자 이것도 ..!
첫 번째 인덱스랑 두 번째 인덱스랑 크기를 비교해서 두번째 인덱스가 작다면 첫번째 인덱스와 자리를 변경하고,

크다면 그대로 자리를 유지한다.

그리고나서 두번째 인덱스와 세번째 인덱스도 크기를 비교해서 세번째 인덱스가 작다면 두번째 인덱스와 자리를 변경하고,

크다면 그대로 자리를 유지한다.

이런식으로 맨 끝에까지 비교를하고 다시 처음부터 비교를 시작한다.

그러면서 처음 회전 때 가장 큰 자료가 맨끝으로 이동하게 되는데,
두번째 회전 부터는 맨끝의 자료는 비교하지않고 그대로 놔둔다. (어차피~! 맨뒤에 값은 제일 큰 값일테니!)
그리고나서 세번째 회전에서는 맨뒤에서 두번째 자료까지 놔두고~ 이런식으로 뒤에서부터 정렬을 시작한다고 생각하면 된다.

 

function bubbleSort(array) {

    let temp;

    for (let i = 0; i < array.length - 1; i++) {

        for (let j = 0; j < array.length - 1 - i; j++) {

            if (array[j] > array[j + 1]) {

                temp = array[j];

                array[j] = array[j + 1];

                array[j + 1] = temp;

            }

        }

    }

    return array;

}

console.log(bubbleSort([5, 4, 3, 2, 1]));

 

위에 코드를 봤을 때 반복문을 돌려 변수에 array[i]를 남아서 그 다음에 있는 인덱스와 비교하는 코드를 작성하고,

비교한 후 교체하던지 유지하던지 한 다음 인덱스를 다시 변수에 담아준다.

이렇게 앞뒤를 확인하면서 교체하는 작업을 하다보니 성능이 가장 안좋게될수밖에없당..

 

 

✍ 합병 정렬(병합 정렬, Merge Sort)

주어진 배열의 크기가 1이 될 때 까지 쪼갠 후 작은 단위부터 정렬하여 정렬된 단위들을 계속 병합해 가며 정렬하는 방법이다.

 

쉽게 생각!
배열이 주어지면,

1. 일단 배열을 더이상 쪼개지지않을 작은 단위 하나씩 쪼갠다.

2. 쪼갠 배열들을 두개씩 합치는데, 합칠때 두개중에 작은것을 앞으로 큰것을 뒤로가게끔해서 정렬을 맞추면서 합친다.

3. 두개씩 배열이 나눠져있는데, 이젠 네개씩 합쳐준다.

    이때도 두개씩있는 정렬 두개중 첫번째 인자들을 비교해서 그중 작은 인자를 앞에두고, 두번째 인자들 중 작은것을 앞으로가게 해서
    길이가 4인 정렬로 만든다.

4. 길이가 4인 정렬들 2개를 합쳐 8개짜리로 만드는데,

    이때도 네개씩 있는 정렬 네개 중 첫번째 인자들을 비교해서 그중 작은인자를 앞에, 두번째도, 세번째도, 네번째도..

    이런식으로 합쳐가면서 정렬을 해나간다.

 

function mergeSort(array) {

    if (array.length < 2) {

        return array;

    }

    let pivot = Math.floor(array.length / 2);

    let left = array.slice(0, pivot);

    let right = array.slice(pivot, array.length);

 

    return merge(mergeSort(left), mergeSort(right));

}

 

function merge(left, right) {

    let result = [];

    while (left.length && right.length) {

        if (left[0] <= right[0]) {

            result.push(left.shift());

        } else {

            result.push(right.shift());

        }

    }

    while (left.length) {

        result.push(left.shift());

    }

    while (right.length) {

        result.push(right.shift());

    }

    return result;

}

 

const array = [5, 2, 4, 7, 6, 1, 3, 8];

 

console.log(mergeSort(array));

 

위에 mergeSort는 아래있는 merge를 실행해주는 함수다.

 

mergeSort먼저 시행해서 가장 작은 단위로 쪼개기전에 반반 나눠주고 그 반반 나눠준 변수값으로
합쳐가면서 정렬을 맞춰간다.

 

 

✍ 퀵 정렬(Quick Sort)

연속적인 분할에 의한 정렬법이다.

처음 하나의 축을 정해 이 축의 값보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 변경하고,

왼쪽 오른쪽의 수들을 다시 각각의 축으로 나눠서 축값이 1이될때 까지 정렬한다.

 

사실 위에 말로는 이해가 어렵다 ..

 

쉽게 생각해보자.

기준 점을 나타내는 변수를 pivot이라고 하고,

기준점을 기준으로 왼쪽에는 기준점보다 작은 항목들이 위치하도록 하고 오른쪽에는 기준점보다 큰 항목들이 위치하도록 한다.

<이 부분 퀵정렬은 내일 다시 공부하고 작성하겠습니다..!!>