[코테]알고리즘

2021.1.25 월

브루트 포스 (완전 검색)

• 가능한 모든 경우에 대해 모두 직접 해 보는 방법
• 중요하지만 쉬움
• 다른 알고리즘을 생각할 때 도움이 됨 (완전검색으로 시작하여 완벽하게 답인것을 확인하고 더 효율적인 알고리즘으로 넘어가기)

추가 개념)
bagy-gin = run(연속된 3개의 숫자 ex) 1,2,3) + triplet(같은 숫자 3개 ex) 3,3,3) - 지금은 이런게 있다 정도로만 알아두기

시간복잡도

• O(1) : 상수시간 ex) li[0] - 하나를 불러오는데 걸리는 시간
• O(n) : 선형시간 ex) for문 - n번 돌아가야 하는 경우
• O(logn) : 로그시간 ex) range(1,n*1/2)와 같이 n보다 더 좁은 범위로 지정된 for문
  --> logn은 n보다 적은 시간이 걸림을 상징적으로 보여주는 것
• O(nlogn) : 선형로그시간 ex) while문
• O(n!) : 팩토리얼
• O(n+k)

정렬

배열을 최소에서 최대의 순으로 정렬

1. 선택 정렬 - O(n제곱)

• 최대 원소를 찾아 맨 오른쪽 원소와 교환 -> 다음에는 맨 오른쪽을 제외하고 교환 -> 하나 남을때 까지 반복

2. 버블 정렬 - O(n제곱)

• 처음부터 2개씩 비교해서 큰거를 오른쪽으로 보냄 -> 반복

3. 삽입 정렬 (insertion sort) - O(n제곱)

• 첫 원소부터 한 원소씩 나아가면서 들어가야할 index에 insert
• 수학적 귀납법과 같다 (아직 이해하지 못함)

4. 병합 정렬 (merge sort) - O(nlogn)

• 배열의 두개로 쪼개서 각각 sort를 진행 -> 원소가 하나일때 까지 재귀함수로 계속 쪼갬 -> merge함수로 병합
• 배열을 반으로 나누기 때문에 O(logn) + 재귀를 원소의 수만큼 진행하기 때문에 O(n)

5. 퀵 정렬 (quick sort) - O(nlogn)

• 병합정렬과 비슷하지만 다른 점은 partition : 한 수를 기준으로 삼고 그 수보다 작은수는 왼쪽 큰수는 오른쪽에 할당 -> 왼쪽 오른쪽 배열 모두 독립적으로 정렬 (기준점은 처음부터 시작해서 오른쪽으로 이동)
  

6. 카운팅 정렬 (counting sort) - O(n+k)

• 정렬할 배열의 min, max값을 알고 시작해야 함 (비교적 적은 수의 배열에 적합)
• range(min, max+1)에 해당하는 리스트 생성 -> 각 수의 개수를 리스트에 넣음 -> 누적 개수 리스트도 생성 -> 누적개수를 활용하여 인덱스에 넣고 -1하는 방식으로 정렬
• 배열의 숫자가 다른 고유값을 가지고 있는 경우 활용됨 ex)지윤:1, 익선:1, 지우:2
• 수의 종류 O(n) + 리스트의 갯수O(k) : 다른 알고리즘은 리스트가 1개인것에 비해 카운팅 정렬은 1+3(개수리스트, 누적리스트, 정렬리스트)개가 생성된다. 시간 복잡도에 유의.
  

순환(Recursion 순열과 조합)

팩토리얼, 피보나치, 하노이탑, 이진수출력, 조합출력, Rn
-pick 함수: n개의원소에서m개를뽑아야하는데이미고른것은picked 안에넣었고, 앞으로toPick개수만큼고르는함수라고가정. (앞으로 만나게 될 문제에서 다시 정리)