패스트캠퍼스 챌린지 10일차

---

Part 2. 알고리즘 이론

Ch 14. 동적 계획법과 분할 정복

 

01. 동적 계획법과 분할 정복

Ch 15. 고급 정렬 알고리즘

 

01. 병합정렬 (1)

 

02. 병합정렬 (2)

---

오늘은 동적 계획법과 분할 정복, 병합 정렬에 관해 공부했다. 동적 계획법과 분할 정복은 교재에 알고리즘이라고 되어있었지만 사실 알고리즘이라 보기 어렵고 문제를 푸는 방법이라고 하셨다. 동적 계획법과 분할 정복의 개념을 상향식, 하향식이라는 개념으로 설명했지만 비슷해서 구분하기 어렵다고 하시면서 공통점과 차이점으로 나눠 설명해주셨다. 나도 이 설명이 더 와닿고 잘 이해가 되어서 한 번 글로 정리해본다. 두 개념 모두 분할할 수 없을 만큼 가장 작은 단위로 분할해야한다는 공통점이 있다. 하지만 동적 계획법은 상향식이라는 설명처럼 작은 단위로 분할된 부분이 중복되어 상위 문제에서 재활용된다. 이를 활용하여 부분의 해답을 저장해서 재활용하여 최적화하는 Memoization 기법을 사용한다. 분할 정복은 하향식이라는 개념처럼 가장 큰 단위에서 작은 단위로 분할해가다보니 부분 문제가 중복되지 않고 Memoization 기법을 사용하지 않는다.

 병합 정렬은 부스트코스에서 배운 내용이다. 그때는  C언어로 코드를 구현했고, 메소드를 이용하지 않았던 것 같은데 기억이 잘 안 난다. 아무튼 배열의 요소를 하나가 되도록 나누고 배열의 순서대로 두 개씩 묶고 크기를 비교해 순서대로 합친다. 두 개씩 합쳐진 배열은 하나로 보고 다시 또 다음 배열과 크기를 비교하여 합친다. 이렇게 배워둬서 개념을 이해하는 건 어렵지 않았는데 코드로 작성하는 게 어려웠다. 여태까지 했던 것처럼 경우의 수를 모두 생각해야 해서 그냥 두 개로 나누면 된다는 것에서 왼쪽 오른쪽 요소가 둘 다 있을 때, 왼쪽만 있을 때, 오른쪽만 있을 때로 나눠서 모두 생각해야 했다. 그리고 개념을 이해할 땐 그냥 쉬웠는데 코드로 작성하자니 포인터 역할을 하는 인덱스도 신경 써야 했다. 그래서 원래는 퀵정렬까지 공부한 다음 후기를 작성하려고 했는데 병합정렬만 보는게 좋을 것 같아서 여기까지만 했다. 후기를 다 쓰고 코드를 다시 봐야겠다.

 

---

https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

- 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.-