급수표

제목 없는 데이터베이스

중요한 포인트

1. 면접관에게 문제의 모호한 부분에 대해서 묻는다.
   • 자료형, 데이터의 수, 어떤 가정이 포함되어 있는지, 사용자는 누구인지
2. 알고리즘을 설계한다.
   • 시간과 공간 복잡도
   • 데이터의 수
   • 파생되는 이슈 살피기
   • 트레이드오프
3. 가상코드 작성
4. 실제코드 작성
   • 자류 구조를 풍부하게 사용
   • 한가지 일을 하는 함수, 모듈성, 가독성, 정확성
5. 테스트를 하면서 오류 살피기
   • Worst case
   • Average case
   • 그 외 사용자 실수 에러

알고리즘 설계의 다섯가지 접근법

1. 예증 Examplify
   • 문제를 구성하는 특정한 사례들을 나열.
2. 패턴 매칭 Pattern matching
   • 풀어야 할 알고리즘이 어떤 문제와 유사한지 살피기
3. 단순화와 일반화
   • 다단계 접근법으로 진행.
   • 자료형이나 데이터 양과 같은 제약 조건들을 변경
4. 초기사례로부터의 확장 Build by base case
   • 초기 사례에 대해서 풀고, 다음 가정, 그 다음 가정, …
   • n=1, n=2, n=3, …
5. 자료구조 브레인스토밍
   • 일련의 자료구조를 차례차례 적용해보고 해결되는지 보기

자료구조

1. HashTable : key를 value에 대응 (hash function을 사용하므로 O(1) 접근)
   • 내부를 이진 탐색 트리로 구성하면 탐색에 O(log n)
2. List : 노드간의 연결로 이루어지는 구조
   • Runner 기법 (1 step pointer, 2 step pointer)
   • 재귀로 푸는 경우가 많음 (재귀는 스택에 쌓이므로, 공간복잡도 추가)
3. Stack (LIFO) / Queue (FIFO)
4. Tree
   • 이진 트리 vs 이진 탐색 트리
   • 균형 vs 비균형
   • 이진 트리 순회
     • 정순회 (왼, 중간, 오른), 후순회, 전순회
   • 트라이: n-차 트리
5. Graph
   • 깊이 우선 탐색 DFS : 그래프 내의 모든 노드를 방문하고 싶다거나, 찾는 것을 발견할 때까지 모든 노드를 적어도 한 번은 방문하도록 하고 싶을 때.
   • 너비 우선 탐색 BFS : 큐를 사용해 순환적 형태로 구현하는 것이 보통은 가장 잘 동작