프로그래밍 문제 접근법
인터뷰에서 가장 주된 부분을 차지하는 것은 기술면접, 코딩 => 어려운 문제 => 능력을 보여줄 수 있는 기회
답이 보이지 않는 상황에서 문제를 어떤 식으로 해결하는지를 살펴보기 위한 문제들도 있으니 긴장은 하지말자!
답이 보이지 않는 상황에서 문제를 어떤 식으로 해결하는지를 살펴보기 위한 문제들도 있으니 긴장은 하지말자!
1. 절차
1.1 시나리오
코딩문제는 인터뷰어와 일대일로 진행하는 것이 일반적.
종이와 펜을 코드를 작성하라고 한다거나, 전에 문제를 설명해보라고 할 수 있다.
1.2 문제
짧은 시간안에 설명까지 할수 있어야 하기 때문에, 변별력 있는 적당히 어려운 문제가 출제된다.
(실전에 직접 적용할 수 있는 코드를 만드는 문제가 나올 가능성은 희박함)
문제의 난이도는 대체로 점점 어려워지는 순서로 배치된다
1.3 어떤 언어를 선택할 것인가?
일반 프로그래밍 또는 개발업무를 지원했다면 C#, Java, C++, C 같은 주류 언어를 제대로 쓸수있는 정도면 됨
인터뷰를 하러 가기 전에 자신이 사용할 모든 언어의 사용법 및 문법을 제대로 숙지해야함
(C++ 프로그래밍을 마지막으로 건드려본지 몇년 지났다면 적당한 C++ 레퍼런스 가이드를 펼쳐 중요한 내용 체크!)
1.4 의사소통의 중요성
자신이 사용할 언어를 가다듬고 가능하면 가장 좋은 코드를 만들자.
인터뷰어가 정말로 원하는 것은 지원자가 문제를 푸는 각 단계들을 어떻게 진행하는지 보는 것임
지속적으로 무슨일을 하고 있는지 설명하도록 하자
2. 문제해결
인터뷰 문제를 해결하는 조직적인 방법을 알아보면,
1) 문제를 확실히 이해한다
- 문제를 이해하지 못했을 경우 주저하지 말고 인터뷰어에게 문제에 대한 질문을 해야함
2) 일단 문제를 이해하고 나면 몇 가지 예를 들어본다
- 예를 시도하다보면 문제를 어떻게 풀어야 할지 감을 잘을 수도 있다.
3) 문제 풀이에 사용할 알고리즘에 초점을 맞춘다
- 보통 이 과정은 시간이 오래 걸리는 단계임. 부담을 가지지 말고, 인터뷰어와 대화를 통해 무엇을 하고 있는지를 보여줘야함
4) 알고리즘과 구현 방법을 알아내고 나면 인터뷰어에게 풀이를 설명한다.
5) 코딩을 할 때도 뭘 하고 있는지 설명한다.
- 조용히 코드만 적는 방법은 그리 좋지 않다.
6) 필요하다면 질문을 한다
7) 코드를 완성하고 나면 바로 몇 가지 예를 시도해 보고 맞는지 확인한다
8) 모든 오류 및 특별 케이스, 특히 경계 조건을 확인한다
- 문제를 이해하지 못했을 경우 주저하지 말고 인터뷰어에게 문제에 대한 질문을 해야함
2) 일단 문제를 이해하고 나면 몇 가지 예를 들어본다
- 예를 시도하다보면 문제를 어떻게 풀어야 할지 감을 잘을 수도 있다.
3) 문제 풀이에 사용할 알고리즘에 초점을 맞춘다
- 보통 이 과정은 시간이 오래 걸리는 단계임. 부담을 가지지 말고, 인터뷰어와 대화를 통해 무엇을 하고 있는지를 보여줘야함
4) 알고리즘과 구현 방법을 알아내고 나면 인터뷰어에게 풀이를 설명한다.
5) 코딩을 할 때도 뭘 하고 있는지 설명한다.
- 조용히 코드만 적는 방법은 그리 좋지 않다.
6) 필요하다면 질문을 한다
7) 코드를 완성하고 나면 바로 몇 가지 예를 시도해 보고 맞는지 확인한다
8) 모든 오류 및 특별 케이스, 특히 경계 조건을 확인한다
=> 코드가 제대로 만들어졌다는 판단이 들면 인터뷰어가 코드에 대한 질문을 몇 가지 던질 것이다.
보통 이런 추가 질문에는 실행시간이나 또 다른 구현 방법, 복잡도 등에 초점을 맞춘다
2.1 문제를 풀다가 막히는 경우
인터뷰어는 문제에 대한 답을 바로 알아낼 수 없는 경우에 지원자가 어떤 식으로 반응하는지를 살펴보고 싶어하기 마련.
문제를 풀다가 갑자기 막히게 됐을 때 포기하거나 좌절하는 것은 최악의 대응책이다.
계속해서 흥미를 보이고 풀려고 시도하는 모습을 보이자
* 예를 다시 따져본다
- 특정 예에서 일반적인 경우로 확장을 해보고 그로부터 풀이를 도출해보자.
* 다른 자료 구조를 사용해 시도해 본다.
* 언어에서 그리 많이 쓰이지 않는 기능 또는 고급 기능을 고려해 보자.
- 다른 자료구조, 언어ㄱ의 고급 기능이 문제 풀이의 핵심이 되는 경우도 있다.
3. 풀이 분석
3.1 빅 오 분석법(big-O analysis)
입력 값의 개수에 따라 알고리즘이 수행되는데 걸리는 시간을 바탕으로 알고리즘의 효율성을 평가하는 실행 시간 분석법
(입력의 개수 n이 매우 큰 경우의 실행시간인 점근적인 실행시간을 따지기 때문에 상수항은 무시함
(n이 매우 커질 때 가장 큰 항만 남기고 다른 항은 무시함)
(입력의 개수 n이 매우 큰 경우의 실행시간인 점근적인 실행시간을 따지기 때문에 상수항은 무시함
(n이 매우 커질 때 가장 큰 항만 남기고 다른 항은 무시함)
3.2 빅 오 분석법을 적용하는 방법
1) 입력 값이 무엇인지 확인하고 어떤 것을 n으로 놓아야 할지 결정한다.
2) 알고리즘에서 수행해야 할 연산 횟수를 n의 식으로 표현한다
3) 차수가 제일 높은 항만 남긴다
4) 모든 상수 인수를 없앤다
2) 알고리즘에서 수행해야 할 연산 횟수를 n의 식으로 표현한다
3) 차수가 제일 높은 항만 남긴다
4) 모든 상수 인수를 없앤다
때론 최선 케이스, 평균 케이스, 최악 케이스의 실행 시간을 따져봐야 하는 문제도 생김.
