알고리즘 스터디 1

01 재귀호출

• 재귀호출은 함수 내부에서 자기 자신을 호출하는 방법

02 완전 탐색

• 가능한 모든 경우를 살펴보는 과정을 완전 탐색이라고 한다.
  
  

시간복잡도

시간복잡도란?

• 코드가 동작하는데 걸리는 시간을 수학식으로 표현한 것
• 낮은 시간복잡도를 가질수록 좋은 알고리즘

상수 시간복잡도

• 실행이 단번에 완료되면 상수 시간복잡도
• 상수 시간에 처리되는 시간 복잡도를 O(1)로 표현

로그 시간 복잡도

• 수학적으로 log(n)에 비례한다고 하고, 로그 시간복잡도라고 한다.
• ex)
  n이 10^2 이라면 3번 출력, 10^5이라면 6번 출력된다. 즉, log(n)에 비례해 수행 시간이 달라짐
• O(log(n))으로 표현

선형 시간 복잡도

• 매개변수 n의 크기에 비례하여 소요 시간이 결정
• ex)

  

• O(n)으로 표현

선형 제곱 시간 복잡도

• 매개변수 n의 제곱 값에 비례하여 소요 시간이 결정
• ex)

  

• O(n^2)으로 표현

03 분할 정복법

• 주어진 큰 문제를 작은 문제로 분할해서 작은 문제를 하나씩 해결함으로써 큰 문제를 해결하는 프로그래밍 기법
• 한 번에 해결하기 힘든 문제를 작은 단위의 문제로 나누어 해결하는 방법

퀵 정렬 알고리즘

• 퀵 정렬은 주어진 리스트를 빠르게 정렬하는 알고리즘

  1. array[0] 값을 기준값(pivot)으로 설정
  2. pivot을 기준으로 더 작거나 같은 값이 들어있는 리스트와 더 큰 값이 들어있는 리스트로 나눔
  3. 그리고 less_or_equal, pivot, greater 순서로 리스트를 정렬
  4. less_or_eqaul과 greater 리스트에 대해서도 지금까지의 작업을 반복하면 정렬이 완성

합병 정렬 알고리즘

• 합병 정렬(merge sort)도 퀵 정렬처럼 큰 리스트를 작게 분할하며 빠르게 정렬하는 알고리즘

  1. 합병 정렬은 값을 비교하지 않고 리스트를 분할
  2. 나눈 리스트를 또 각각 절반으로 분할
  3. 남아있는 리스트의 길이가 0이나 1이면 분할을 멈추고 리스트를 정렬하며 합침
  4. 10과 2를 정렬하고 합치면
  5. 1과 7을 정렬하고 합치면
  6. 이러한 작업을 계속해나가면 처음의 리스트가 정렬된다.

분할 정복법의 장점

• 퀵 정렬과 합병 정렬은 낮은 시간 복잡도를 가짐

04 탐욕적 기법

• 주어진 작은 순간마다 목적에 맞는 최적의 선택을 내려 결과적으로 전체적인 결과에서 최적의 선택을 끌어내는 방식