알고리즘16 [알고리즘] 삽입 정렬 (Insertion Sort) 목차 삽입 정렬이란? 삽입 정렬이란 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신이 들어갈 위치를 찾아 삽입함으로써 정렬을 하는 알고리즘이다. 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다. 삽입 정렬의 원리는 두 번째 자료부터 시작해서 그 앞의 정렬되어 있는 자료들과 비교하여 삽입할 위치를 찾은 뒤에 자료를 뒤에 옮기고 지정한 자료를 삽입하여 정렬하는 알고리즘이다. 즉, 2번째 자료는 1번째 자료, 3번째 자료는 2번째와 1번째 자료, 4번째 자료는 3번째, 2번째, 1번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 이제 예시를 한번 보겠다. 소스 코드 static void insertionSort() { int j, temp; int .. 2022. 7. 21. [알고리즘] 버블 정렬 (Bubble Sort) 목차 버블 정렬이란? 버블 정렬이란 옆에 있는 값과 비교해서 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법이다. 만약에 내림차순으로 정렬을 한다고 하면 옆에 있는 값과 비교해서 더 큰 값을 앞으로 보내면 된다. 우선 예시를 하나 살펴보겠다. 다음과 같은 배열을 오름차순으로 정렬한다고 가정하겠다. 우선 첫 번째와 두 번째 숫자, 즉 4와 2를 비교한다. 2가 4보다 더 작으니 더 작은 숫자인 2를 앞으로 보낸다. 그다음에는 두 번째와 세 번째 숫자, 즉 4와 1을 비교한다. 비교하고 더 작은 1을 앞으로 보낸다. 4와 5를 비교했을 때 4가 더 작으니 건너뛴다. 이 과정을 끝까지 반복하면 다음과 같다. 이 예시에서 알 수 있듯이 더 큰 숫자가 계속 뒤로 밀려나고 마지막에는 가장 큰 숫자가 맨 뒤로 밀려.. 2022. 7. 16. [알고리즘] 에라토스테네스의 체 (Sieve of Eratosthenes) 목차 에라토스테네스의 체란? 에라토스테네스의 체는 소수 판별 알고리즘이다. 소수란 ‘양의 약수를 두 개만 가지는 자연수’를 뜻한다. 즉, 1과 자기 자신만 약수로 가진다. 소수의 예시로는 2, 3, 5, 7, 11, 13 등이 있다. 에라토스테네스의 체는 이런 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 우선 먼저 가장 기본적인 소수 판별 알고리즘들을 살펴보겠다. 시간 복잡도 O(N) boolean isPrime(int n) { for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; } 자연수 n이 소수인지 아닌지 판별하는 가장 쉬운 방법은 2부터 n - 1까지의 수로 나누어 떨어지는지 아닌지 확인하는 것이다. 이때, .. 2022. 7. 15. [알고리즘] 선택 정렬 (Selection Sort) 목차 선택 정렬이란? 선택 정렬 (Selection Sort)이란 배열에서 가장 작은 또는 가장 큰 원소의 위치를 찾고, 그 위치와 배열의 가장 첫 번째 원소부터 차례로 바꿔주는 정렬 방식이다. 이렇게 간단하기 때문에 선택 정렬은 가장 기본적인 정렬 방식이다. 그리고 정렬을 할 때 추가적인 공간이 필요 없기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 우선 한 배열의 숫자들을 오름차순으로 정렬을 한다고 가정해 보겠다. 이때 선택 정렬의 과정은 다음과 같다: 1. 주어진 배열에서 최솟값을 찾는다. 2. 최솟값을 맨 앞자리의 값과 교환한다. 3. 맨 앞자리를 제외한 나머지 값들 중 최솟값을 찾아 위와 같은 방법으로 반복한다. 이제 다음과 같은 예시를 한번 보겠다. 이 예시에는 1부터 7까지.. 2022. 5. 26. 이전 1 2 3 4 다음 반응형
