본문 바로가기

장원익 기술블로그

💻 Computer Science191

[알고리즘-이론] 퀵 정렬 (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.

이전 1 ··· 29 30 31 32 다음

티스토리툴바