개발/알고리즘

DP(동적 프로그래밍) 자바스크립트 구현/ 작성중

동적 프로그래밍 Colt Steele 저자의 유데미 Javascript 자료구조 & 알고리즘 강의를 바탕으로 공부 내용을 정리합니다. 1. 정의 동적 프로그래밍은 복잡한 문제를 더 간단한 하위 문제들의 모음으로 분해하여 각각의 하위 문제들을 풀고 그 답을 저장하는 방식으로 문제를 푸는 방법이다. 모든 문제들에 적용 가능한 방식은 아니지만 동적 프로그래밍을 적용할 수 있는 문제의 경우엔 코드의 성능에서 큰 이점을 가진다. DP 요구조건 1 - 중첩되는 하위 문제가 있어야 한다. 대표 유형: 피보나치 수열 문제 문제 내에서 어떤 방식으로든 반복되는 하위 문제들이 있어야 한다. 즉, 하나의 커다란 문제를 더 작은 문제들로 나눌수 있으며 그 나뉜 작은 문제들을 재사용 가능해야 한다. 피보나치 수열은 모든 숫자가..

자바스크립트로 설명하는 재귀함수

1. 재귀함수 재귀: 자기 자신을 호출하는 절차. 재귀 호출: 함수가 자기 자신을 호출하는 것.(recursive call) 재귀 함수: 재귀 호출을 수행하는 함수. 즉 자기 자신을 호출하는 함수를 말한다. 재귀 함수는 반복되는 처리 를 위해 사용한다. 주로 아래 경우에서 많이 사용한다. JSON.parse() 를 호출하는 JSON.parse() 팩토리얼 DOM 순회 객체 순회 자료구조 구현 모든 경우에서 반복문을 대체함이 아닌, 재귀함수를 사용하는 것이 더 코드를 이해하기 쉬운 경우에 사용한다. 탈출 조건이 없으면 무한반복 하여 스택 오버플로우 되므로 반드시 탈출 조건이 주어져야 한다! (탈출 조건: base case) 반복되면서 입력받을 값 또한 계속 바뀌어야 한다. 그렇지 않으면 계속 같은 값만 확..