[SW정글] week04 후기 (feat, dp, 그리디)

 

Dynamic Programming - DP

 

 정의 

- 큰 문제를 작은 문제로 나눌 수 있고, 그 겹치는 작은 문제들의 경우 메모제이션 기법을 사용하여 큰 문제를 푸는 기법

분할 정복을 하는데 그걸 메모제이션해서 나아간다.

 

 

 DP의 장점 

- 모든 가능한 경우를 확인하기 때문에 근사치가 아닌 정확한 값을 얻을 수 있따.

 

 DP의 단점 

- 모든 가능한 경우를 확인하기 때문에 시간복잡도가 크다.

 

알고리즘 주차를 진행하며 DP가 제일 어려웠다. 점화식을 떠올리는게 정말 어려웠고, 정답 코드는 너무 짧아서 보면 허무했을 정도다.

 

또한, 알고리즘이 너무 많았다. 예를 들어 Knapsack problem, LIS(Longest Increasing Sequence), LCS(Longest Common Sequence), Bit Mask ... 정말 넘모 넘모 어려웠다.

 

아직까지는 문제를 보고 이 알고리즘이어서 이러한 풀이법을 써야겠다는  "직사의 마안" 을 가지기엔 갈 길이 먼 것 같다.

 

 

Greedy 

 

그리디는 욕심쟁이다. 현재 상황에서 최선의 선택을 하며 나아가, 최종적으로도 최선을 선택한다는 것이다.

 

그리디 문제라는 것을 알고 풀어서 그런지, '이거 이렇게 하면 되겠는데 ?' 라고 생각하고 제출을 하면 정답이었다.

 

그러나, 실전에서 문제를 받는다면 그리디 문제라고 느끼지 못할 것 같아 걱정이다.

 

---

 

잡설

 

마지막 알고리즘 시험을 3문제중 한문제 밖에 못풀어서 아쉬움이 컸다.

 

3문제 다 풀었지만 2문제가 시간초과가 났다.

 

풀이를 보니 접근을 초큼 잘못한 듯하다 ..ㅠ

 

목요일부터 알고리즘(컴퓨팅 사고로의 전환)이 끝나고 Red-Black Tree(탐험준비)를 시작했다.

 

정글 합격을 받고 C언어 공부를 2주 정도 동안 했다. 그러나, 다까먹었다... 다시 보니까 하나도 모르겠다,,,

 

목요일로부터 2일이 지낫는데 트리도 구현을 못하고 있다.

 

독자가 만약 정글 입소 예정자라면, C 언어 포인터 정도는 완벽히 익혀서 오길 권한다.

 

너무너무너무너무너무너무 어렵고 헷갈리는 개념인것 같다.

 

 

이 글을 읽는 모두들 열코다 🔥! 화이팅 !