정글에서 살아남기 | WEEK04 | 다이나믹 프로그래밍은 다이나믹하지 않다구

 

 

드디어 알고리즘 마지막 4주 차...!!! 진짜 내가 컴퓨팅 사고로 전환하고 있는지 잘 모르겠지만 확실한 점은 알고리즘 문제를 건드릴 수는 있게 되었다는 점..? 처음에는 알고리즘 문제를 보고 나서 어떻게 풀어야 할지 접근조차 하지 못했었는데 이제는 완벽하게 정답을 출력하지는 못하더라도 이렇게 풀면 되겠다~라는 생각을 가지고 코드를 작성하기는 한다는 것(물론 결국 오답이다 ㅎㅎㅎ 이제 화나지도 않아)

 

여하튼, WEEK04주 차의 알고리즘 키워드!

WEEK04 : 동적 프로그래밍, 그리디 알고리즘

이번 주 과제의 수는 14개였다. 저번주처럼 과제 수가 적었고, 그 의미는 동적 프로그래밍(dp), 그리디 알고리즘(greedy) 역시 만만치 않게 어려운 카테고리라는 것이다. 그래도 저번 주에 기대 이상으로 dfs, bfs 등 그래프 탐색하는 알고리즘을 푸는데 선방(?)해서 이번에도 자신감을 가지고 공부를 시작했다.

 

 

1. 알고리즘 공부

이번 조는 2명만 있는 조가 걸렸다.(정글 2기 총원이 23명이고, 3명씩 한 조를 이루다 보니 마지막 조는 항상 2명)

3명보다 불리할 것 같지만, 오히려 2명이라서 더 좋았다. 코드 리뷰를 할 때 더 몰입해서 서로의 의견을 잘 공유할 수 있었고, 시간을 더 효율적으로 사용하는데 타협하기도 수월했다.

 

무엇보다 이번에 같은 조원인 형의 팀 운영 방식이 정말 좋았다. 정글은 매주 조가 바뀌기 때문에 항상 다른 방식으로 공부하면서 조 회의를 가졌었고 모든 방법들을 다 만족했었지만, 이번 주 같은 경우 일별로 개념 공부, 문제 풀이 개수, 서로 코드 리뷰 등 나름 일정을 체계적으로 가지면서 공부를 했다. 서로 같은 문제를 어떻게 접근하고 어떤 코드로 풀었는지 등을 두 명이서 서로 얘기 나누는 것이 도움이 많이 됐다! 그 과정에서 내가 상대방에서 내 코드를 설명하는 능력이 많이 부족하다는 것을 느꼈고, 문제를 잘 푸는 것 말고도 전달력을 키워야겠다는 생각도 들었다.

 

조원과 공부 방식은 정말 좋았다. 하지만 문제는 DP와 그리디...... dfs, bfs와는 또 다른 어려움을 선사했다.. 그래도 그래프 문제들은 어떻게 풀지 감이라도 잡고 나름 잘 헤쳐왔다고 생각했지만, dp는 다르다. 진짜 심각하게 어렵다..!

 

다이나믹 프로그래밍(Dynamic Programming, DP)

동적 계획법이라고도 불리는 이 DP는 다음과 같은 조건을 만족할 때 사용할 수 있다.

1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있다.
2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결한다.

위 사용 조건들을 보면 분할정복과 동일한 건가?라는 의문이 들 수도 있지만, 엄연히 다른 알고리즘이다.

이건 내가 공부할 때 정리했던 글

여하튼 일반적인 코딩 테스트 수준에서는 기본 유형의 DP문제가 출제된다고 하긴 하지만 그래도 싫다. 근데 내가 싫어도 어쩔 수 없다. 해야 한다! 일단 무조건 익혀야 한다...! 

 

그리디 같은 경우는 그래도 DP보다는 나았다. 문제를 보면서 아이디어를 떠올리고 구현하는 능력이 필요하긴 하지만(사실 모든 알고리즘이 다 마찬가지..) 여하튼 그리디는 DP보다는 쉽게(?) 접근할 수 있었다. 그리디 관련 내용은 아래 사진으로

 

 

2. WEEK04 테스트

역시 어렵게 어렵게 공부를 마치고 목요일 오전 10시, 저번 주와 마찬가지로 테스트를 봤다. 1주 차에 0문제, 2주 차에 1문제, 3주 차에 2문제를 맞혔으니까 등차수열에 맞게 이번 주는 3문제 모두 맞히는 것이 올바르겠지만 난 틀려먹었나 보다 ㅋ 이번 주는 한 문제만 맞혔다 ㅠㅠㅠ... 첫 번째 문제는 DP문제였는데 엄청 어렵지 않았다. 그런데 문제를 잘못 이해해서 계속 오답이 나왔고, 결국 2번 문제부터 풀었다.

2번 문제는 DFS와 DP를 같이 사용해서 어찌저찌 겨우 풀었다. 솔직히 2번 문제도 진짜 어려운 문제였는데 내가 풀었다는 게 신기할 정도... 3번은 볼 시간조차 없었구ㅜㅜㅜ

 

많이 아쉬웠지만 그래도 열심히는 했으니까...! 대신 알고리즘 주차가 끝났어도 매일 최소 한 문제씩은 풀면서 알고리즘 역량을 차근차근 쌓아갈 것이라는 목표를 세웠다.

 

---

 

사실 쓰고 싶은 내용이 많지만 지금 일요일에 편하게 블로그 글을 쓸 여유가 없다. 이번 주부터 시작한 C언어 커리큘럼이 기대 이상으로 강력하기 때문에... 목요일부터 글을 쓰는 현시점까지 C 기본 문법을 이해하고, linked-list를 공부하고, 과제인 Red-Black-Tree를 공부하는데.... 이해가 안 돼... 계속 같은 부분만 읽고 있다 도르마무 C를 알려줘... 도르마무 C를 알려줘... 도르마ㅁ...

 

여하튼! 그나마 이번 주 조원 형들과 케미가 좋아서 조 회의를 하면서 서로 차근차근 이해하고 있다. 다음 주에 WEEK05 리뷰를 할 때는 마음 편하게 RBtree에 대해 설명할 수 있게 되기를 바라면서 공부하러 가이지...

 

가져올 짐들이 있어서 오전부터 기차타고 잠시 수원 가는 중. RBTREE 저놈 때문에 잠도 오지 않는다 ㅠㅠ(그렇다고 코드를 봐도 이해할 수 없다는 것은 함정 ㅋ)