2021년 6월

2021-06-01#

블록체인#

데이터 분산 처리 기술

개념#

블록체인은 '분산원장'(分散元帳, distributed ledger) 기술이라고 한다. 즉, 거래내역을 기록한 원장을 다수의 사람들에게 분산하여 저장·관리하는 기술이다. 자세히 설명하면, 블록체인이란 다수의 온라인 거래 기록을 묶어 하나의 데이터 블록(block)을 구성하고, 해시(hash) 값을 이용하여 이전 블록과 이후 블록을 체인(chain)처럼 연결한 뒤, 이 정보의 전부 또는 일부를 P2P 방식으로 전 세계 여러 컴퓨터에 복사하여 분산 저장·관리하는 기술이다.

역사#

블록체인을 처음 만든 것은 사토시 나카모토(Satoshi Nakamoto)라는 가명을 쓰는 사람이었다. 그는 2008년 10월 31일 〈비트코인 : 개인 대 개인의 전자화폐 시스템〉이라는 논문을 작성하여 암호학계 관련자들이 공동으로 사용하는 메일링 리스트로 전송하였다. 이듬해인 2009년 1월 3일 사토시 나카모토는 블록체인 기술을 적용한 최초의 암호화폐인 비트코인(Bitcoin)을 개발하고 C++ 언어로 작성한 소스 코드를 배포했다.

기존거래와 블록체인의 차이점#

기존거래 방식은 거래 내역을 은행이 저장 하고 블록체인은 거래 내역을 여러 명이 나눠서 저장을 합니다. 만약 한 네트워크에 10명이 참여하고 있다면 거래 내역을 10개의 블록을 생성해 10명 모두에게 전송, 저장한다. 나중에 거래 내역을 확인할 때는 블록으로 나눠 저장한 데이터들을 연결해 확인한다.

블록체인 개념도

특징#

블록체인은 분산저장을 한다는 점이 특징입니다. 기존 거래 방식에서 데이터를 위·변조하기 위해선 은행의 중앙서버를 공격하면 가능했습니다. 그러나 블록체인은 여러 명이 데이터를 저장하기 때문에 위·변조가 어렵습니다. 블록체인 네트워크를 위·변조하기 위해서는 참여자의 거래 데이터를 모두 공격해야 하기 때문에 사실상 해킹은 불가능하다고 여겨집니다.

거래과정#

A가 B에게 송금 희망 등의 거래 요청을 한다.
해당 거래 정보가 담긴 블록이 생성된다.
블록이 네트워크상의 모든 참여자 에게 전송된다
참여자들은 거래 정보의 유효성을 상호 검증한다.
참여자 과반수의 데이터와 일치하는 거래내역은 정상 장부로 확인하는 방식으로 검증이 완료된 블록은 이전 블록에 연결되고, 그 사본이 만들어져 각 사용자의 컴퓨터에 분산 저장된다.
A가 B에게 송금하여 거래가 완료된다.

2021-06-08#

삽입 정렬(insertion sort)#

삽입 정렬(insertion sort) 알고리즘 개념 요약#

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 방법

삽입 정렬(insertion sort)알고리즘의 구체적인 개념#

삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
처음 key값은 두번쨰 자료부터 시작한다.

삽입 정렬(insertion sort) 알고리즘의 예제#

배열에 8,5,6,2,4가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

1회전: 두 번째 자료인 5를 Key로 해서 그 이전의 자료들과 비교한다.
- Key 값 5와 첫 번째 자료인 8을 비교한다. 8이 5보다 크므로 8을 5자리에 넣고 Key 값 5를 8의 자리인 첫 번째에 위치 시킨다.
2회전: 세 번째 자료인 6을 Key 값으로 해서 그 이전의 자료들과 비교한다.
- Key 값 6과 두 번째 자료인 8을 비교한다. 8이 Key 값보다 크므로 8을 6이 있던 세 번째 자리에 위치 시킨다.
- Key 값 6과 첫 번째 자료인 5를 비교한다. 5가 Key 값보다 작으므로 Key 값 6을 두 번째 자리에 위치 시킨다.
3회전: 네 번째 자료인 2를 Key 값으로 해서 그 이전의 자료들과 비교한다.
- Key 값 2와 세 번째 자료인 8을 비교한다. 8이 Key 값보다 크므로 8을 2가 있던 네 번째 자리에 위치 시킨다.
- Key 값 2와 두 번째 자료인 6을 비교한다. 6이 Key 값보다 크므로 6을 세 번째 자리에 위치 시킨다.
- Key 값 2와 첫 번째 자료인 5를 비교한다. 5가 Key 값보다 크므로 5를 두 번째 자리에 넣고 그 자리에 Key 값 2를 위치 시킨다.
4회전: 다섯 번째 자료인 4를 Key 값으로 해서 그 이전의 자료들과 비교한다.
- Key 값 4와 네 번째 자료인 8을 비교한다. 8이 Key 값보다 크므로 8을 다섯 번째 자리에 위치 시킨다.
- Key 값 4와 세 번째 자료인 6을 비교한다. 6이 Key 값보다 크므로 6을 네 번째 자리에 위치 시킨다.
- Key 값 4와 두 번째 자료인 5를 비교한다. 5가 Key 값보다 크므로 5를 세 번째 자리에 위치 시킨다.
- Key 값 4와 첫 번째 자료인 2를 비교한다. 2가 Key 값보다 작으므로 4를 두 번째 자리에 위치 시킨다.

구현 코드#

function insertionSort(arr) {
  let key;
  let x;
  for (let i = 1; i < arr.length; i++) {
    key = arr[i];
    for (x = i - 1; x >= 0 && arr[x] > key; x--) {
      arr[x + 1] = arr[x];
    }
    arr[x + 1] = key;
  }
  return arr;
}
let arr = [8, 5, 6, 2, 4];
console.log(insertionSort(arr)); // [2, 4, 5, 6, 8]

삽입 정렬(insertion sort) 알고리즘의 특징#

장점

안정한 정렬 방법
레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

단점

비교적 많은 레코드들의 이동을 포함한다.
레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.

정렬 알고리즘 시간 복잡도 비교#

단순(구현 간단) 하지만 비효율적인 방법
- 삽입 정렬(insertion sort), 선택 정렬(selection sort), 버블 정렬(bubble sort)
복잡하지만 효율적인 방법
- 퀵 정렬(quick sort), 힙 정렬(heap sort), 병합 정렬(merge sort), 셸 정렬(shell sort)

출처:https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

2021-06-15#

선택 정렬(selection sort)#

선택 정렬(selection sort) 알고리즘 개념 요약#

제자리 정렬(in-place sorting) 알고리즘의 하나
- 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
- 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
- 두 번째 순서에는 두 번째 위치에 남은 값 중에서 최소값을 넣는다.
- ...
과정 설명
1. 주어진 배열 중에서 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
4. 하나의 원소만 남을 때까지 위의 1~3과정을 반복한다.

선택 정렬(selection sort)알고리즘의 구체적인 개념#

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.

선택 정렬(selection sort) 알고리즘의 예제#

배열에 9,6,7,3,5가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
1회전
- 첫 번째 자료 9를 두 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 4번 비교한다.
2회전
- 두 번째 자료 6을 세 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 두 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 3번 비교한다.
3회전
- 세 번째 자료 7을 네 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 2번 비교한다.
4회전
- 네 번째 자료 9와 마지막에 있는 7을 비교하여 서로 교환한다.

구현 코드#

function solution(n, arr) {
  let temp;
  let minIndex;
  for (let i = 0; i < n - 1; i++) {
    minIndex = i;
    //최소값 구하기
    for (let j = i + 1; j < n; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    //위치 바꾸기
    if (i != minIndex) {
      temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
  return arr;
}
let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(6, arr)); // [5, 7, 11, 13, 15, 23]

선택 정렬(selection sort) 알고리즘의 특징#

장점
- 정렬을 위한 비교 횟수는 많으나 교환 횟수가 적기에, 교환이 많이 이루어져야 하는 상태에서 효율적으로 사용될 수 있으며, 이에 가장 적합한 자료 상태는 역순 정렬이다. 즉, 내림차순이 정렬되어 있는 자료를 오름차순으로 재정렬할 때 적합하다.
단점
- 안정성을 만족하지 않는다.
- 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.
- 정렬을 위한 비교 횟수가 많으며, 이미 정렬된 상태에서 소수의 자료가 추가되면 재정렬할 때 최악의 처리 속도를 보인다.

선택 정렬(selection sort)의 시간복잡도#

비교 횟수
- 두 개의 for 루프의 실행 횟수
- 외부 루프: (n-1)번
- 내부 루프(최솟값 찾기): n-1, n-2, … , 2, 1 번
교환 횟수
- 외부 루프의 실행 횟수와 동일. 즉, 상수 시간 작업
- 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 3(n-1)번
T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

정렬 알고리즘 시간 복잡도 비교#

단순(구현 간단) 하지만 비효율적인 방법
- 삽입 정렬(insertion sort), 선택 정렬(selection sort), 버블 정렬(bubble sort)
복잡하지만 효율적인 방법
- 퀵 정렬(quick sort), 힙 정렬(heap sort), 병합 정렬(merge sort), 셸 정렬(shell sort)

출처:https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

2021-06-22#

버블 정렬(bubble sort)#

버블 정렬(bubble sort) 알고리즘 개념 요약#

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
- 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
선택 정렬과 기본 개념이 유사하다.

버블 정렬(bubble sort) 알고리즘의 구체적인 개념#

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세번째 자료를, 세 번째와 네 번째를 ... 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
1회전을 수행하고 나면 가장 큰 값의 자료가 맨 뒤로 이동 하므로 그 다음 회전에서는 맨 끝에 있는 자료는 정렬 에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

버블 정렬(bubble sort) 알고리즘의 예제#

배열에 7,4,5,1,3 이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
1회전
- 첫 번째 자료 7을 두 번째 자료 4와 비교하여 교환하고, 두 번째의 7과 세 번째의 5를 비교하여 교환하고, 세 번째의 7과 네 번째의 1을 비교하여 교환하고, 네 번째의 7과 다섯 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 네 번 비교한다. 그리고 가장 큰 자료가 맨 끝으로 이동하므로 다음 회전에서는 맨 끝에 있는 자료는 비교할 필요가 없다.
2회전
- 첫 번째의 4을 두 번째 5와 비교하여 교환하지 않고, 두 번째의 5와 세 번째의 1을 비교하여 교환하고, 세 번째의 5와 네 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 세 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 두 번째에 놓인다.
3회전
- 첫 번째의 4를 두 번째 1과 비교하여 교환하고, 두 번째의 4와 세 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 두 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 세 번째에 놓인다.
4회전
- 첫 번째의 1과 두 번째의 3을 비교하여 교환하지 않는다.

구현 코드#

function bubble_sort(n, arr) {
  let temp;
  for (let i = 0; i < n; i++) {
    for (let x = 0; x < n - i; x++) {
      if (arr[x] > arr[x + 1]) {
        temp = arr[x];
        arr[x] = arr[x + 1];
        arr[x + 1] = temp;
      }
    }
  }
  return arr;
}

버블 정렬(bubble sort) 알고리즘의 특징#

장점
- 구현이 매우 간단하다.
단점
- 순서에 맞지 않는 요소를 인접한 요소와 교환한다.
- 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환 되어야 한다.
- 특히 일정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

버블 정렬(bubble sort)의 시간복잡도#

비교 횟수
- 최상,평균,최악 모두 일정
- n-1,n-2,````,2,1 번 = n(n-1)/2
교환 횟수
- 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 *3) 번 = 3n(n-1)2
- 입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.
T(n) = O(n^2)

정렬 알고리즘 시간 복잡도 비교#

단순(구현 간단) 하지만 비효율적인 방법
- 삽입 정렬(insertion sort), 선택 정렬(selection sort), 버블 정렬(bubble sort)
복잡하지만 효율적인 방법
- 퀵 정렬(quick sort), 힙 정렬(heap sort), 병합 정렬(merge sort), 셸 정렬(shell sort)

출처:https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

2021-06-29#

셸 정렬(shell sort)#

셸 정렬(shell sort) 알고리즘 개념 요약#

'Donald L.Shell'이라는 사람이 제안한 방법으로, 삽입 정렬을 보완한 알고리즘이다.
삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안
- 삽입 정렬의 최대 문제점: 요소들이 삽입될 때, 이웃한 위치로만 이동
- 즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다.
- 삽입 정렬과 다르게 셸 정렬은 전체 리스트를 한 번에 정렬하지 않는다.
과정 설명
1. 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류
2. 연속적이지 않은 여러 개의 부분 리스트를 생성
3. 각 부분 리스트를 삽입 정렬을 이용하여 정렬
4. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 반복
5. 위의 과정을 부분 리스트의 개수가 1이 될 때까지 반복

셸 정렬(shell sort) 알고리즘의 구체적인 개념#

정렬해야 할 리스트의 각 k 번째 요소를 추출해서 부분 리스트를 만든다. 이때, k를 '간격(gap)' 이라고 한다.
- 간격의 초깃값: (정렬할 값의 수)/2
- 생성된 부분 리스트의 개수는 gap과 같다.
각 회전마다 간격 k를 절반으로 줄인다. 즉, 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 증가한다.
- 간격은 홀수로 하는 것이 좋다.
- 간격을 절반으로 줄일 때 짝수가 나오면 +1을 해서 홀수로 만든다.
간격 k가 1이 될 때까지 반복한다.

셸 정렬(shell sort) 알고리즘의 예제#

배열에 10,8,6,20,4,3,22,1,0,15,16이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
1회전
- 처음 간격을 (정렬할 값의 수:10)/2 =5로 하고, 다섯 번째 요소를 추출해서 부분 리스트를 만든다. 만들어진 5개의 부분 리스트를 삽입 정렬로 정렬한다.
2회전
- 다음 간격은 = (5/2: 짝수)+1 = 3으로 하고, 1회전 정렬한 리스트에서 세 번째 요소를 추출해서 부분 리스트를 만든다. 만들어진 3개의 부분 리스트를 삽입 정렬로 정렬한다.
3회전
- 다음 간격은 = (3/2) = 1으로 하고, 간격 k가 1이므로 마지막으로 정렬을 수행한다. 만들어진 1개의 부분 리스트를 삽입 정렬로 정렬한다.

구현 코드#

function shellSort(list) {
  let gap;
  for (gap = Math.floor(list.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
    if (gap % 2 === 0) gap++;
    for (let i = 0; i < gap; i++) {
      insertSort(list, i, gap);
    }
  }
}

function insertSort(list, first, gap) {
  let key;
  let j;
  for (let i = first + gap; i < list.length; i += gap) {
    key = list[i];
    for (j = i - gap; j >= first; j -= gap) {
      if (list[j] < key) break;
      list[j + gap] = list[j];
    }
    list[j + gap] = key;
  }
}

셸 정렬(shell sort) 알고리즘의 특징#

장점
1. 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 따라서 교환되는 요소들이 삽입 정렬보다 최종 위치에 있을 가능 성이 높아진다.
2. 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면 셸 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 삽입 정렬보다 더욱 빠르게 수행된다.
3. 알고리즘이 간단하여 프로그램으로 쉽게 구현할 수 있다.

셸 정렬(shell sort)의 시간복잡도#

시간 복잡도를 계산한다면

평균: T(n) = O(n^1.5)
최악의 경우: T(n) = O(n^2)

정렬 알고리즘 시간 복잡도 비교#

출처:https://gmlwjd9405.github.io/2018/05/08/algorithm-shell-sort.html