코딩 테스트를 매일 풀면서 느끼지만 알고림즘이 크게 필요하지 않은 (프로그래머스) Lv.0,1 단계만 풀다보니 다른 난이도 있는 문제를 접하면 머리가 하예지고 손도 못 대겠더라고요...🥲
어떻게하면 알고리즘 문제를 잘 풀 수 있을까 찾아보니 유튜브에 입문자(?)들을 위해 정리를 잘해두신 분이 있더라고요!
그래서 알고리즘 공부를 체계적으로 해려고 합니다🔥
일반적으로 가장 먼저 풀어보는 것이 '정렬(sort)'인데 그중에서 가장 접근하기 쉬운 '선택 정렬'에 대해 공부해 보았습니다.
2학년 1학기 마지막쯤에 자료구조 수업에서 배운 기억이 나 반갑네요. 이해가 가지 않아도 뭐라도 들어 놓으니 다시 공부할 때 도움이 되는 것 같습니다.
다음 학기부터는 수업에 더더더 집중해야겠습니다!!
다음은 문제입니다.
2,6,10,3,7,1,5,8,4,9 을 오름차순으로 정렬하시오.
선택 정렬은 원소 중 가장 작은 값을 선택해서 제일 앞으로 보내여 정렬하는 알고리즘입니다.
코드
#include <stdio.h>
int main() {
int array[10] = { 2,6,10,3,7,1,5,8,4,9 };
int i, j, min, index, temp;
for (i = 0; i < 10; i++) {
// 최솟값을 구하기 위해 조건의 값 중에서 가장 큰 값으로 임의로 정한 것 입니다.
min = 999;
for (j = i; j < 10; j++) { //앞을 제외한고 i부터 끝까지 반복
if (min > array[j]) {
min = array[j]; //최솟값
index = j; //인덱스값
}
}
//swap(교환) : 최솟값의 위치와 맨 앞 인덱스 자리를 교환
// 원본 : { 2,6,10,3,7,1,5,8,4,9 }
//교환 후 : { 2,3,10,6,7,1,5,8,4,9 } -> 3과 6을 교환
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
for (i = 0; i < 10; i++) {
printf("%d ", array[i]); //결과 출력하기 : 1 2 3 4 5 6 7 8 9 10
}
return 0;
}선택 정렬의 시간 복잡도는 O(n^2) 입니다.
그 이유를 설명해드리겠습니다.
2,6,10,3,7,1,5,8,4,9을 정렬하기 위해서는 처음부터 끝까지 반복을 하며 최솟값을 찾아 맨 앞으로 보내줘야합니다.
- 처음(1)부터 끝까지 : 최솟값=1 ,
1,6,10,3,7,2,5,8,4,9- 두번째(6)부터 끝까지 : 최솟값=2,
1,2,10,3,7,6,5,8,4,9- 세번째(10)부터 끝까지 : 최솟값=3,
1,2,3,10,7,6,5,8,4,9- 네번째(10)부터 끝까지 : 최솟값=4,
1,2,3,4,7,6,5,8,10,9- 다섯번째(7)부터 끝까지 : 최솟값=5,
1,2,3,4,5,6,7,8,10,9- 여섯번째(6)부터 끝까지 : 최솟값=6,
1,2,3,4,5,6,7,8,10,9- 일곱번째(7)부터 끝까지 : 최솟값=7,
1,2,3,4,5,6,7,8,10,9- 여덟번째(8)부터 끝까지 : 최솟값=8,
1,2,3,4,5,6,7,8,10,9- 아홉번째(10)부터 끝까지 : 최솟값=9,
1,2,3,4,5,6,7,8,9,10
10번 + 9번 + 8번 + 7 + ... + 2 + 1번 확인을 해야합니다.
이게 등차수열이므로 등차수열의 합으로 구하면 10(10+1)/2=55 입니다. 즉, 최소 55번은 이동을 해야한다는 것입니다.
이를 정리하면 N * (N + 1) / 2입니다. 컴퓨터는 방대한 데이터를 처리하기 때문에 더하기, 나누기 같은 자잘한 연산들은 무시합니다. 따라서 N * N = N^2입니다.
N^2는 시간 복잡도 사이에서 가장 느리기 때문에 가능한 사용하지 않는게 좋다고 합니다. 쉽지만 느려 많이 사용지 않는다는 것이 좀 슬프네요..🥲
