책너두 (코딩 인터뷰 완전분석) 6일차 (~108p)

요약

• 기술적 문제
  • 준비하기
  • 알고 있어야 할 것들
    • 핵심 자료구조, 알고리즘, 기본 개념
    • 2의 승수(power of 2) 표
  • 실제 문제 살펴보기
    • 원하는 것이 무엇인가.
  • 최적화 및 문제풀이 기술 #1: BUD를 찾으라
  • 최적화 및 문제풀이 기술 #2: 스스로 풀어보라 DIY(Do Iy Yourself)
  • 최적화 및 문제풀이 기술 #3: 단순화 일반화하라
  • 최적화 및 문제풀이 기술 #4: 초기 사례(base case)로부터 확장하기(build)
  • 최적화 및 문제풀이 기술 #5: 자료구조 브레인스토밍

메모

7. 기술적 문제

준비하기

• 이 책에 실린 문제를 만날 때마다 다음과 같이 하라

1. 직접 풀도록 노력하라
   • 답을 보지 않고 직접 풀려고 노력하라
   • 공간과 시간 효율에 대해서 반드시 생각하라
2. 코드를 종이에 적으라
   • 코드를 작성하고 수정하는 데 오래 걸리는 환경에 익숙해지라
3. 코드를 테스트하라
   • 일반적인 경우 뿐 아니라, 기본 조건, 오류 발생 조건 등을 전부 테스트 하라.
4. 종이에 적은 코드를 그대로 컴퓨터로 옮긴 뒤 실제로 실행해 보라
   • 종이에 적으면서 실수한 것들의 목록을 만들고, 실제 면접장에서 실수하지 않도록 유의하라.

• 가상 면접을 가능한 많이 해봐라.

알고 있어야 할 것들

핵심 자료구조, 알고리즘, 기본 개념

• 이진 트리의 균형을 맞추는 특정 방법, 혹은 기타 복잡한 알고리즘에 대한 질문을 하지 않음.
  • 면접관이 기대하는 것은 기본기임.
• 자료구조
  • 연결리스트
  • 트리, 트라이, 그래프
  • 스택, 큐
  • 힙
  • Vector, ArrayList
  • 해시테이블
• 알고리즘
  • 너비 우선 탐색
  • 깊이 우선 탐색
  • 이진 탐색
  • 병합 정렬
  • 퀵 정렬
• 개념
  • 비트 조작
  • 메모리 (스택 vs 힙)
  • 재귀
  • 동적 프로그래밍
  • big-O 시간 & 공간
• 위 주제에 대해 사용법, 구현법, 공간과 시간 복잡도에 대해서 알아두길 바란다.
• 자료구조와 알고리즘은 밑바닥부터 직접 구현해보는 것이 좋다.
  • 자료구조가 내부적으로 어떻게 돌아가는지 이해할 수도 있음.
• 특히, 해시테이블은 매우 중요한 주제임
  • 이 자료구조를 아주 능숙하게 다룰 수 있도록 연습하길 바란다.

2의 승수(power of 2) 표

• 규모 확장성 및 메모리 제한과 관련된 문제를 풀 때 유용함.
  • 이 표를 반드시 외울 필요는 없지만 암기해 두면 꽤 유용하게 쓰임.
  • 적어도 쉽게 유도할 수 있을 정도로 익숙해지길 바란다.

실제 문제 살펴보기

• p 93 순서도에 어떻게 문제를 풀어야 하는지 정리되어 있음.
  • 실제로 연습할 때 이 순서도를 사용하라
  • 순서도 외에 다양한 자료들이 https://www.crackingthecodinginterview.com 에서 다운받을 수 있음.

원하는 것이 무엇인가.

• 면접 문제는 어렵기에 모두 즉시 답하지 못해도 괜찮음.

1. 문제 설명 듣기
2. 예제
3. 무식하게 풀기
4. 최적화
5. 검토하기
6. 구현하기
7. 테스트

• 면접관이 하는 말을 잘 들어야 한다.

1. 경청하기
   • 반드시 문제를 잘 듣고 정확히 이해했는지 확인해야 함.
   • 문제와 관련된 모든 독특한 정보를 머릿속에 기억해 둬야 함.
2. 예제를 직접 그려보기
   • 머릿속으로 생각하는 것보다 차원이 다른 문제풀이 능력을 발휘할 수 있을 것임
   • 예제를 만들 때 다음을 유의해야 함.
     • 명확한 예제를 쓰라
     • 충분히 큰 예제를 쓰라
     • 특별한 예제를 지양하라
3. 무식한 방법으로 일단 해보기
4. 최적화
   • 간과한 정보가 있는지 찾아보자
   • 새로운 예제를 만들어 보자
   • 잘못된 방식으로 문제를 풀어보자
   • 시간과 공간의 실익을 따져 보고 균형을 맞추라
5. 검토하기
6. 코드 작성하기
   • 모듈화된 코드를 사용하라
   • 에러를 검증하라
   • 필요한 경우, 다른 클래스나 구조체를 사용하라
   • 좋은 변수명을 사용하라
7. 테스트
   • 개념적 테스트부터 시작하라
   • 코드에서 평소와는 다르게 돌아가는 부분을 유심히 살펴보라
   • 버그가 자주 발생하는 부분을 유심히 살펴보라
   • 작은 규모의 테스트를 돌려보라

최적화 및 문제풀이 기술 #1: BUD를 찾으라

• 병목현상
  • 어떤 부분 때문에 알고리즘이 느려지는 경우
  • 검색을 여러 번하는 것처럼 반복적으로 수행하는 부분이 여러 개 있는 경우
• 불필요한 작업
  • 시간복잡도를 줄일 수 있음.
• 중복되는 작업
  • 이 또한 시간복잡도를 줄일 수 있음.

최적화 및 문제풀이 기술 #2: 스스로 풀어보라 DIY(Do Iy Yourself)

• 질문을 받으면 실제 예제를 통해 직관적으로 문제를 풀어 나가려는 노력을 하길 바란다.

최적화 및 문제풀이 기술 #3: 단순화 일반화하라

• 단순화와 일반화를 이용하여 어려 단계에 걸친 접근법을 구현할 것임
  1. 자료형(data type)과 같은 제약조건을 단순화하거나 변형시킨다.
  2. 단순화된 버전의 문제를 푼다
  3. 단순화된 문제의 알고리즘이 완성되면 해당 알고리즘을 보다 복잡한 형태로 다듬어 간다

최적화 및 문제풀이 기술 #4: 초기 사례(base case)로부터 확장하기(build)

• 초기 사례(ex: n=1) 에 대한 문제를 푼 뒤, 해법을 확장해 나간다.
  • n=1 에서 구한 해법을 이용해서 n=3 혹은 n=4 같이 좀 더 복잡한 경우의 해법을 구해 나간다.

최적화 및 문제풀이 기술 #5: 자료구조 브레인스토밍

• 단순하게 일련의 자료구조를 차례로 살펴보면서 하나씩 적용해 보면 된다.