ㅇ 삽입 정렬 (Insertion Sort) 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입하여 정렬하는 방식이다. 평균 시간복잡도는 O(n²)로 느린 편이지만 구현하기 쉽다. ㅇ 삽입 정렬의 이해 삽입 정렬의 과정은 다음과 같다. ① index 1의 데이터를 선택한다. ② 선택 인덱스(index 1)의 데이터와 이전 정렬된 데이터 범위의 데이터를 비교하여 삽입될 위치를 찾는다. ③ 삽입 위치에 데이터를 삽입한다. ④ index 1에서 index 2로 변경한다. 위 과정을 반복하며 정렬한다. 5 4 1 3 2 라는 배열을 초기 상태를 두고 그림으로 표현하면 다음과 같다. index 1에 해당하는 숫자를 선택하여 정렬된 데이터 범위 내의 어디에 삽입 될 것인지 찾는다. 적절한 위치를 찾으면..
ㅇ 정렬이란? 데이터를 정해진 기준에 따라 배치해 의미 있는 구조로 재설정하는 것이다. 즉, 내림차 순이나 오름차 순으로 다시 배치하는 것이다. ㅇ 정렬의 종류 ① 버블 정렬(Bubble Sort) : 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 ② 선택 정렬(Selection Sort) : 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 ③ 삽입 정렬(Insertion Sort) : 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 ④ 퀵 정렬(Quick Sort) : pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 ⑤ 병합 정렬(Merge Sort) : 이미 정렬된 부분 집합들을 효율적으로 병합해 ..
ㅇ 소수란? 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 예를 들어 10보다 작은 소수는 2, 3, 5, 7이 있다. ㅇ 소수 찾기 소수를 찾는 방법은 총 3가지가 있다. 1. N을 N보다 작은 자연수로 모두 나누기 2. N의 제곱근보다 작은 자연수로 모두 나누기 3. 에라토스테네스의 체 이용하기 ㅇ N보다 작은 자연수로 나누기 첫번째 방법은 매우 간단하면서 기초적인 방법이다. N보다 작은 수로 모두 나누어 만약 나누어 떨어지는 것이 없다면 N은 소수일 것이다. 예를 들어보자. 만약 6이 주어졌을 때 1보다 크고 6보다 작은 수, 2, 3, 4, 5로 모두 나누어보자. 6 / 2 = 3 6 / 3 = 2 6 / 4 = 1 ... 2 6 / 5 = 1 ... 1 6은 2와 3으로 나누어 떨어..
ㅇ 알고리즘이란? 컴퓨터가 특정 문제를 해결하는 방식이다. 물론 특정 문제를 해결하는 방식이 많이 있지만, 그중에서도 효율적인 방식을 찾는 것이 중요하다. 이러한 효율적인 알고리즘을 찾는 기준은 시간복잡도이다. ㅇ 시간복잡도란? 알고리즘의 시간 복잡도는 성능을 나타내는 척도 중 하나로 알고리즘의 수행 시간을 나타낸다. 즉, 프로그램이 얼마나 많은 시간이 걸리는지를 나타내는 것이다. 다시 말하면, 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주한다. 시간복잡도가 큰 알고리즘은 작은 데이터에서도 느리게 동작하는 반면, 시간복잡도가 작은 알고리즘은 빠르게 동작한다. ㅇ 시간복잡도 유형 이러한 시간복잡도를 정의하는 3가지 유형이 있다. ①..
