정신차려 하프물범 정신차려 하프물범

최적의 해를 구하기에 시간이 너무 많이 걸리거나 메모리 공간이 많이 필요한 문제가 있다. 이는 컴퓨터의 연산 속도, 메모리 공간에 대한 제약이 걸려 효율적인 알고리즘이 필요하다. 다만, 이런 문제들 중에서도 메모리 공간을 약간 더 사용하여, 속도를 비약적으로 높이는 방법이 있는데 이 중 대표적인 방법이 다이나믹 프로그래밍(Dynamic Programming)기법(동적 계획법)이다. 다이나믹 프로그래밍이란? 한번 해결된 부분 문제의 정답을 메모리에 기록하여, 한번 계산한 답은 다시 계산하지 않도록 하는 문제 해결법 이다. 다이나믹 프로그래밍은 *점화식을 그대로 코드로 옮겨 구현할 수 있다. (점화식: 인접한 항들 사이의 관계식) 대표적인 예시 문제가 피보나치 수열 문제이다. 피보나치 함수 코드 # 피보나치..

이진 탐색탐색의 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색하는 기법.특징이진 탐색은 배열 내부의 데이터가 정렬되어 있을 때만 사용데이터의 개수가 1000만개를 넘어가거나 탐색 범위의 크기가 2000만-1000억 이면 이진 탐색으로 접근하길 권한다.3가지 변수(시작점, 끝점, 중간점)가 사용된다.시작점, 끝점 : 탐색하고자 하는 범위를 나타내기 위해 사용중간점 : 중간점에 있는 데이터와 찾고자 하는 데이터가 일치하는지 비교기위해 사용.시간 복잡도: O(logN) -> 한 번 비교때마다 반 씩 줄어드니까!소스코드 (재귀, 반복문)1. 재귀# 이진 탐색 소스코드 구현 (재귀 함수)def binary_search(array, target, start, end): if start > end: ..