한 지점까지 탐색한 정보를 바탕으로 다음 상태의 최적해를 구하는 알고리즘. 이전의 정보를 저장해놓는 메모이제이션, 앞으로 사용할 정보를 미리 계산하는 타뷸레이션 두 방식이 존재한다. 코딩 테스트에서는 주로 메모이제이션을 이용하며, 이로 인해 메모리 공간을 많이 사용하지만 탐색 시간이 빠른 것이 장점이다. 가장 전형적인 동적프로그래밍 문제로 피보나치 수열이 있다.
피보나치 수,
의 초기조건과 의 규칙을 가지는 수열. 이전 값 을 메모이제이션 했다면 값을 알 수 있다.
위와 같이 초기조건을 지정할 수 있고, 초기 조건을 바탕으로 다음 값을 알아낼 수 있다면 동적프로그래밍으로 해결 할 수 있는 문제인지 고려해보는 것이 좋다.
앞서 배운 map, reduce, filter를 적절하게 조합하면 하나의 이터러블로 부터 자신이 원하는 값을 얻을 수 있다. 또한 이 조합을 함수로 선언하여 코드의 재사용성을 높힐 수 있다.
const iter = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const powerSum = pipe(
map(a => a*a),
reduce((a, b) => a + b)
);
console.log(powerSum(iter)) // 285
위의 코드에서 powerSum
은 이터러블의 모든 요소의 제곱을 더한 값을 출력하는 함수이다. 그런데 만약 모든 요소의 제곱근의 총합을 구하는 sqrtSum
을 구현해야 한다면 어떨까?
const sqrtSum = pipe(
map(a => Math.sqrt(a)),
reduce((a, b) => a + b)
);
이렇게 구현한 두 개의 함수는 공통의 코드 부분이 너무 많다. 따라서 각 요소를 처리하는 map 부분을 입력받는 함수에 맡겨서 다형성을 높일 수 있다.
const add = (a, b) => a + b;
const optionalSum = (opt, param) => go(
param,
map(opt),
reduce(add)
);
//sqrtSum
const sqrtSum = optionalSum(a => Math.sqrt(a), iter);
//powerSum
const powerSum = optionalSum(a => a * a, iter);
위와 같이 함수 opt
의 입력에 따라 powerSum
또는 sqrtSum
의 동작을 하며 중복된 부분을 최소화 할 수 있다. 또한 currying을 통해서 더 가독성이 좋은 함수를 만드는 것이 가능하다.
const optionalSum = curry((opt, param) => go(
param,
map(opt),
reduce(add)
));
const powerSum = optionalSum(a => a * a);
console.log(powerSum(iter));
CSS selector, CSS의 id와 class의 차이점, 동적프로그래밍 문제풀이
오늘은 오랜만에 답안이나 해설없이 실습을 스스로 풀었다. 효용성에서 약간 막히는 부분이 있어서 시간을 좀 썼지만 혼자서 끝까지 했다는 사실이 뜻깊다. 동적프로그래밍은 점화식을 짜는 것도 어렵지만, 풀고 있는 문제가 동적프로그래밍 문제인지 판단하는 것도 어렵다고 한다. DP 실습인 걸 알고 풀어서 금방 풀리지 않았을까? 라는 생각도 든다.
프로그래머스 프론트엔드 데브코스