TIL 7/4

학습내용

오늘은 분할정복 알고리즘에 대해서 학습했다. 분할 정복 알고리즘은 큰 문제를 작은 문제로 분할해서 재귀적으로 해결하는 방식의 알고리즘이다. 작은 문제로 나눠 해결하면서 큰 문제를 조합해 올라간다.

분할정복을 활용해서 배열의 최대값을 구하는 방법이 있다.

let arr = [ 4, 7, -3, 2, 6, -1, 8, 9 ];

이런 배열의 숫자가 있다고 봤을때

[4] [7, -3, 2, 6, -1, 8, 9 ]
maxNum(arr) = maxNum([...arr[0],...maxNum(arr.slice)]

으로 나눠볼 수 있다. 계속 나눠서 계산하면
나중에 4와 비교해서 최대값을 찾는 마지막 단계를 거쳐서 최대값을 구할 수 있다.

이렇게 기본적으로 작은 단위로 쪼개서 basecase를 생각해 문제를 해결하는 방법이다.

느낀점

재귀를 사용하는게 익숙해 질만한데 아직도 어렵다. basecase를 생각하는게 조금만 복잡해져도 어려웠다. 조금더 다양한 문제를 통해서 이숙해져야겠다.