크래프톤정글 1주차; 알고리즘, 재귀함수, 정렬, 완전탐색

참고: 부스트코스 CS50 모두를 위한 컴퓨터과학
에드위드 파이썬으로 배우는 알고리즘 기초

알고리즘

1. 알고리즘 표기법

1. 빅O와 빅Ω
   1. 빅O
      1. 알고리즘 실행 시간의 상한
      2. 최악의 경우! (즉, 자료가 맨 마지막 경우에 발견되거나, 리스트 안에 없는 경우)
      3. O는 "on the order of"의 약자 → "~만큼의 정도로 커지는"
      4. 알고리즘별 일반적인 빅O
         • O(n²) - 버블 정렬, 선택 정렬, 삽입 정렬(정렬이 하나도 안 된 경우)
         • O(n log n)
         • O(n) - 선형 검색
         • O(log n) - 이진 검색
         • O(1)
   2. 빅Ω
      1. 알고리즘 실행 시간의 하한
      2. 운이 좋은 경우!
      3. 알고리즘별 일반적인 빅Ω
         • Ω(n²) - 버블 정렬, 선택 정렬
         • Ω(n log n)
         • Ω(n) - 배열 안에 존재하는 값의 개수 세기, 버블정렬(이미 정렬된 경우), 삽입정렬(정렬이 좀 된 경우)
         • Ω(log n)
         • Ω(1) - 선형 검색, 이진 검색
   3. 빅O와 빅Ω의 비교
      • 최악의 경우일때 더 나은 알고리즘, 즉 상한선이 낮은 알고리즘이 좋음 (평균적으로, 일반적으로 계산했을 때의 경우가 더 중요하단 것. 안전빵 개념.)

2. 알고리즘 설계 종류

1. Brute-force (단순무식): 선형검색 같은 거
   1. 백트래킹
   2. 분기한정정
2. divide-conquer (분할, 정복): +필요하면 통합까지! 탑다운 방식, 작은 입력 사례를 각각 정복하는데 작은 입력 사례가 충분히 작지 않으면 재귀 호출
3. greedy(탐욕법): 가장 비효율적인 분할정복 알고리즘
4. dynamic programming(동적계획): 바텀업 개념

3. 검색 알고리즘

1. 검색 알고리즘이란?
   2. 주어진 "배열" 속에서 특정 값을 찾는 방법
   3. 배열은 자료형의 여러 값들이 메모리상에 모여 있는 구조
   4. 컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나를 접근
   5. 배열이 정렬되어 있는지 여부가 중요해짐!
2. 선형 검색linear serach
   1. 선형 검색의 특징
      1. 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사
      2. 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색
      3. 정확하지만 아주 효율적이지 못한 방법
      4. 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용
      5. 효율적인 검색을 위해서는 "정렬"이 그래서 중요함 → but 정렬은 시간이 오래 걸리고 공간을 더 차지 → 여러번 검색해야 하는 경우, 더 큰 리스트를 검색해야 하는 경우를 위해서는 필요할 수 있음
      6. 검색을 위해 구조체를 정의하면 편리할 수 있음
   2. 슈도코드

      For i from 0 to n–1
      If i'th element is 50
      Return true
      Return false

3. 정렬 알고리즘

1. 정렬 알고리즘이란?
   1. 말 그대로 정렬을 위함
   2. 정렬해서 더 쉽게 검색하기 위함임!
2. 버블 정렬 (bubble sort)
   1. 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬
   2. 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬
   3. 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수 있음
   4. 버블 정렬시 교환이 하나도 이루어지지 않는다면 이미 정렬되어 있다는 의미 → 교환이 일어나지 않을때까지만 루프가 발생하게 수정한다면 버블 정렬의 하한은 Ω(n)이 됨
   5. 슈도코드

      Repeat n–1 times
          For i from 0 to n–2
              If i'th and i+1'th elements out of order
                  Swap them

   6. 상한 시간: O(n²)
   7. 하한 시간: Ω(n²)
3. 선택 정렬 (selection sort)
   1. 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환
   2. 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가
   3. 슈도코드

      For i from 0 ton–1
      Find smallest item between i'th item and last item
      Swap smallest item with i'th item

   4. 상한 시간: O(n²)
   5. 하한 시간: Ω(n²)
4. 삽입 정렬 (insertion sort)
   1. 정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법
   2. 1번째 원소부터 0번째 원소와 비교하여 정렬하기 시작 → 다음 단계가 진행되며 기존의 자료들의 위치가 바뀔 수 있음
   3. 자료의 양이 적을 때 성능이 우수하며 자료 대부분이 이미 정렬이 되어있는 경우 효율적
   4. 이미 정렬된 자료에 새로운 자료를 삽입해야 하는 경우가 발생하면, 정렬된 자료들이 자리를 이동해야 하므로 안정성이 낮음
   5. 생각해보니 내가 일상 생활에서 많이 쓰는 정렬!
   6. 슈도 코드
      
   7. 상한 시간: O(n²)
   8. 하한 시간: Ω(n)
5. 병합 정렬 (merge sort)
   1. 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식
   2. 버블, 선택 정렬보다 빠름 but 이미 정렬되어 있다면 버블 정렬(O(n))보다는 느림
   3. 상한 시간: O(n log n) → 숫자를 반으로 나누는 데
   4. 하한 시간: Ω(n log n) → 나눈 부분을 다시 정렬하여 병합할 때
6. 퀵 정렬 (quick sort)
   1. 대표적인 분할정복 알고리즘
   2. 내부정렬(in-place) 방식 (추가적인 temp 리스트가 필요하지 않음)
   3. 병합 정렬과 다른 점은 병합 정렬은 반으로 자르는 기준이 N/2라면, 퀵 정렬은 기준원소(pivot)을 정해서 그걸 기준으로 좌우 분할함 (바로 이 부분이 효율성과 성능을 향상시켜줌)
   4. 이때, 피봇을 정하는 것이 중요함!
   5. 정렬이 많이 되어 있는 함수일수록 성능이 떨어짐..! → 랜덤할 수록 성능이 나아지기 때문에, 피봇을 정할때 아무거나 랜덤으로 찍는게 좋음

재귀함수 recursive function

1. 자기 자신을 호출하는 함수
2. 재귀 종료 조건이 존재하여, 종료 조건까지 함수 호출을 반복함
3. 함수 안에 그 함수를 또 써주면 됨 (무한 루프를 조심)
4. 반복문을 재귀 함수로 바꾸어 표현할 수 있음 (재귀 개념은 fractal을 떠올리게 함!)
5. 재귀 함수의 구조
   1. 멈추어야 하는 조건은 1회 이상 하드코딩 해주어야 함 → 안 그런 경우 무한히 재귀 함수를 호출하며 스택 오버플로우 현상이 일어날 것!
      (스택 오버플로우: 재귀함수처럼 자기 자신을 계속 호출하는 함수를 쓰다 보면, 점점 메모리 영역이 위로 늘어나며 힙 영역을 침범)
   2. 마지막 완성 전 한 스텝 뒤를 재귀 함수로 호출
   3. 그리고 완성을 위한 마지막 스텝에서 해주어야 할 과정을 수행문으로 작성하면 됨