보다 뛰어난 개발을 하기 위해서 친구에게코드포스 퍼플이래요 ㄷㄷ 알고리즘 강의를 받기 시작했습니당.
수업은 면접 형식으로 문제를 제공하면 이를 풀어보고 간략한 수도코드로 작성을 하고 거기에서 질문하고 답하는 방식으로 진행했습니당.
이를 통해 효과를 본 것은 주어진 문제를 설명하면서 잘못된 부분이 있으면 정정하고 올바른 로직으로 재전개를 하며 논리적 전개와 사고 능력을 기를 수 있는 좋은 계기가 되었습니당.
여기서, 친구는 저에게 본인이 했던 질문은 제가 스스로 자신에게 질문하라고 하였습니다.
permutation
문제를 DFS
방식으로 푸는 과정에서 다소 막히는 중이었습니당.
그때 친구가 한번 문제를 같이 보자고 하며, 저에게 이러한 방식은 문제가 있지 않을까? 또는 여기에서 무엇을 추가하면 될까? 등 이것저것 질문을 던져주었어용.
신기하게도, 그때마다 저는 설명을 하면서 막혔던 부분이 풀리기 시작하면서 문제를 풀었고,
마지막으로 친구가 이 로직의 퍼포먼스가 어떻게 되냐는 것까지 물어보고 답을 하면서 스스로 로직을 전개하고 이에 대한 스펙을 정의를 할 수 있게 되었습니당. 보다 빠른 시간에 로직을 생각해는 것도 덤으로용 ㅎㅎ 큰 깨달음을 얻었습니당.
수업을 마무리하기 전에 친구가 본인의 알고리즘 풀이 노하우를 알려주었습니당. 이 부분에서 저의 부족한 부분을 정확하게 꼬집어주었고 다음 발전 단계를 생각할 수 있게 되었어용.
친구는 문제당 최대 30~45
분을 가지고 풀어보라고 하였습니다.
그 이상으로 넘어가면 풀이를 중단하고, 어디까지 생각했는지 그리고 그 과정에서 어떤 부분이 막혔는지 정리를 하라고 하였습니당.
적어도 이 시간을 투자해서 문제를 이해하는데 집중하라고 하였습니당.
여기서 조금 세부적으로 들어가는데용,
우선 5
분정도는 자유롭게 생각합니당. 제한 조건을 고려해 timeout
이 일어나지 않을 전략이 떠오르면 그대로 전개
를 합니당.
마땅한 전략이 생각나지 않으면 다음 방식을 순차적으로 생각하며 전략을 짭니당.
친구의 경험으로는 일반적으로 알고리즘 문제로 나오는 건 크게 8
가지라고 합니당(당연히 그 이상도 있어요).
하나씩 대조해가면서 맞는 유형을 고릅니당.
문제 유형 일반화(?)
1. 완전 탐색 Bruteforce, DFS, BFS,...
2. 그리디Greedy
3. 다이나믹 프로그래밍DP
4. Divide & Conquer
5. 논리 퍼즐
6. 수학
7. Adhoc Idea가 필요한 문제
8. 자료구조
실제론 이 유형을 섞어서 내는 경우가 많다고 합니당. 그렇기 때문에 대조하면서 각 부분마다 대조를 천천히 해보는 것도 중요합니당.
제한 조건을 통해서도 대조 유형의 범위를 좁힐 수 있습니당.
조건에 따른 시간 복잡도
1. 100
2. 1000
여기까지는 다이나믹 프로그래밍DP
으로 해결 할 수 있습니다.
3. 10000
여기는 그리디로 풉니다.
이를 통해서도 timeout
이 나는 경우가 있습니당. 그땐 조건을 주면서 불필요한 연산을 최소화하는 방식을 통해 접근해야 합니당.
여기까지 진행했음에도 떠오르지 않는다면 '당연한 것'부터 생각해야 합니당.
예를 들면, '숫자와 문자열이 혼합된 문자열을 숫자로 출력하기' 문제를 봅니당
12threefour5six 123456
여기서 나올 수 있는 '당연한' 가능성을 나열해 봅니당
- 숫자 + 숫자 → 11
- 숫자 + 문자열 → 1one
- 문자열 + 숫자 → one1
- 문자열 + 문자열 → oneone
빈 값은 당연히 없는 거니까 제쳐두고, 위와 같은 4
가지 조건이 나타날 수 있음을 생각하고, 이를 통해 로직을 전개하면 답을 얻을 수 있게 됩니당.
전략이 수립했다면 그대로 진행하시면 되용. 그 과정에서 사소한 예외 처리까지 전부 다하게되면 문제를 풀게 됩니당.
문제는 그러지 못하거나, 아니면 아예 전략을 수립을 못하게 되면 포기하고 다음 문제로 넘어가아아아 기전에 어디까지 설계를 했고, 그 과정이 어디에서 막혔는지를 정리한 다음에 넘어갑니당.
수업을 들으면서 문제 해결 방식에 발전이 필요한 부분이 무엇인지 알게 되었습니당.
특히, 저는 개인적으로 '마땅한 방법이 었으면 알고리즘 대조'에서 큰 깨달음을 얻었어용. 저는 '자유롭게 생각하는' 단계에서 벗어나질 못했거든요...
'이렇게 하면 신박한 방법이 되지 않을까?' '조금만 더하면 풀 수 있을꺼 같은데?' 라는 강박에 잡혀 계속 고집을 부리게되 시간을 낭비하곤 했습니당.
지금 당장 제가 길러야할 것은 방식을 고집하지 않고 효율적으로 진행하는 능력인 것 같습니다 ㅎㅎ
그리고 친구에게서 많은 것을 배워 알고리즘 역량을 빠르게 키울려고 노력할 겁니당.
알고리즘 문제 푸는 마인드를 바꿀 수 있는 좋은 글이었습니다. 감사합니다.