본문 바로가기
  • 장원익 기술블로그

분류 전체보기579

[알고리즘-이론] 퀵 정렬 (Quick Sort) 퀵 소트(Quick Sort)란? 퀵 정렬은 평균적으로 가장 좋은 성능을 가져 현장에서 가장 많이 쓰이는 정렬 알고리즘이다. 바로 예로 설명을 하자면 정렬할 배열 A={31,11,2,6,9} 가 주어진다. 이 때 기준 원소를 중심으로 그 값보다 큰 원소는 뒤에, 작은 원소는 앞에 배치를 하는 식으로 정렬이 이루어진다. 기준 원소를 잡는다. 기준 원소의 왼쪽은 기준 원소보다 작은 값, 오른쪽은 기준 원소보다 큰 값. 왼쪽에 대해서도 재귀호출을 실행한다. 오른쪽에 대해서도 재귀호출을 실행한다. 1라운드 기준 원소를 잡는다 -> 기준원소: 9 -> 기준원소를 기준으로 A[0]부터 값을 비교하며 재배치 한다. -> A={2, 6, 9, 31, 11}; 2라운드 기준 원소를 잡는다 -> 기준원소: 11 -> 기준.. 2019. 11. 23.
[알고리즘-이론] 병합 정렬(Merge Sort) 병합 정렬(Merge Sort)란? 병합정렬은 앞서 설명한 선택 정렬, 버블 정렬, 삽입 정렬과는 비교 할 수 없는 시간 복잡도인 O(n log n)의 알고리즘이다. 현대의 컴퓨터 개념의 시초가 되었떤 폰 노이만(John von Neumann)이 제안한 방법으로 분할 정복 알고리즘중 하나이다. 재귀 호출을 사용하여 정렬의 효율을 극대화 시켰다. 과정 정렬되지 않은 배열을 절반으로 잘라 비슷한 크기의 두 부분의 배열으로 나눈다. 각 부분 배열의 크기가 0이 될 때 까지 반복하고 0이 되면 각 부분을 재귀적으로 합치는 과정을 수행한다. 합치는 과정이 수행될 때 실질적 정렬이 이루어진다. 이런식으로 진행하면 단계를 세 단계로 나눌 수 있다. 1. 분할 : 입력 배열을 같은 크기의 2 개의 부분 배열로 분할한다.. 2019. 11. 23.
[알고리즘-이론] 삽입 정렬 (Insertion Sort) 삽입 정렬(Insertion Sort) 이란? 이미 정렬되어 있는 i개 짜리의 배열에 하나의 원소를 더 더하여 정렬된 i+1 개의 배열을 만드는 과정을 A[n] 까지 반복하는 알고리즘 이다. 차이점이 있다면 지금까지 했던 선택 정렬 이나 버블 정렬은 n 개의 배열에서 시작하여 하나씩 원소를 줄이는데 반하여 삽입 정렬은 그 크기를 하나씩 늘리는 정렬이다. 하지만 선택 정렬이나 버블 정렬에 비하여 구현하기 조금 까다롭다는 점이 있다. 백문이 불여일타 라고 pseudo 코드를 한 번 가볍게 보고 직접 생각해보자. insertionSort(A[], n){ .... 1 for i A[i-1] 이면 A[i]는 A[1..i-1] 의 모든 원소보다 크므로 그냥 제자리에 두고 그렇지 않을 경우 왼쪽부터 차례대로 A[i].. 2019. 11. 23.
[알고리즘-이론] 버블 정렬 (Bubble Sort) 버블 정렬 (Bubble Sort)이란? 버블 정렬은 인접한 두 원소를 비교하여 큰/작은 수를 기준으로 자리를 교환하는 방식으로 정렬하는 알고리즘을 뜻한다. 선택정렬과 같이 제일 큰 원소를 끝자리로 옮기는 작업을 반복하는데 제일 큰 원소를 옮기는 방법의 차이가 있다. 버블정렬을 간단하게 설명하자면. 라운드의 순서별로 임의의 포인터를 만들어 뒷 값과 비교를 하는 과정을 반복한다. 만약 뒷 값보다 크게되면 자리를 옮겨 그 다음 값과 비교하고 크지 않다면 포인터를 뒤로 넘겨 포인터가 정렬되지 않은 배열의 끝까지 도달했을 때 한 라운드가 종료된다. pseudo 코드를 먼저 보자면 bubbleSort(A[], n){ .... 1 for last 7과 22중 22가 더 크므로 포인터를 22로 옮긴다. 결과: {7,.. 2019. 11. 23.
[알고리즘-이론] 선택 정렬(Selection Sort) 선택 정렬(Selection Sort) 이란? 선택정렬은 가장 원리가 간단하면서 알고리즘의 효율로 봤을때 결코 좋은 알고리즘이로 볼 수 없다.(시간 복잡도로 본다면) 원리는 배열 원소에가 가장 큰/작은 수를 배열의 끝으로 보내는 작업을 계속 반복하는 것이다. 선택정렬에는 크게 2가지가 존재하고 정렬 목적에 따라 또 2가지로 나뉘게 된다. 최대 선택 정렬(오름차순) : 큰 수를 가장 오른쪽에 위치시키고 배열의 인덱스를 1씩 줄이는 방법 최대 선택 정렬(내림차순) : 작은 수를 가장 오른쪽에 위치시키고 배열의 인덱스를 1씩 줄이는 방법 최소 선택 정렬(오름차순) : 작은 수를 가장 왼쪽에 위치시키고 배열의 인덱스를 1씩 늘리는 방법 최소 선택 정렬(내림차순) : 큰 수를 가장 왼쪽에 위치시키고 배열의 인덱스.. 2019. 11. 23.
10. 블록체인 기반의 대학 통합 정보서비스 실증 모델 설계 본 글은 문상국(동국대학교 경영 정보학과)의 논문에 필자의 견해를 더해 게시한 글로 연구자의 의도와 다른 의도가 포함될 수 있습니다. 이 연구는 정보 시스템의 중요도가 날로 높아지는 현 시대에 제기되는 각종 불편함과 복잡성을 대체할 기술인 블록체인을 이용하여 대학 통합 정보 서비스를 설계하고 기초 로드맵을 블록체인 기반으로 구성하는 실증 모델을 제시하는 연구다. 블록체인은 데이터 거래 시 참여하는 네트워크 노드가 데이터를 묶음, 블록 (Block)으로 분산 저장하는 분산원장 기술이다. 거래 정보가 중앙 서버에 집중되지 않고 네트워크의 여러 컴퓨터에 공유 저장되는 것을 블록체인이라 한다. 블록체인의 블록은 사슬처럼 이어져 고리를 형성하여 하나의 장부로 만든다. 데이터의 거래 변경이 발생하면 거래 시 데이터.. 2019. 10. 10.

티스토리툴바