Computer Science/알고리즘

코딩 테스트를 위한 Tip

길순이 2020. 9. 22. 19:05

Translate this article: How to Rock an Algorithms Interview

1. 칠판에 글쓰기를 시작하십시오.

이것은 당연하게 들릴지 모르지만, 빈 벽을 쳐다 보면서 수십 명의 후보자가 붙어 있습니다. 나는 아무것도 보지 않는 것보다 문제의 예를 응시하는 것이 더 생산적이라고 생각합니다. 관련성이있는 그림을 생각할 수 있다면 그 그림을 그립니다. 중간 크기의 예제가 있으면 작업 할 수 있습니다. (중간 크기는 작은 것보다 낫습니다.) 때로는 작은 예제에 대한 솔루션이 일반화되지 않기 때문입니다. 또는 알고있는 몇 가지 명제를 적어 두십시오. 뭐라도 하는 것이 아무것도 안 하는 것보다 낫습니다.

2. 그것을 통해 이야기하십시오.

자신이 한 말이 어리석은 소리일까 걱정하지 마십시오. 많은 사람들이 문제를 조용히 생각하는 것을 선호하지만, 문제를 풀다가 막혔다면 말하는 것이 한 가지 방법이 될 수 있습니다. 가끔은 면접관에게 진행 상황에 대해서 명확하게 말하는 것이 지금 문제에서 무슨 일이 일어나고 있는지 이해할 수 있는 계기가 될 수 있습니다. 당신의 면접관은 당신이 그 생각을 추구하도록 당신을 방해 할 수도 있습니다. 무엇을 하든지 힌트를 위해 면접관을 속이려 하지 마십시오. 힌트가 필요하면 정직하게 질문하십시오.

3. 알고리즘을 생각하세요.

때로는 문제의 세부 사항을 검토하고 해결책이 당신에게 나올 것을 기대하는 것이 유용합니다 (이것이 상향식 접근법 일 것입니다). 그러나 다른 알고리즘에 대해서도 생각해 볼 수 있으며 각각의 알고리즘이 당신 앞의 문제에 적용되는지를 질문 할 수 있습니다 (하향식 접근법). 이러한 방식으로 참조 프레임을 변경하면 종종 즉각적인 통찰력을 얻을 수 있습니다. 다음은 면접에서 요구하는 문제의 절반 이상을 해결하는 데 도움이되는 알고리즘 기법입니다.

  • Sorting (plus searching / binary search)
  • Divide and Conquer
  • Dynamic Programming / Memoization
  • Greediness
  • Recursion
  • Algorithms associated with a specific data structure (which brings us to our fourth suggestion...)

4. 데이터 구조를 생각하십시오.

상위 10 개 데이터 구조가 실제 세계에서 사용되는 모든 데이터 구조의 99 %를 차지한다는 것을 알고 계셨습니까? 때로는 최적의 솔루션이 블룸 필터 또는 접미어 트리를 필요로하는 문제를 묻습니다. 하지만 이러한 문제조차도 훨씬 더 일상적인 데이터 구조를 사용하는 최적의 솔루션을 사용하는 경향이 있습니다. 가장 자주 표시 될 데이터 구조는 다음과 같습니다.

  • Array
  • Stack / Queue
  • HashSet / HashMap / HashTable / Dictionary
  • Tree / Binary tree
  • Heap
  • Graph

5. 이전에 보았던 관련 문제와 해결 방법에 대해 생각해보십시오.

여러분에게 제시한 문제는 이전에 보았던 문제이거나 적어도 조금은 유사합니다. 이러한 솔루션에 대해 생각해보고 문제의 세부 사항에 어떻게 적응할 수 있는지 생각하십시오. 문제가 제기되는 형태로 넘어지지는 마십시오. 핵심 과제로 넘어 가서 과거에 해결 한 것과 일치하는지 확인하십시오.

6. 문제를 작은 문제로 분해하여 수정하십시오.

특별한 경우 또는 문제의 단순화 된 버전을 해결하십시오. 코너 케이스를 보는 것은 문제의 복잡성과 범위를 제한하는 좋은 방법입니다. 문제를 큰 문제의 하위 집합으로 축소하면 작은 부분부터 시작하여 전체 범위까지 작업을 진행할 수 있습니다. 작은 문제의 구성으로 문제를 보는 것도 도움이 될 수 있습니다.

7. 되돌아 오는 것을 두려워하지 마십시오.

특정 접근법이 효과적이지 않다고 느끼면 다른 접근 방식을 시도 할 때가 있습니다. 물론 너무 쉽게 포기해서는 안됩니다. 그러나 열매를 맺지 않고도 유망한 생각이 들지 않는 접근법에 몇 분을 소비했다면, 백업하고 다른 것을 시도해보십시오. 저는 덜 접근한 지원자보다 한참 더 많이 나아간 지원자를 많이 보았습니다. 즉, (모두 평등 한) 다른 사람들이 좀 더 기민한 접근 방식을 포기해야 한다는 것을 의미합니다.