Algorithm

=> 어떤 문제를 푸는 알고리즘 = 어떤 입력에도 정확한 출력을 유한한 시간에 내는 프로그램"어떤 입력" - 문제가 풀기 쉽든, 여렵든, 입력의 크기가 작건, 크건 문제를 풀 수 있다.어떤 경우에는 정답을 내지 못한다면 우리가 이 프로그램을 믿고 쓸 수 있겠는가?"정확

탐색 문제 2의 최적성 이진 탐색의 경우, n = 2^k 로 가정하면 T(n) = 1+T(n/2) = 1 + (1+T(n/4)) = 1+1+(1+T(n/8)) = 1 + ... + 1 + T(n/2k) = k + 1 = O(log n)번 비교 => 반으로 나눠서

n개의 서로 다른 수가 주어졌을 때, 이들을 이동하여 점점 커지게, 또는 점점 작아지게 만드는 문제.\-> 한 문제를 풀기 위해서 여러가지 방법이 가능\-> 방법마다 특징이 다름\-> 기본적인 문제이면서, 실생활에 자주 쓰임\-> 시간 복잡도, 최적성에 대해서 증명이

가장 좋을 때: 기준의 왼쪽, 오른쪽에 같은 수의 원소가 이동함\-> T(n) = 2T(n/2) + n\-> T(n) = O(n log n)가장 나쁜 경우: 기준의 왼쪽 또는 오른쪽 한 쪽으로만 원소가 쏠림\-> T(n) = T(n-1) + n\-> T(n) = O(n