[week04] SW사관학교 정글 4주차 회고

📷 회고

이번 주차는 알고리즘 주차의 마지막 주였고 키워드는 동적 프로그래밍, 그리디 알고리즘이었다.

알고리즘 4주차쯤 오니까 어떻게 개념공부를 해야 하고, 어떻게 팀 활동을 해야 하는지 슬슬 알 수 있었다.

문제 수가 적어서 우리 조는 주어진 과제들을 모두 풀고, 답을 보고 푼 문제들은 한번 더 풀고, leetcode와 백준에 연관되어있는 문제도 같이 풀어보았다. 조원 형이 문제를 끊임없이 추천해줘서 문파르타 코딩클럽이라고 장난쳤던게 기억에 남는다. 시험에서 실제로 조원 형이 추천해준 문제가 나왔다...!

 

시험문제에서 dfs와 greedy를 섞어 놓은 문제가 나왔는데 실제 코딩 테스트에서는 이런 식으로 출제가 될 것 같았다. 정형화된 문제들은 정말 쉽게 풀 수 있어야 2~3개의 개념이 섞인 문제도 풀 수 있을 것 같다고 생각했다.

 

내가 이번주에 헷갈렸던 부분은 다이나믹 프로그래밍과 그리디 알고리즘의 접근방법이었다.

다이나믹 프로그래밍과 그리디 알고리즘은 완전히 다르다.

• DP는 n의 상황에서 점화식을 구하고, 초기값을 설정해 주는 느낌이라면
• 그리디는 주어진 상황을 관통하는 하나의 방법을 찾는 느낌이다.

DP 문제를 그리디로 풀려고 하면 풀리지 않기 때문에 이 둘을 구분하는 것이 중요하다.

그리고 그리디 문제는 이 문제가 그리디로 풀어도 되는 것인지 아닌지를 판단하는것이 어려웠다. 많이 풀어보는게 답인 것 같다.

 

토요일 저녁 12시쯤 기숙사에 들어가기 전에 조원 형과 맥주를 한잔 했는데 먹어본 맥주중에 TOP 5안에 들었다... 역시 고생하고 나서 즐거운 일을 할 때는 즐거움이 배가 되는 것 같다. 

기숙사 들어가는 길

원래 나는 한글파일로 계획표를 작성하고 있었는데 그걸 보더니 조원 형이 구글 캘린더를 써보라고 추천해줬다. 원래 하던게 있어서 '한글이 얼마나 편한데!' 라는 마음이 있었지만 한번 도전해봤다.

구글 캘린더가 확실히 이쁘고 편하고 용량걱정도 없다... 1년 넘게 한글파일로 관리하고 있었는데 진작 바꿀껄 그랬다.

 

백준 문제를 풀다 보면 예제는 다 맞는데 막상 제출하면 틀렸습니다 가 나오는 경우가 많다. 그럴 경우에 어떻게 생각해야 하는지 도움이 되는 조언들을 모아놓은 링크를 공유한다.

https://www.acmicpc.net/blog/view/70

자주 틀리는 요인

벌써 정글에 들어온지 1달이 지났다. 분명히 처음 들어왔을 때보다 알고리즘 푸는 실력이 올라간 것은 확실하지만 아직 정리가 덜 된 느낌이다. 다음주 부터는 알고리즘 스터디를 진행해서 4주만에 빠르게 훑었던 알고리즘을 구조화하고 정리하는 시간을 가져야 할 것 같다.

💻 코치님 조언

컴퓨팅 사고로의 전환 마지막 주가 지나고 있습니다.
어떠신가요? 이미 소프트웨어 개발자가 된 것 같나요? 아직 뭐가 뭔지 모르겠나요?

1. 혹시 아직도 뭐가 뭔지 모르겠다면

내가 생각한 것을 프로그램으로 만들 수 있는지 자기 자신에게 질문해 보십시오.
이 과정의 가장 근본적인 목표는 내가 원하는 작업을 컴퓨터에게 시키는 능력을 키우는 것입니다.
일단, 내가 원하는 것을 컴퓨터에게 쉽게 시킬 수 있다면 잘 따라가고 있다고 생각합니다.

미래에 내가 원하는 것, 해내야 할 작업이 뭐가 될지 모르기 때문에 정형화된 문제들로 연습하는 것이고
이왕이면 효율적으로 빠르게 컴퓨터에게 일을 시키기 위해 계산 복잡도를 고려하고, 문제 유형을 나누어 익히고,
정해진 시간 안에 프로그램을 짜는 연습을 하는 것입니다.

2. 눈치 빠른 분들은 알고 계시겠지만 각 주의 keyword 들은 서로 연관이 있습니다.

• 분할 정복은 재귀함수로 구현하기 좋습니다.
• 이분 탐색은 분할 정복의 한 가지 방법입니다.
• 재귀 함수를 반복문(loop)으로 바꿀 때 스택을 사용하면 쉽게 바꿀 수 있습니다. (문제에 따라서는 스택을 안 쓰고도 바꿀 수 있습니다.)
• DFS는 재귀로 구현하면 매우 쉽게 구현할 수 있고 반복문으로 구현하려면 스택을 사용하면 됩니다.
• BFS를 구현할 때 큐(queue)를 사용하며, 큐를 priority queue로 바꾸면 Dijkstra 알고리즘이 됩니다.
• DP(dynamic programming)도 분할 정복을 구현하는 방법들 중 한 가지 방법이며, 따라서 재귀 함수로 구현하기 좋습니다. (솔직히 점화식이 보이는데 이걸 깨닫지 못한다면...)
• DP 문제를 단순 재귀 함수로 구현하면 같은 함수가 여러번 불리는 경우가 있으므로 한번 계산한 함수는 그 결과값을 저장하는 기법을 사용하는데 그 기법을 memoization이라고 부릅니다.
• 1주차의 완전탐색 문제를 3주차에 다시 보면 문제의 graph를 탐색하는 방법으로 생각할 수 있다는 걸 깨달을 수 있습니다.

각각의 풀이 방법을 외우려고 하지 않고 이런 연관성을 가지고 보면, 컴퓨터로 풀 수 있는 문제의 모양을 보는 데 도움이 되리라고 생각합니다.

3. DP에 대해서 좀 더 이야기 하자면 

• k-차원 array를 만들고 array를 채워 나가는 DP의 풀이 방식, 소위 bottom-up 방식의 풀이는 가끔 이해하기 어려운 경우가 있습니다. 사실 bottom-up 방식은 재귀를 이용한 top-down 방식을 (stack 없이) 반복문으로 만든 겁니다. 이렇게 만들어 놓고 보면 상당량의 최적화, 특히 공간 최적화를 더 할 수 있는 경우가 많기 때문에 이 방식의 풀이를 좋아하시는 분들이 계신데... 일단은 이해가 중요합니다. 이해 할 수 있는 풀이를 먼저 찾는 것을 권장합니다.
• Python은 cache decorator를 제공하여 top-down DP 구현을 쉽게 만듭니다. (function argument == array index)
• "점화식을 알면 DP를 쉽게 짤 수 있는데 점화식을 어떻게 만들지 모르겠다"라고 하시는 분들 계실텐데, 맞습니다. 점화식을 만드는 것 자체가 문제를 푸는 것이고, 좀 더 정확하게는 문제를 어떻게 잘 자를 수 있는가를 찾는 과정입니다. 사실 1주차 재귀, 2주차 분할정복에서부터 필요했던 능력입니다.
• 가끔 보면 문제를 딱 보고 어떻게 자르면 되는지 알아차리기를 원하시는 분이 계시는데, 그 정도의 능력은 저는 재능의 영역으로 봅니다. 솔직히 이게 되면 못 풀 문제 없죠. 특정 사람들만 알아듣는 말로 "직사의 마안"을 가졌다고 표현합니다. 그렇다고, 노력해도 기를 수 없는 능력이냐 하면... 뭐, 하다 보면 늘기는 합니다.