알고리즘22 [정렬] 삽입 정렬 (Insertion Sort) 두 번째 자료부터 시작하여 앞에 자료들과 비교하여 알맞은 위치에 자료를 넣는 형식의 정렬이다. 비교를 하는 앞의 배열은 이미 정렬이 되어있다. 즉, n번째 자료를 비교할 때 0 ~ (n - 1) 번째 자료는 정렬이 되어있다. 손에 카드를 들고 정렬하는 방식과 유사하다. 1. i = (1 ~ n)인덱스까지 탐색 2. j = ( (i - 1) ~ 0 ) 인덱스까지 탐색 3. j번째 값이 i번째 값보다 크면 j + 1의 값에 j의 값을 할당하고, 크지 않으면 해당 위치에 i번째 값을 삽입 4. 위 과정 반복 코드 구현 #include void PrintArray(int* arr, int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } pri.. 2020. 1. 20. [정렬] 버블 정렬 (Bubble Sort) 소개 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 다른 정렬 알고리즘에 비해 느린 편이지만, 코드가 간단하다. 정렬 과정 첫 번째 탐색 1. 5와 3을 비교 2. 앞에 있는 5가 더 크므로 5와 3의 위치를 바꾼다. 3. 5와 1을 비교 4. 앞에 있는 5가 더 크므로 5와 1의 위치를 바꾼다. 5. 5와 9를 비교 6. 뒤에 있는 9가 더 크므로 위치를 변경하지 않는다. 7. 9와 7을 비교 8. 앞에 있는 9가 더 크므로 9와 7의 위치를 바꾼다. 9. 첫 번째 순회가 끝난 배열 첫 번째 탐색의 과정을 보면 가장 큰 수가 맨 뒤로 이동하게 된다. 즉, 매 순회마다 정렬된 수를 제외한 가장 큰 수가 맨 뒤로 가 뒤에서부터 정렬이 된다. 그러므로 맨 순회마다 배열의 전체를 탐색할 필요 없이 정.. 2019. 11. 21. 에라토스테네스의 체(Eratosthenes' sieve) 에라토스테네스의 체(Eratosthenes' sieve) 1부터 N사이의 모든 소수와 소수가 아닌 수를 찾는 방법이다. 소수는 1과 자기 자신만을 약수로 가지는 수이다. 쉽게 말해 소수는 자기 자신과 1로 밖에 못 나누는 수이다. 이러한 원리를 이용해 배수를 지우면서 소수가 아닌 수를 배제해 나가는 방법이다. 즉, 1)--- 2의 배수인 4, 6, 8, 10, 12..........지움 3의 배수이면서 지워지지 않은 수인 9, 15, 21.......지움 . . . . . . 2)--- 이러한 과정을 반복하며 소수가 아닌 수를 지워나간 후 마지막까지 지워지지 않은 수인 소수를 찾는 방법이다. ----- 예를 들어 1 ~ 50 사이의 소수를 찾는 다면, 1은 소수가 아니므로 먼저 배제하고 2의 배수들을 배.. 2019. 3. 17. [BOJ 1978] 소수 찾기 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 위 문제를 풀기 위해서는 '에라토스테네스의 체'를 알고 있다면 쉽게 풀 수 있다. 위 알고리즘을 통해 소수를 찾은 후 N개의 수를 입력 받으며 소수인지 아닌지 확인하면 된다. '에라토스테네스의 체'의 자세한 내용은 아래 URL을 통해 볼 수 있다. https://ladun.tistory.com/10?category=323065 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 .. 2019. 3. 16. 이전 1 2 3 다음
