알고리즘과 문제 해결 패턴, 전략 계획, 접근방식
알고리즘이란?
특정 작업을 달성하기 위한 과정이나 일련의 단계
문제를 해결하기 위해 수행해야 하는 일련의 수학적 단계
왜 알아야되나?
→ 프로그래밍에서 수행하는 거의 모든 작업에는 일종의 알고리즘이 포함.
면접에서는 항상 알고리즘이 다뤄진다.
알고리즘을 다루기를 잘하는 법
- 문제 해결을 위한 계획을 수립할 것.
- 일반적인 문제 해결 패턴을 익힐 것.
면접에서 다뤄지는 알고리즘들을 일련의 카테고리로 나누어 공부한다.
문제 해결 전략
문제를 이해하기
시간 제약이 있을때도 바로 코드를 입력하기 보다는, 한발 물러서서 직면한 과제를 확실히 이해해야한다.
스스로에게 이런 질문을 해본다.
→ “문제를 여러분 방식대로 다시 생각할 수 있나요?”
인풋은 무엇인가?
아웃풋은 무엇이 나와야 할까?
출력값은 어떤 형태여야 하나?
문제를 해결할 충분한 정보가 주어졌는가?
문제의 일부인 데이터 중요 부분에 어떻게 라벨을 지정할 수 있을까?
구체적인 예시를 찾아보기
간단한 예시를 만든다
인풋고 아웃풋의 순서대로 예시를 두 세개 작성해본다
경계조건 → 유효하지 않은 인풋이 주어지면 어떻게 되나?
항상 사용자가 유효하지 않은 인풋을 입력할때 어떻게 될지를 생각해야한다
예시를 살펴보고 면접관이 나의 말을 듣고 과정에 들어올 수 있도록 크게 이야기하라.
수행하는 작업, 문제 세분화, 단계 작성을 면접관에게 인지시킨 후 문제를 해결.
문제를 세분화하기(break down)
문제에 대한 단계들을 작성한다는 뜻
면접에서 면접관들은 면접자가 수행하는 작업이 무엇인지를 소통하기를 원한다
미간을 찌푸린 채 말없이 코드를 입력하면X
이러이러 한걸 할거다 말하는게 낫다. 그러면 힌트를 얻을 수도 있고 면접관이 질문을 할수도 있다.
문제를 세분화하는 것은 아주 중요함.
아주 세세하게 작성할 필요는 없음. 모든 라인마다 작성할 필요도 없음.
해결책의 기본적인 구성 요소만 작성하면 된다.
그러면 코드를 실제로 입력하기 전에 한번 생각해볼 수 있게 해준다.
감이 잡히지 않거나 이해되지 않는 부분들을 파악하게 하거나 이해할 수 있게 해줌.
세분화하면
→단계들의 틀을 잡고 항상 집중할 수 있도록 해주고 확신이 들지 않는 문제를 짚을 수 있게 해준다.
그러고나서 코드를 입력하면 됨.
완전한 수도코드가 아니더라도 단계별로 해야할 작업들을 세분화하여 주석으로 쓴다.
무엇을 해야할지 길이 생김.
면접에서 완전한 답을 못 내더라도 올바른 길을 제시했다면 붙을 수 있다.
답이 아니라 어떻게 진행하는지를 본다. 즉 과정이 중요하다
문제를 해결하고 단순화하기
문제를 해결할 수 있다면 해결하고
해결할 수 없다면 더 단순한 문제를 해결한다.
해결해야할 대상을 아예 바꿔서 시간이 많이 소요되는 부분을 무시하라는 것이다.
가로막히는 부분은 건너뛰고 풀리는 지점들을 푼다.
단순화 과정에서 실제 문제의 어려운 부분을 파악하면서 점차 해결되기 시작한다.
이해→예시→세분화→
→어려운 부분은 무시하고 단순한 해결책을 작성한 다음 다시 어려운 부분을 통합.
블랭크를 건너뛰고 면접관에게 ‘ 이 부분은 방법이 정확히 기억이 안나니 건너뛰겠다’ 말하고 마지막까지 진행한다.
문제를 해결할 수 있다면
세분화한 수도코드나 주석을 한줄씩 코드로 바꾼다.
어느정도 완성한 상태에서 달성하는데 한가지 작은 부분만 남겨둔 상태라면
면접관에게 질문할수도 있다.
‘세가지 방법을 알고 있는데 무엇이 최선인지, 확신이 들지 않는다. 제안이 있나요?”
90% 달성한 상태에서 이와 같은 질문을 한다면 문제 해결 능력을 보여줄 수 있다.
시작하기 전에 가로막히는 것과는 훨씬 낫다.
성급하게 무언가 작성하기 보다 페이지에 뭐든 작성하여 작동하기를 바라되 어려운 부분을 피하고
바로 연결할수 있도록 올바른 부분을 적합한 위치에 두는 것이 훨씬 낫다.
문제를 복습하고 재구성하기
스스로 발전하는데 가장 중요한 단계이다.
만든 해결책을 되돌아보고 미비한 부분을 다시 정리해야 한다.
답이 나왔다면 노트북을 덮고 게임을 하고 싶은 충동이 든다.
해결책이 나왔으니 그러고 싶다.
하지만 코드를 향상시키고자 노력하는 것은 정말 중요하다.
시간을 내어 코드를 살펴보고 되돌아보고 성찰하지 않는다면 좋은 기회를 놓칠것.
각 구성요소를 한 줄씩 살펴 보면서 마음에 들지 않는 부분이나, 코드의 형태, 해석 방법, 이해하기 쉬운지 등에 대해 이야기 해야 한다.
대부분의 사람들이 중요하게 여기는 것은 코드의 효율성.
그러나 효율성과 가독성이라는 두 기둥 사이에 균형을 맞추어야 한다.
일단 해결책을 완성했다면 제대로 작동한다는 데에 자부심을 가져도 좋다.
그 다음 코드를 한줄씩 읽으면서 생각한다.
이상적이지 않은 부분에 더 나은 방법을 적용할 수 있을텐데, 확신이 들지 않으니 더 빨리 처리할 수 있는 방법을 검색해 봐야겠다 이런 생각을 하는 것.
- 더 빨리 처리할 수 있는 방법이 없을까?
- 결과를 다른 방식으로 도출할 수 있는가?
- 생각나는 다른 접근 방식이 있는가?
- 한눈에 이해가 되는가?
- 해결책이 얼마나 직관적인가?
- 코드 내용을 종이나 화이트보드에 적어놓으면 이해가 되나?
- 결과와 방법을 다른 문제에도 적용할 수 있을까?
문제를 해결함으로써 얻을 수 있는 큰 이점은 직감을 발달시켜 다른 문제를 해결할 수 있는 직관력을 길러준다는 것.
따라서 해결책을 작성할때마다 다른 문제와 유사점 있는지 자문해보면 좋다.
- 성능을 향상시킬수 있는가?
→ 시간 복잡도와 공간 복잡도로 분석한다.
면접 상황에서는 나의 코드가 깔끔하지 않다는 것을 인정하고 시간이 없었지만 깔끔하게 만들 의향이 있다는 것을 알리는 것이 중요하다.
- 다른 사람은 어떻게 풀었을까?
다른 사람이 푼 방법을 보고 공부할 수 있다.
나는 자바스크립트를 써도 다른 사람이 파이썬이나 자바로 푼 해결책을 보고 아이디어를 얻을수도있다.
리팩토링은 중요하다.
코드를 분석하고 성찰하고 되돌아보는 것이 작동하는 코드를 완성하고 덮어버리는 것보다 훨씬 가치 있다.
charCodeAt을 사용하면 소문자, 대문자, 숫자인지 빠르게 확인할수 있다.
정규 표현식보다 55%빠르다.
만약 면접이라면 면접관에게 정규표현식을 사용했지만 아마 더 빠른 방법을 찾아봤을 거라고 말한다.
