[개념] 순차, 이분검색 & 피보나치 수(자세히)

순차 검색과 이분 검색은 배열에서 원소를 찾는 대표적인 알고리즘이며, 피보나치 수열은 재귀와 DP 방식으로 구현할 수 있습니다. 이 글에서는 각 알고리즘의 특징, 시간 복잡도, 그리고 피보나치 수를 구하는 여러 방법(일반적인 방법, 행렬 제곱 방법, 모듈로 연산)을 자세히 설명합니다.

순차 검색, 이분 검색의 특징과 피보나치 수에대해 설명

• 피보나치 수를 구하는 방식이 한가지가 아니며, 다른 방법도 알아보겠음

순차검색, 이분검색

• 순차검색 : 처음부터 순서대로 검색(순회)하는 알고리즘
  • 문제 : 크기가 n인 배열 S에 x가 있는가?
  • 최악의 복잡도 : 전체를 차례대로 순회하기 때문에 N
• 이분검색 : 2로 나눈 절반의 위치로 검색(순회)하는 알고리즘
  • 문제 : 크기가 n인 정렬된 배열 S에 x가 있는가?
  • 최악의 복잡도 : 전체를 절반 씩 찾아가서 순회하기 때문에 logN

n번째 피보나치 수

일반적인 방법

• 즉, 바로 앞에 2개의 숫자를 더한 값이 현재 값이 되는게 피보나치 수열이다.

또 다른 방법

%(나머지)를 이용해서 숫자 앞자리는 무시하고 뒷자리 만으로 계산해서 구하는 방식

• 이 공식을 이용하면 큰 숫자도 간단히 구할 수 있다.

예제

풀이

• 참고로 0 1 행렬을 곱해주면 처음 n=199인 행렬에서 당연히 n=200이 행렬이 되는 특징을 이용 1 1

참고 : 200제곱x200제곱=400제곱 이라는 단순한 수학계산이지만 이 아이디어로 복잡도를 대폭 줄이는 경우들이 존재하기 때문에 기억하고있으면 좋음

알고리즘 방식

재귀, DP 방식이 존재하며 DP 방식이 중복 계산이 없기 때문에 속도가 훨씬 빠르다.

• 재귀는 만약 f(9)를 구한다면, f(0)부터 f(8)까지 다시 계산해서 다 구해야하기 때문 -> 중복 계산
• DP는 만약 f(9)를 구한다면, 이미 전역 배열에 기록해둔 f(7), f(8)을 바로 사용해서 계산