본문 바로가기

알고리즘7

계수 정렬 (Counting Sort) 계수 정렬의 시간 복잡도는 O(N)으로 굉장히 빠르다. 기존 정렬들과 다른 점은 각 인덱스에 위치한 값들을 서로 바꾸어주는 것이 아니라 값의 크기를 기준으로 개수를 세는 알고리즘이다. 단! 범위 조건이 있는 조건에 한해서만 빠른 알고리즘이다. 예시를 보면 1 ~5까지 범위의 제한이 있다. 1 2 1 3 5 3 4 2 1 5 2 4 3 1 2 3 2 5 5 2 3 2 1 5 5 4 2 3 1 1 만약 이렇게 되어있다면 1. 0인덱스 1 2 1 3 5 3 4 2 1 5 2 4 3 1 2 3 2 5 5 2 3 2 1 5 5 4 2 3 1 1 크기 1 2 3 4 5 개수 1 0 0 0 0 2. 1 인덱스 1 2 1 3 5 3 4 2 1 5 2 4 3 1 2 3 2 5 5 2 3 2 1 5 5 4 2 3 1 1 .. 2021. 11. 9.
C++STL sort()함수 sort()함수를 이용한다면 알아서 정렬을 해준다. => 1 2 3 4 5 6 7 8 9 10 이 출력된다. sort( )안에는 정렬하려는 배열의 메모리 주소값을 넣어준다. 따라서 a 는 첫 번째 원소의 메모리주소, a+10은 a 배열의 마지막 원소의 주소까지 정렬한다는 소리다. 하지만 내가 함수를 만들어서 정렬을 바꿀 수도 있다. 만약 오름차순으로 한다면 compare 함수의 return a 10 9 8 7 6 5 4 3 2 1 데이터 묶어서 정렬하는 방법 Student 클래스에 이름과 점수가 있고 operator 함수는 점수가 작을 경우 true값을 반환하게 설정하여 즉 점수가 작은 순서대로 정렬한다. 2021. 11. 2.
병합 정렬(Merge Sort) 키 포인트!! 일단은 반으로 나누고 나중에 합친다! 병합정렬은 퀵정렬가 달라 피벗 값이 없고 항상 반으로 나누는 특징이 있다 이렇게 반으로 쪼개는 단계때문에 O(Nlog N)이 된다. 또한 퀵 정렬과 다르게 정확히 반으로만 나누기 때문에 NlogN이 보장이 된다. 7 4 5 8 6 3 10 9 이런 배열이 있다고 가정하자 이것을 이제 2의 배수의 개수만큼 합친다. 근데 그때 오름차순으로 정렬하면서 합친다 2^1 : 4,7 5,8 3,6 9,10 2^2 : 4,5,7,8 3,6,9,10 2^3 : 3,4,5,6,7,8,9,10 이렇게 2의 승으로 진행되기 때문에 많은 데이터를 다룰 수가 있고 이 때문에 시간복잡도가 logN이다. 위의 표를 사각형으로보면 가로는 N이고 높이는 logN이다 따라서 총 시간 복.. 2021. 11. 1.
퀵 정렬 대표적인 분할 정복 알고리즘 으로 평균 속도는 O(N*logN)이다 삽입, 버블, 선택 보다는 훨씬 더 빠르다. 포인트는 특정한 값을 기준으로 서로 교환한 뒤에 배열을 반으로 나누는 것! 3 7 8 1 5 9 6 10 2 4 이런 배열이 있다면 가장 앞에 있는 3이 피벗값(기준값)이 된다. 이것을 기준으로 오른쪽으로 가면서 자신보다 큰 값을 찾고 배열의 끝 4부터는 자신보다 작은 값을 찾는다. 찾았다면 서로의 위치를 바궈준다. 3 2 8 1 5 9 6 10 7 4 이렇게 피벗값은 변하지 않은 채로 이 과정을 반복해준다. 3 2 1 8 5 9 6 10 7 4 이 경우 엇갈렸다 라는 표현을 쓰는 데 배열 끝에서부터 피벗값보다 작은 값의 INDEX 값이 오른쪽에서 피벗값보다 큰 값을 찾는 데의 INDEX 보다.. 2021. 10. 30.
삽입정렬 삽입 정렬은 숫자를 적절한 위치에 삽입하는 방법이다. 즉 필요할 때에만 위치를 바꾸면 된다. 8번라인에서 j=i인 이유는 비교할 숫자를 선택하는 것이다 그리고 13번라인에서 j--를 해주는 이미 정렬되어 있는 왼쪽에 배열과 비교하기 때문이다. 위의 array처럼 되어 있다면 10 >4인 경우 임으로 4와 10의 위치를 바꾼다. 그리고 for문으로 가서 2는 10앞에 들어갈 지 4 앞에 들어갈지 비교한다. 이렇게 현재 자신의 왼쪽에 이미 정렬되어 있는 배열과 비교한다. 만약 자신이 왼쪽 배열보다 크다면 반복문에서 벗어나기 때문에 멈춰서 필요할 때만 삽입되는 것을 알 수 있다. 즉 기본적으로 정렬이 되어있다고 가정하면서 돌린다. 이것도 마찬가지로 시간복잡도는 O(N^2) 이다 ※ 만약 거의 정렬되어 있다면... 2021. 10. 30.
버블정렬 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내는 것! 1회전 했을 때 가장 큰 값이 가장 뒤로 간다! 9번 라인에서 9-i를 해주는 이유는 1회전 할 때 10부터 3까지 다 비교를 하고 그 다음 9까지 8까지 이렇게 끝에서부터 하나씩 줄기 때문이다. 11번부터 13번 라인은 선택과 똑같이 서로의 위치를 교환해주는 알고리즘이다. 버블정렬도 선택과 마찬가지로 데이터 개수가 N개 일때 N * (N+1)/2이다 따라서 O(N^2) 이다. 그러나 빅오표기법은 똑같지만 버블정렬은 선택정렬보다 오래걸린다. 그 이유는 11번에서 13번 라인을 계속 비교하기 때문에 수행시간이 선택정렬보다 더 걸린다. 따라서 가장 비효율적인 알고리즘이라 할 수 있다. 2021. 10. 30.
선택정렬 선택정렬은 말그대로 어떤 기준에 맞는 것을 선택하여 바꾸는 알고리즘이다. 13번까지 array를 돌면서 가장 작은 값을 min에 넣어주고 그 가장 작은 값이 있는 위치를 index에 넣어준다. 그리고 현재 i=0이기 때문에 해당 위치에 있는 값을 temp에 넣어주고 0번위치에 가장 작은 값이 있던 위치의 값을 넣어준다. 그리고 그 처음 i=0의 위치에 있던 값을 index에 넣어 위치를 바꿔주는 알고리즘이다. 이 선택 정렬의 시간 복잡도는 O(N^2)이다. 1 ,2 3, 4, 5, 6, 7, 8, 9, 10 이렇게 10개의 숫자 배열이 있다면 서로 크기를 비교하기 위해 처음에 10번, 가장 작은 값을 찾았다면 그거 빼고 9번, 8번....1번 총 10+9+8+7+...+2+1= 55번 비교를 한다. 이것.. 2021. 10. 29.

티스토리툴바