우아 한의원 | 조재성 원장의 한의학, 의학통계, 프로그래밍

이 글은 코드잇의 알고리즘 강의와 오픈소스들을 참고하여 정리한 글입니다^^

선형탐색 알고리즘 평가하기

각 변수선언, 함수들을 한 줄씩 보면, 모두 리스트의 크기(n)과는 상관없이 일어나므로 O(1)이 소요된다.

while 반복문 또한, 한번 일어났다고 가정하면, n과 관계없으므로 반복횟수 X O(1)이 소요된다.

이 때, Best 경우 반복문 1번만에 = 첫 원소가 찾는 element인 경우,
걸리는 시간은 4 * O(1) = O(4) 역시 O(1)라 할 수 있다.

최악의 Worst 경우 반복문 n(0~n-1)번 돌아도 찾는 element가 리스트에 없는 경우로서,
걸리는 시간은 3*O(1) + O(1)*n이며, O(1) * n은 O(n)으로 나타낼 수 있다. ( 리스트의 개수만큼 반복된다. n이 관여)
즉, O(n +3)이 된다. 하지만, 점근표기법에서는 3은 없애줘도 되므로 O(n)이 된다.

이진탐색 알고리즘 평가하기

Best의 경우는 아래와 같이 반복문이 1번 도는 시간으로서, O(4) = O(1)이다.

하지만, 이진탐색의 Worst(리스트에 없는 경우) 는 반복문이 몇번 돌까?

loga(b) = x 와 log2(x) = y의 의미 :

    혹은 b를 a로 몇번 나누어야지 1이 되는가? 이다.
    컴퓨터 알고리즘 문제에서는 a가 2인 경우가 많다.
    log2(16)은 16을 2로 몇번 나누어야(몇번 반토막내야) 1이 나오는지 생각해보면, 4번이다.
    예를 들어, 길이가 16인 리스트가 있다면, 총 4번 반토막 내어야한다.

리스트의 원소길이 n 을 2로 몇번나누어야 1이 나오는지 횟수 = log2(n) 으로 나타낸다.
즉, lg(n) = n(리스트의 길이)를 몇번을 2로 나누면 1이 나오는지 = 몇번 반토막 내면 1이 나오는지라고 하였다.

그렇다면, 이진탐색의 Worst는 [ 반복문1회(O(1)) * lg(n) ] + O(3) = O(lg(n))이다.

정리하자면, 아래와 같다.

알고리즘에서는 보수적이라 최악의 경우를 자주 살핀다. 그러므로 아래와 같이 부른다.

1. 선형탐색 = Big-O of n 알고리즘
2. 이진탐색 = Big-O of lg(n)알고리즘

나의 정리

1. 알고리즘 최악의 경우는 element가 list에 없어서 반복문(회당 O(1))을 모두 돈 경우로서, n과 관련된다.
2. 선택탐색은 n번 / 이진탐색은 log2(n)번 반복문을 돈다. ( n은 리스트의 원소 개수)

알고리즘 평가시 주의사항

코드의 모든 줄은 O(1)인가요?

아닙니다!
인풋 크기와 상관 없이 실행되는 코드만 O(1)입니다. 그렇지 않은 코드는 시간 복잡도를 따져봐야 합니다.
예를 들어서 sorted 함수나 list.sort 메소드를 사용하면 내부적으로 O(nlgn)의 정렬이 이루어집니다.

만약 리스트에서 in 키워드를 통해 값의 존재 여부를 확인하면 내부적으로 O(n)의 선형 탐색이 이루어집니다.

파이썬의 내장된 정렬 알고리즘은 timsort라는 것입니다. 최악 or 평균의 경우 O(n lg n), 최고의 경우 O(n)이라고 하네요.
합병 정렬과 퀵 정렬도 평균 O(n lg n)입니다.

이 글은 코드잇의 알고리즘 강의와 오픈소스들을 참고하여 정리한 글입니다^^

알고리즘 평가의 2가지 기준

1. 시간 : 빨리빨리 => 더 중요
2. (메모리)공간 => 돈 주고 사면 됨

시간 복잡도(Time Complexity)

컴퓨터 과학에서 알고리즘의 시간평가 방법

• 걸리는 시간으로는 판단x
  
  

• 데이터(리스트의 원소 개수)가 많아질수록 걸리는시간이 얼마나 급격히 증가하는지
  예를 들어, 리스트의 원소 개수가 10개, 20개, 100개 -> 걸리는 시간 10, 20, 100초라면 -> 걸리는 시간 일정하게 증가
  

  그러나 알고리즘 B는 걸리는 시간 증가량이 급격하다
  

  A보다 B의 시간복잡도가 크다.! = A 알고리즘이 시간 복잡도가 더 작은 빠른 알고리즘
  

시간복잡도 계산을 위한 거듭제곱과 로그

거듭제곱 (Exponentiation)

• 패턴을 따라가다보면 2의 -1승은 2의 0승(1) / 2 이므로 1/2 임을 알 수 있다.
  
  

로그 (Logarithms)

• a는 밑수 b는 진수 라 부른다.

• 편하게 생각하기 위해서는 a를 몇번(x) 곱해야 b가 나오는지로 생각한다.
  

• 혹은 b를 a로 몇번 나누어야지 1이 되는가? 이다.

• 컴퓨터 알고리즘 문제에서는 a가 2인 경우가 많다.

• log2(16)은 16을 2로 몇번 나누어야(몇번 반토막내야) 1이 나오는지 생각해보면, 4번이다.

• 예를 들어, 길이가 16인 리스트가 있다면, 총 4번 반토막 내어야한다.
  그림으로 예를 들면,
  

  이 상태에서 총 4번을 반토막 내야 1이 된다.
  
  
  
  

  log2( ) 를 lg로 쓰기도 한다.
  

시간복잡도 계산을 위한 1부터 n까지의 합

1부터 n까지의 합을 나열하여 T라 나타내고, 밑줄에 반대로 나열해놓고 더하자

2T = n * (n+1)
T= n(n+1) /2

점근 표기법 (Big-O Notation)

알고리즘은 일반적으로 걸리는시간(X) 인풋에 따라 걸리는 시간의 증가량에 의해 평가된다고 하였다.

하나의 알고리즘은 인풋에 따라 걸리는 시간이 달라진다.
즉, 알고리즘 소요시간 = 인풋크기(n)의 수식으로 나타낼 수 있다.

예를 들어, 아래 리스트를 인풋한다고 가정했을 때 리스트의 길이(n)라면,
알고리즘 소요시간 = 20n+40 or 2n^2 + 8n +157 일수도 있다.

그러나 n에 붙은 숫자들은 컴퓨터의 환경적인 것들에 의해 달라진다.

즉, 수식하나가지고는 하나의 알고리즘을 완벽하게 나타내지는 못한다.

그래서 컴퓨터 과학자들이 다같이 약속한 것이 점근표기법으로 알고리즘을 평가하자는 것이다.

점근표기법의 룰

1. 만약, 소요시간이 20n+40이라면?

   • n의 영향력이 작은 40 삭제(영향력 젤 큰 항만 남김) -> n앞에 계수 삭제 -> n만남아서 O(n)으로 표기
   • 해당 알고리즘을 Big-O of n 알고리즘이라 부른다.
     

2. 소요시간이 2차식이라면?

   • 가장 영향력이 큰 2n^2 만 남김 -> 앞에 계수 삭제 -> O(n^2)
   • Big O of n^2 알고리즘
     

3. 20lg(n) + 60 ?

   • 60 없앰 -> 20없앰 -> O(lg(n))
   • Big O of lg(n) 알고리즘
     

점근표기법을 위와 같이 표기하는 이유?

점근 표기법의 핵심 : n이 엄청 크다고 가정 -> my)낮은차수와 계수는 무시된다.
절대적인 시간보다는 성장성을 보기위함이다.

• n(input, 리스트의 길이, 원소의 개수)가 얼마 안되면, 굳이 좋은 알고리즘을 쓸 필요가 없다.
  
• 골치 아픈 경우는, n이 엄청 컸을 때의 알고리즘이다.

만약, 한 알고리즘의 소요시간이 n(리스트의 길이)에 대한 수식으로 2n^2 + 8n + 157로 나타났다고 가정하자.
그리고 2n^2 과 점근표기법에서 삭제되는 8n+157을 n에 대한 소요시간 그래프로 나타내보자.

• 처음에는 8n+157의 소요시간이 더 크더라도, 나중에는 2n^2의 소요시간이 압도적으로 커진다.
  

• n이 100만 정도로 엄청 커졌을 때, 차이는 두드러진다. 즉, n이 엄청 크다고 가정하면 영향력이 작은 부분은 그냥 무시해버리는 것이 핵심이다.
  

• 2n^2이 아니라 0.01n^2이라면??? -> 결과적으로 계수도 무시해도 된다
  

점근표기법의 의미

O(1) : Big-O of 1 알고리즘은 인풋사이즈(n)에 영향받지 않고 일정하게 1초가 걸린다.

O(n) : 인풋(n) 증가량(n배)과 소요시간이 비례(n배)해서 증가한다.

• 리스트 크기가 100 -> 1초, 200 -> 2초...
  

O(n^2) : 인풋(n) 2배 -> 소요시간(n^2) 4배 증가
O(n^3) : 인풋이 n배 -> 소요시간 n^3배 증가

n이 1000까지라면,,,

n이 10000까지라면,,, 더 차이가 난다.

• O(n^3)은 너무 오래걸리니 안좋은 알고리즘이다.
  

같은 컴퓨터가 아니라... 오래걸리는 알고리즘에 최고사양 컴퓨터를 배정한다면? 소요시간이 더 줄 수 있다.

그러나, 이것은 리스트의 길이가 적을 때의 이야기이다.
BigO의 핵심은 n이 무수히 크다고 가정하는 것이고,
그 상태에서는 리스트의 길이(n)이 증가함에 따라 소요시간(n) 폭팔적으로 증가하여, 결국은 n의 차수가 높은 O(n^3)이 가장 오래 걸릴 것이다.

즉, 컴퓨터 사양이 아무리 좋아도, 빠른 언어를 사용하여도,
결국 알고리즘이 별로면, 싸구려 컴퓨터보다 느려진다.

이글은 코드잇의 알고리즘 강의와 오픈소스들을 참고하여 정리한 글입니다^^

정렬(Sorting) : 리스트의 원서들을 특정 순서로 정리하는 것

• 오름차순, 내림차순, 알파벳순
• python에는 이미 sorted( list ) 내장함수나 리스트의 list..sort() method도 있다.

그냥 sorted()나 .sort()를 쓰면 될 것 같으나 정렬을 왜 배워야 할까?
그 이유는 정렬 자체가 알고리즘의 기초 & 모든 개발자가 알아야할 가장 기본적인 알고리즘이기 때문이다.

1. 선택 정렬(Selection Sort) : 각 인덱스에 들어갈 값들을 찾아서 정렬하는 알고리즘으로서,
   가장 작은 값 -> 0번 인덱스
   2번째 작은 값 -> 1번 인덱스
   3번째 작은 값 -> 2번 인덱스 ... 방식으로 정렬한다.
   예를들어,
   

   • 0번 인덱스에 넣어줄 가장 작은 값을 찾기위해, 0~5번 인덱스의 값들을 확인한 뒤 넣어준다.

   • 0번 인덱스의 값을 볼때는, 4가 가장 최소값이다.

   • 1번 인덱스의 값을 볼때는, 2가 가장 최소값이다.

   • 3번 인덱스의 값을 볼때는, 1가 가장 최소값이다.

   • 5번 인덱스까지 1회전 다봤으면,
     0번 인덱스의 값 <-> 3번 인덱스의 값(최소값)을 교체한다.

   • 이제 1번 인덱스에 들어갈 값을 찾기위해서, 1 ~ 5번 인덱스까지 값을 보고 가장 작은 값과 교체해준다.

   • 마찬가지로 2번 인덱스 -> 2~5번 인덱스의 값 탐색 후 가장 최소값 넣어주기 -> 반복한다.

2. 삽입 정렬(Insertion Sort) : 각 값이 어떤 인덱스에 들어가야할지 찾는 알고리즘으로서,
   예를 들어, 카드 게임을 한다고 할 때, 이미 정렬된 카드를 가지고 있는 상태에서 딜러가 새로운 카드를 줬을 때, 새로운 카드를 올바른 위치에 삽입(끼워넣는)한다.

my) 0과1 정렬/ 0,1,2 정렬/ 0,1,2,3 정렬 하는데, 마지막값을 기준으로 왼쪽으로 차례차례 비교해나간다.


아래와 같은 리스트가 있다고 가정하자.

- 먼저, 0번과 1번 인덱스의 값만 보고, 정렬한다.

- 다음으로, 0,1,2번 인덱스의 값을 보고, 정렬한다.

- 다음은, 0,1,2,3번 인덱스의 값을 보고 정렬한다. 이 때, 3값<->2값, 2<->1값, 1값<->0값순으로 한번씩 비교하는 것 같다.





- 마지막 5번인덱스의 값 3은,
(1) 9와 비교해서 왼쪽,
(2) 7과 비교해서 왼쪽,
(3) 4와 비교해서 왼쪽, 총 3번을 한칸씩 움직인다.

참고)

• 이미 거의 정렬된 리스트를 정렬할 때는 삽입 정렬(Insertion Sort)이 가장 빠른 반면,
• 아예 정반대로 정렬된 리스트의 경우에는 삽입 정렬이 매우 오래 걸린다는 것도 볼 수 있죠.
• 선택 정렬(Selection Sort)과 합병 정렬(Merge Sort)은 상황에 영향을 받지 않고 일정한 시간이 소요된다는 점도 주목해 볼 만합니다.
• 무작위 순서의 리스트를 정렬할 때는 힙 정렬(Heapsort)이 가장 먼저 끝나네요.

구현시 참고 블로그 : http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html

이글은 코드잇의 알고리즘 강의와 오픈소스들을 참고하여 정리한 글입니다^^

알고리즘 공부 방법

하나의 문제를 해결하는 방법에는 여러가지가 있다. 그 방법들을 찾아서 가장 좋은 방법을 찾는 것이 알고리즘 공부 방법이다.

예를 들어, 책장에서 원하는 책을 찾는 방법 2가지 방법을 확인해보자.

1. 왼쪽부터 하나씩 확인하다가 찾기
   

2. 책이 알파벳순으로 정렬되어 있다는 것을 활용하여,
   (1) 전체 중 중간을 선택한 뒤, 원하는 책이 앞인지 / 뒤인지 확인하기
   

   (2) 남은 책들 중에 중간지점을 선택한 뒤, 확인하기
   
   (3) 이렇게 반씩 줄이는 것을 반복하다보면 원하는 책을 찾을 수 있다.
   

탐색문제

위에서 살펴보면 문제는 탐색문제이다.
탐색이란? 저장된 정보들 중에 원하는 값을 찾는 것이다. ex> 파이썬 숫자 리스트 중 특정값 찾기

탐색문제 해결방법 2가지

1. 선형 탐색 알고리즘(Linear search algorithm) : 순서대로 하나하나씩 찾기
2. 이진 탐색 알고리즘(Binary search algorithm) : 반씩 제외시키면서 찾기

1. 선형 탐색 알고리즘 : 순서대로 하나하나씩 찾기

   • 왼쪽부터 하나하나씩 원하는 값을 찾아본다.
     

   • 원하는 값 발견시, 더이상 안보고 끝낸다.
     

2. 이진 탐색 알고리즘 : 반씩 제외하면서 찾기

   • 중간지점(중간값)을 먼저 선택한 뒤, 왼쪽 or 오른쪽만 남긴다.
     

   • 남은값들 중에 중간값을 선택(여기서는 그냥 왼쪽것을 선택)하고, 왼쪽or오른쪽 남기기
     

   • 반복해서 찾아가기
     
     

2가지 탐색문제 해결방법 중 어느 것이 더 효율적일까??

탐색 알고리즘 2개 비교

16개의 원소를 가지고 있는 리스트가 있다고 가정하고, 얼마나 걸리는지 한번 생각해보자.

선형탐색의 경우, 언제 가장 빨리 마치고/ 언제 가장 늦게 마칠 까?

• 정답이 리스트 첫 원소인 경우 -> 1번걸림
  

• 정답이 마지막 원소이거나 없는 경우 -> 16번걸림
  

이진탐색의 경우, 가장 빨리 되는 경우는

• 정답이 가운데( 0 + 15 // 2) 있는 경우 -> 1번
  
• 정답이 없는 경우 = ex> 0을 찾는 경우 -> 4번
  
  
  
  

이진 탐색의 경우 최악의 경우시 4번만 봐도 되지만, 선형 탐색은 16번 다 봐야한다.

최악의 경우를 일반화 해보면, n개의 원소 리스트는

• 선형탐색 -> n번
• 이진탐색 -> 2^m = n의 m번 걸린다.
• 리스트의 길이가 길어지더라도, 이진 탐색은 걸리는 시간이 아주 천천히 늘어난다.

언제 선형탐색을 쓸까???

이진 탐색의 전제조건은 정렬된 리스트-이진탐색이다.
만약, 리스트가 정렬되지 않은 상태라면 정렬x리스트-선형탐색을 쓸 수 밖에 없다.