참고 자료는 다음과 같습니다.
- 파이썬 자료구조와 알고리즘 (한빛미디어, 2019)
검색
검색 알고리즘 : 순차 검색, 이진 검색이 있음
○ 순차 검색 : 배열이 정렬되어 있지 않거나, 연결 리스트 같이 입력이 동적으로 할당되는 경우 사용
● 시간복잡도 : O(1)로 최악의 경우 O(n)임
○ 이진 검색
● 정렬된 배열 내에서 지정된 입력값의 위치(키)를 찾음
● 각 단계에서 입력값과 배열 중간 요소 비교하여 일치 안할 때 값의 크기에 따라 왼쪽 또는 오른쪽 하위 배열에서 검색과정 반복.
● 시간 복잡도 : O(log n)
동적 계획법
동적 계획법
○ 복잡한 문제를 재귀를 통해 간단한 하위 문제로 분류해 단순화하여 해결하는 방법
○ 어떤 문제가 최적 부분 구조와 중복되는 부분 문제 가지면 동적 계획법으로 해결 가능
● 최적 부분 구조 : 답 구하기 위해 사용한 계산 반복해야 하는 문제 구조
○ 부분 문제를 풀고 결과 저장 후 다음 부분 문제 푸는 과정에서 사용
메모이제이션(memoization)
○ 프로그램이 동일 계산 반복시, 이전에 계산한 값을 메모리에 저장해 동일한 계산 반복 수행을 제거해 프로그램의 실행 속도 빠르게 하는 방법
사례
○ 피보나치 수열
○ 최장 증가 부분열 : 증가하는 순서(오름차순)로 숫자를 고른 부분열 길이가 최대가 되게 하는 방법
