[Hello Coding 알고리즘] 1. 알고리즘 소개

[Hello Coding] 알고리즘 1장. 알고리즘의 소개

알고리즘이란?

: 어떤 일을하기 위한 명령의 집합.
특히 다른 코드보다 속도를 빠르게 하거나, 문제를 풀기 위한 것.

알고리즘의 성능

• 여러 알고리즘들의 장단점과 차이점을 알아야 한다.
• 단순히 다른 자료구조/알고리즘을 사용하는 것만으로도 성능이 크게 달라진다.

이진 탐색

탐색 문제 Search

: 주어진 데이터에서 원하는 항목을 어떤 방법으로 찾을 것인가.
예) 1부터 100까지의 숫자들 중 '78'이라는 숫자 찾기

단순 탐색 Simple search

: 처음부터 하나씩 순서대로 항목을 탐색
예) 1, 2, 3, 4, ... 77, 78 순으로 탐색해 78을 찾는다.

• N개의 원소를 가진 리스트에서 최대 N번 만에 답을 찾을 수 있다.

이진 탐색 Binary search

• 정렬된 원소 리스트에서,
• 원하는 원소가 있으면 그 원소의 인덱스를 반환 / 없으면 null을 반환.
• N개의 원소를 가진 리스트에서 최대 log2 N번 만에 답을 찾을 수 있다.

이진 탐색의 동작원리

: 리스트의 중간 값을 기준으로 중간 값보다 큰지/작은지/같은지 판단해, 범위를 줄여가면서 반복 탐색한다.

예시)
1부터 100까지의 숫자들 중 57의 인덱스 찾기

• 50이라는 중간값보다 큰지 작은지 판단 -> 크다.
• 1-50은 범위에서 제외한 다음, 51-100 의 중간인 75보다 큰지 작은지 판단한다. -> 작다.
• 75-100은 범위에서 제외한 다음, 51-74 의 중간인 63보다 큰지 작은지 판단한다.
• ... 를 반복해 답을 찾는다.

1-100 중 어떤 숫자라도 최대 7번 만에 찾을 수 있다.

실행 시간 running time

우리는 시간이나 저장공간을 절약해 주는 가장 효율적인 알고리즘을 찾고 싶어 한다.

선형 시간 linear time

: 단순탐색과 같이, N개 중에서 찾을 때 최대 N번 만에 찾을 수 있는 경우 선형 시간으로 실행된다고 한다.

로그 시간 logarithmic time

: 이진탐색과 같이, N개 중에서 찾을 때 최대log2 N번 만에 찾을 수 있는 경우 로그 시간으로 실행된다고 한다.

빅오 표기법 Big O notation

: 알고리즘이 얼마나 빠른지 나타내는 표기법이다.

• 알고리즘의 속도를 시간이 아닌 연산횟수가 어떻게 증가하는지로 측정한다.
  즉 알고리즘이 동작하기 위해 필요한 최대 연산 횟수를 나타낸다.
• 빅오 표기법은 최악의 경우를 나타낸다.
  단순탐색의 경우) 아무리 느려져도 O(n)보다 느려지진 않음을 의미한다.

예를 들어..

리스트 크기가 n일 때 어떤 원소를 찾으려면

• 단순 탐색
  : n번 연산해야 한다 - O(n) 만큼 걸린다고 표기한다.
  (O(n) : n이라는 결과를 위해 n번 연산해야 함을 의미)

• 이진 탐색
  : log2 n번 연산해야 한다 - O(log n)만큼 걸린다고 표기한다.
  (O(log n) : n이라는 결과를 위해 log2 n번 연산해야 함을 의미)

빅오 표기법에서 log는..

빅오 표기법에 나타난 모든 log함수는 log2 (밑이 2인 로그)를 뜻한다.

많이 사용하는 빅오 실행시간

많이 사용하는 빅오 실행시간을 다섯 개만 알아본다.

• O(log n) , 로그 시간
  : 다섯 개 중 가장 빠르다.
  이진 탐색과 같은 경우.
• O(n), 선형 시간
  : 다섯 개 중 두 번째로 빠르다.
  단순 탐색과 같은 경우.
• O(n * log n)
  : 다섯 개 중 세 번째로 빠르다.
  퀵 정렬과 같은 경우.
• O(n2) (n제곱)
  : 다섯 개 중 네 번째로 빠르다.
  선택 정렬과 같은 경우.
• O(n!) (n팩토리얼)
  : 다섯 개 중 다섯 번째로 빠르다 (가장 느리다).
  외판원 문제와 같은 경우.