크래프톤 정글 2기 4주차 후기

4주차를 마무리했다.

 

이번 알고리즘 4주차에 다룬 주제는 동적 프로그래밍(DP)와 그리디이다.

이번주에 같은 조가 된 조원들 덕에 정글에 와서 처음으로 알고리즘 스터디를 해봤다. 여태 혼자 풀며 알았다고 생각하고 넘어갔던 문제들은 시간이 어느 정도 흐른 뒤에 다시 보면 낯선 친구가 되어있었는데 스터디를 통해 같이 시간을 정해놓고 푸니 시간 단축이 되는 건 물론 남들 앞에서 내 코드를 설명해야 하니 동기부여가 됨으로써  열심히 준비하게 되고  기억에 더 남게 되는 것 같다. 이 재미난걸 왜 안했나싶다.

 

이번 주로 알고리즘 주차가 끝나지만 너무 신난다 스터디를 통해 매일매일 알고리즘 문제를 풀게 되는 것이 정말 도움이 많이 될 것이다. 5주차부터 3주동안 이어질 (Red-Black tree → malloc → 웹 proxy 서버) 과정을 위해 C언어를 미리 공부해둬야겠다. 오기전에 좀 할껄 ㅜㅜ

 

 

이번주 키워드

동적 프로그래밍(Dynamic Programming) - 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임이다. 반복문과 재귀를 주로 사용함

 

DP의 2가지 사용 조건 (문제 풀때 먼저 확인해야한다.)

 

1) Overlapping Subproblems(겹치는 부분 문제)

DP는 기본적으로 문제를 나누고 그 문제의 결과값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복해서 나타날때 DP를 사용가능하다. 

ex) 이진 탐색, 피보나치 수열

즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.

 

2) Optimal Substructure(최적 부분 구조)

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다. 

ex) 피보나치 수열

 

그리디 알고리즘(greedy Algorithm) - 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념이다. 미래를 생각 x 최적의 해를 구하기를 바람 ex) 거스름돈, 프림 알고리즘, 다익스트라 알고리즘

 

고려조건 - 그리디 알고리즘을 통해 정확한 답을 찾을 수 있다는 보장

 

 

DP와 그리디 문제들은 풀면 풀수록 더 모르겠다..

푸는 문제량이 부족해서 그런가봐