[PS] 문제 풀이 요령
in PS
cracking the coding interview 6/e 일부 내용입니다.
핵심 자료구조 및 알고리즘
| 자료구조 | 알고리즘 | 개념 |
|---|---|---|
| 연결 리스트 | 너비 우선 탐색 | 비트 조작 |
| 트리, 트라이, 그래프 | 깊이 우선 탐색 | 메모리 |
| 스택, 큐 | 이진 탐색 | 재귀 |
| 힙 | 병합 정렬 | 동적 프로그래밍 |
| 리스트 | 퀵 정렬 | 빅오 시간&공간 |
| 해시 테이블 |
문제 풀이 과정
1. 문제 정확하게 읽고 파악하기
- “정렬된” 배열 두 개가 주어질 때… 와 같이 문제 풀이에 핵심적인 정보를 놓치지 않고 파악
2. 예제 직접 그려보기
- 실제 숫자나 문자열을 사용
- 충분히 큰 예제
- 특별한 케이스가 아니도록 일반적인 예제 그리기
3. 무식한 방법으로 풀어보기
- 최초의 답이 무식해도 괜찮음. 일단 푸는게 중요
- 최적화를 통해 개선하면 됨
4. 최적화
- 해당 알고리즘에서 사용되지 않은 정보가 있는지
- 새로운 예제를 통해 새로운 패턴이 보일수도 있음
- 시간, 공간 복잡도 간 trade-off
- 전처리를 통해 개선할 수 있는지(정렬, 해시테이블 등)
- 여러 자료구조 적용해보기(리스트, 연결리스트, 해시, 힙 등)
- BCR(Best Conceivable Runtime) 과 비교
5. 검토하기
- 알고리즘이 나왔다고 해서 절대로 바로 코딩하지 말 것
- 알고리즘을 완벽하게 이해한 상태에서 머리로 미리 예제 케이스 돌려봄
6. 구현하기
- 짧은 몇 줄로 면접관에게 어필해야 하기 때문에 아름다운 코드를 짜야 함
- 모듈화 된 코드
- 에러 체크
- 변수 이름
7. 테스트
- 개념적 테스트: 머리로 한 줄씩 실행해보면서 변수들이 어떻게 변화하는 지
- 특이한 부분: 루프가
i=1부터 시작한다던지,length - 2에서 끝나는 같은 것들 - 버그가 자주 발생하는 부분: 재귀함수 베이스 케이스, 연결리스트 앞 끝 부분, 이진 트리 널 부분 등
- 실제 예제로 테스트: 서너 개 크기인 배열이면 충분
- 특별한 케이스 예제로 테스트: Null, 단일 원소, 극단적인 입력 등
