[Tips]알고리즘 문제 풀이 마인드셋

최지수·2021년 7월 13일
1

Tips

목록 보기
1/1

보다 뛰어난 개발을 하기 위해서 친구에게코드포스 퍼플이래요 ㄷㄷ 알고리즘 강의를 받기 시작했습니당.

수업은 면접 형식으로 문제를 제공하면 이를 풀어보고 간략한 수도코드로 작성을 하고 거기에서 질문하고 답하는 방식으로 진행했습니당.

이를 통해 효과를 본 것은 주어진 문제를 설명하면서 잘못된 부분이 있으면 정정하고 올바른 로직으로 재전개를 하며 논리적 전개와 사고 능력을 기를 수 있는 좋은 계기가 되었습니당.

여기서, 친구는 저에게 본인이 했던 질문은 제가 스스로 자신에게 질문하라고 하였습니다.

스스로 질문하고 답하라

permutation 문제를 DFS 방식으로 푸는 과정에서 다소 막히는 중이었습니당.

그때 친구가 한번 문제를 같이 보자고 하며, 저에게 이러한 방식은 문제가 있지 않을까? 또는 여기에서 무엇을 추가하면 될까? 등 이것저것 질문을 던져주었어용.

신기하게도, 그때마다 저는 설명을 하면서 막혔던 부분이 풀리기 시작하면서 문제를 풀었고,

마지막으로 친구가 이 로직의 퍼포먼스가 어떻게 되냐는 것까지 물어보고 답을 하면서 스스로 로직을 전개하고 이에 대한 스펙을 정의를 할 수 있게 되었습니당. 보다 빠른 시간에 로직을 생각해는 것도 덤으로용 ㅎㅎ 큰 깨달음을 얻었습니당.

수업을 마무리하기 전에 친구가 본인의 알고리즘 풀이 노하우를 알려주었습니당. 이 부분에서 저의 부족한 부분을 정확하게 꼬집어주었고 다음 발전 단계를 생각할 수 있게 되었어용.

풀이 방식

친구는 문제당 최대 30~45분을 가지고 풀어보라고 하였습니다.

그 이상으로 넘어가면 풀이를 중단하고, 어디까지 생각했는지 그리고 그 과정에서 어떤 부분이 막혔는지 정리를 하라고 하였습니당.

10~15분 : 문제 이해

적어도 이 시간을 투자해서 문제를 이해하는데 집중하라고 하였습니당.

15분 : 전략 수립

여기서 조금 세부적으로 들어가는데용,

이정도는 5분컷

우선 5분정도는 자유롭게 생각합니당. 제한 조건을 고려해 timeout이 일어나지 않을 전략이 떠오르면 그대로 전개를 합니당.

마땅한 방법이 떠오르지 않는다. 10분 남음

마땅한 전략이 생각나지 않으면 다음 방식을 순차적으로 생각하며 전략을 짭니당.

알고리즘 대조

친구의 경험으로는 일반적으로 알고리즘 문제로 나오는 건 크게 8가지라고 합니당(당연히 그 이상도 있어요).

하나씩 대조해가면서 맞는 유형을 고릅니당.

문제 유형 일반화(?)
1. 완전 탐색 \to Bruteforce, DFS, BFS,...
2. 그리디Greedy
3. 다이나믹 프로그래밍DP
4. Divide & Conquer
5. 논리 퍼즐
6. 수학
7. Adhoc \to Idea가 필요한 문제
8. 자료구조

실제론 이 유형을 섞어서 내는 경우가 많다고 합니당. 그렇기 때문에 대조하면서 각 부분마다 대조를 천천히 해보는 것도 중요합니당.

제한 조건을 통해서도 대조 유형의 범위를 좁힐 수 있습니당.

조건에 따른 시간 복잡도
1. 100 O(n3)\to O(n^3)
2. 1000 O(n2)\to O(n^2)
여기까지는 다이나믹 프로그래밍DP으로 해결 할 수 있습니다.
3. 10000 O(nlogn)\to O(n\log n)
여기는 그리디로 풉니다.

이를 통해서도 timeout이 나는 경우가 있습니당. 그땐 조건을 주면서 불필요한 연산을 최소화하는 방식을 통해 접근해야 합니당.

그래도 안 떠오른다? 그럼 우선 당연한 것부터

여기까지 진행했음에도 떠오르지 않는다면 '당연한 것'부터 생각해야 합니당.

예를 들면, '숫자와 문자열이 혼합된 문자열을 숫자로 출력하기' 문제를 봅니당

12threefour5six \to 123456

여기서 나올 수 있는 '당연한' 가능성을 나열해 봅니당

  1. 숫자 + 숫자 → 11
  2. 숫자 + 문자열 → 1one
  3. 문자열 + 숫자 → one1
  4. 문자열 + 문자열 → oneone

빈 값은 당연히 없는 거니까 제쳐두고, 위와 같은 4가지 조건이 나타날 수 있음을 생각하고, 이를 통해 로직을 전개하면 답을 얻을 수 있게 됩니당.

마지막 15분 : 풀거나, GG쳐도 본전은 뽑거나

전략이 수립했다면 그대로 진행하시면 되용. 그 과정에서 사소한 예외 처리까지 전부 다하게되면 문제를 풀게 됩니당.

문제는 그러지 못하거나, 아니면 아예 전략을 수립을 못하게 되면 포기하고 다음 문제로 넘어가아아아 기전에 어디까지 설계를 했고, 그 과정이 어디에서 막혔는지를 정리한 다음에 넘어갑니당.

많은 것을 배웠어요

수업을 들으면서 문제 해결 방식에 발전이 필요한 부분이 무엇인지 알게 되었습니당.

특히, 저는 개인적으로 '마땅한 방법이 었으면 알고리즘 대조'에서 큰 깨달음을 얻었어용. 저는 '자유롭게 생각하는' 단계에서 벗어나질 못했거든요...

'이렇게 하면 신박한 방법이 되지 않을까?' '조금만 더하면 풀 수 있을꺼 같은데?' 라는 강박에 잡혀 계속 고집을 부리게되 시간을 낭비하곤 했습니당.

지금 당장 제가 길러야할 것은 방식을 고집하지 않고 효율적으로 진행하는 능력인 것 같습니다 ㅎㅎ

그리고 친구에게서 많은 것을 배워 알고리즘 역량을 빠르게 키울려고 노력할 겁니당.

profile
#행복 #도전 #지속성

1개의 댓글

comment-user-thumbnail
2021년 8월 2일

알고리즘 문제 푸는 마인드를 바꿀 수 있는 좋은 글이었습니다. 감사합니다.

답글 달기