뚝딱햄 탈출기

다이나믹 프로그래밍?다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘이다. DP와 다르게 분할 정복은 동일한 문제를 다시 푼다.예를 들어 피보나치 수열을 분할 정복을 통해 푼다면 특정 숫자를 구하기 위해 그 n-1와 n-2 에 계속 접근한다.즉, 반복적인 데이터 계산이 발생한다.DP 사용할 수 있는 경우큰 문제를 작은 문제로 나눌 수 있다.작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.위의 조건을 만족할 때 다이나믹 프로그래밍을 사용하면 효율적으로 문제를 해결할 수 있다.다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 문제를 풀 때, 주어진 문제가 다이나믹 프로그래밍 유형임을 파악해야한다...

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저 Chapter 1 - 3. 복잡도 정리 내용 복잡도는 알고리즘의 성능을 나타내는 척도로, 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도 : 특정 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미. 알고리즘을 위해 필요한 연산의 횟수. 공간 복잡도 : 특정 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미. 알고리즘을 위해 필요한 메모리의 양. 동일 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이다. 코딩 테스트에서 문제를 풀 때, 가독성을 해치지 않는 선에서 최대한 복잡도가 낮게 프로그램을 작성해야 한다. 시간 복잡도 알고리즘 문제를 풀 때 단순히 '복잡도'라고 하면..