Page tree
Skip to end of metadata
Go to start of metadata


참여 링크 - https://meet.google.com/ytw-nkkt-zzr

주제 소개

정렬이란? 정렬(sorting)은 이름,학번, 키 등 핵심 항목(key)의 대소관계에 따라 데이터 집합을 일정한순서로 줄지어 늘어서도록 바꾸는 작업을 말합니다


단순 정렬

가장 단순한 정렬 중 삽입 정렬과 선택 정렬이 있으며 이 둘 모두 낮은 부하로 인해 작은 데이터에 효율적이지만 큰 데이터에는 효율적이지 않다.


효율 정렬

실용적인 일반 정렬 알고리즘들은 평균 시간 복잡도(및 일반적으로 최악의 경우의 복잡도) O(n log n)의 알고리즘에 기반한 경우가 대부분이며 그 중 가장 흔한 것이 힙 정렬, 합병 정렬, 퀵 정렬이다


선택 정렬

  1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택
  2. a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환
선택정렬
for(int i = 0; i < n - 1 ; i++) {
	// min = a[i] ~ a[n - 1] 에서 가장 작은 값을 가지는 요소의 인덱스
	// a[i] 와 a[min] 의 값을 교환


삽입 정렬

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

  1. 주어진 배열 중에서 최솟값 또는 최댓값을 찾는다.
  2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
  3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
  4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
삽입 정렬
for (int i =1; i <n; i++) {
		A[1...last] 중 가장 큰 수 A[k]를 찾는다
        A[K] = A[last]; A[k]와 A[last]값을 교환
}


합병 정렬

  1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
  2. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  3. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  4. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
  5. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.
합병정렬
mergeSort(A[],p,r){
    if(p<r) then{
        q = (p+r)/2;
        mergeSort(A,p,q);
        mergeSort(A,q+1,r);
        merge(A, p, q, r);
    }
}

merge(A[], p, q, r){
    정렬되어 있는 배열 A[p..q]와 A[q+1...r]을 합하여
    정렬된 하나의 배열 A[p...r]을 만든다.
}



ref )https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html


문자열

문자열 검색이란 어떤 문자열 안에 다른 문자열이 들어 있는지 조사하고 들어 있다면 그 위치를 찾아내는 것을 말합니다


브루트-포스법 (Brute: 짐승, 동물, Force: 힘)

이름에서 느껴지듯, 매우 단순무식한 알고리즘 가능한 모든 경우에 대해 모두 직접 해 보는 방법

ex) N : ABCABABCDE , M : CAB

이 과정의 시간 복잡도는 텍스트의 길이를 N, 패턴의 길이를 M이라 할 때 각 텍스트의 인덱스에 대해 패턴이 일치하는지 비교하므로 O(NM)입니다.


KMP (Knuth, Morris, Prett)

KMP 알고리즘을 이용하면 O(N+M)에 문자열 검색을 할 수 있습니다.

KMP알고리즘의 시간 복잡도는 O(N+M)으로 위의 무식한 방법 O(NM) 보다 매우 빠릅니다.

https://bowbowbow.tistory.com/6


기본 예시

https://leetcode.com/problems/sort-colors/

https://leetcode.com/problems/valid-anagram/


문제

https://leetcode.com/


https://leetcode.com/problems/relative-sort-array/  (easy) 

https://leetcode.com/problems/largest-number/ (medium)

https://leetcode.com/problems/find-and-replace-in-string/ (medium)

  • No labels