이번에는 병합 정렬에 대해 알아보자. 병합 정렬의 경우, 퀵 정렬과 마찬가지로 시간복잡도가 O(N*logN)이다. 퀵 정렬은 최악의 경우에는 O(N^2) 까지도 늘어날 수가 있지만, 병합 정렬의 경우 최악의 경우에도 O(N*LogN)을 보장함으로써 아주 빠른, 훌륭한 정렬 방법이라고 볼 수 있다. 다음 숫자들을 일렬로 정렬하는 알고리즘을 작성하시오. 7 6 5 8 3 5 9 1 병합정렬 또한 분할 정복(divide and conquer) 가 기본 아이디어이다. 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤 각자 계산하고 나중에 합친다. 문제에서 8개의 숫자가 있는데 모두 낱개로 분해한 뒤에, 2개씩 합쳐나가는 것이다. 시작 단계에서는 정렬 안된 낱개의 8개 숫자가, 각 단계를 거치면서 2개씩 묶어서 ..

지난 포스팅에서 살펴본 선택, 버블, 삽입 정렬은 모두 시간복잡도 O(N^2)을 가졌습니다. 그렇기 때문에 데이터의 갯수가 많아지면 일반적인 상황에서 사용하기 매우 어렵습니다. 이번에 다룰 퀵 정렬(Quick Sort)은 대표적인 분할정복(divide and conquer) 알고리즘으로, 시간복잡도 O(N*logN)을 가져 매우 빠른편으로, 일반적인 상황에서 사용하기 용이합니다. 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오. 1 10 5 8 7 6 4 3 2 9 문제는 동일합니다. 숫자들을 arr 배열이라고 합시다. 퀵 정렬에서는 기준값(피벗) 을 정해놓고 진행합니다. 보통 첫 번째 원소인 1 을 피벗으로 정합니다. P: 1보다 큰 숫자를 왼쪽부터 찾고, 1보다 작은 숫자를 오른쪽부터 찾습..

이번에는 삽입정렬에 대해 알아봅시다. 전에 알아본 두 가지 정렬 알고리즘인 선택정렬, 버블 정렬은 시간복잡도가 O(N^2) 로, 비효율적이었습니다. 문제는 동일합니다. 다음 숫자들을 오름차순으로 정렬하시오. 1 10 5 8 7 6 4 3 2 9 삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방식으로 문제를 해결합니다. 선택, 버블 정렬은 모든 원소를 돌면서 정렬은 했지만 삽입 정렬은 그렇지 않고 필요한 경우에만 위치를 바꿉니다. 소스코드 public class TestMain { public static void main(String[] args) { int[] array = {1,10,5,8,7,6,4,3,2,9}; for(int i=0;i=0 && array[j]>array[j+1]){ int tem..

버블 정렬에 대해서 알아보겠습니다. 다음 숫자들을 오름차순으로 정렬하시오. 1 10 5 8 7 6 4 3 2 9 버블 정렬(Bubble Sort)은 인접한 값과 비교하여 더 작은 값을 앞으로 보냅니다. 이 과정을 반복합니다. 알고리즘 중 아이디어는 간단하지만, 가장 비효율적인 알고리즘입니다. 소스코드 public class TestMain { public static void main(String[] args) { int[] array = {1,10,5,8,7,6,4,3,2,9}; for(int i=0;i

다음 숫자들을 오름차순으로 정렬하는 알고리즘을 작성하시오. 1 10 5 8 7 6 4 3 2 9 가장 간단하면서도 쉽게 떠오르는 방법으로 알고리즘을 작성해봅시다. 배열을 탐색하여 가장 작은 값을 앞으로 보내면 어떨까? 순차적으로 가장 작은 숫자를 탐색해 맨 앞쪽과 자리를 바꾸어 줍니다. 가장 기초적이고 원시적인 선택정렬 알고리즘입니다. 소스코드 public class TestMain { public static void main(String[] args) { int[] array = {1,10,5,8,7,6,4,3,2,9}; for(int i=0;i

시간복잡도 시간복잡도란 어떤 알고리즘을 수행하는데 걸리는 시간을 설명하는 계산적인 복잡도를 의미합니다. 컴퓨터 공학에서 시간복잡도를 나타낼 때 빅 오 표기법을 사용하는데, 입력값 N이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기방법입니다. 빅오 표기법의 종류 1. O(1): 입력값의 크기와 상관없이 일정한 실행시간을 보장. 최고의 알고리즘이라 할 수 있다. 2. O(log n) : 로그 함수를 생각해보자. n이 무한히 커져도 값의 차이는 매우 작다고 볼 수 있다. 아주 효율적인 알고리즘. 이진 탐색(Binary-Search)의 경우가 이에 해당한다. 이진탐색 알고리즘은 정렬된 배열 또는 리스트에서 고속으로 탐색할 때 사용된다. 3. O(n): 알고리즘을 수행하는데 걸리는 시간이 입력값에 비례하는..