Study_farobi

1. 예증법 : 특정한 사례들을 나열한 뒤 그 안에서 일반적인 규칙을 찾는다.

2. 패턴 매칭 : 풀어야 할 알고리즘과 비슷한 문제를 생각해내고 비슷한 문제의 풀이법을 수정하여 풀어야 할 알고리즘을 만들어낸다.

3. 단순화와 일반화 : 문제를 단순화하여 푼 뒤, 알고리즘이 구해지면 일반화

4. 초기 사례로부터의 확장 : n=1, n=2, n=3,... 식으로 확장하여 규칙을 찾아낸다. 보통 재귀 알고리즘으로 구현된다.

5. 자료구조 브레인스토밍 : 자료구조들을 차례차례 적용해보고 해결되는지 본다. 

기술 문제를 푸는 다섯 단계

1. 문제의 모호한 점에 대하여 면접관에게 질문을 한다.

-명확하지 않은 부분에 대해 질문

-좋은 질문 : 자료형은 무엇인가?/데이터의 양은?/어떤 가정을 해야하는가?/사용자는 누구인가?

2. 알고리즘을 설계한다.

-시간과 공간복잡도는?

-데이터가 많아지면 어떻게 되는가?

-내 설계로 인해 다른 문제가 발생하지 않는가?(변형 이진 탐색 트리를 만들었을 경우 나의 설계가 기존의 삽입, 탐색, 삭제 시간에 영향을 미치지는 않는가?)

-다른 이슈나 한계점이 있다면 적절한 타협안을 만들었는가? 타협안이 최적으로 동작하지 않는 시나리오는?

-데이터의 특징이 명시되어 있다면 그 특징을 활용하였는가?

-처음부터 완벽할 수 없으니 시작 코드를 최적화시켜 나가면 됨

3. 가상코드(수도코드)를 먼저 작성한다.

-면접관에게 후에 코드로 변환할 것이라 알리는 것이 좋음

4. 코드를 작성한다.

-자료구조를 충분히 활용 : 기존의 자료구조를 활용하거나 스스로 정의하여 사용

-코드가 복잡하게 보이지 않도록 : 정중앙부터 써내려가지 말고 왼쪽 위부터

5. 코드를 테스트하고, 오류를 교정한다.

-테스트 경우

• 극단적인 경우 : 0, null, 음수, 최댓값, 최솟값
• 사용자 실수 : 올바른 값의 입력이 아닌 이상한 값(null, 음수, ...)
• 일반적인 경우

-알고리즘이 복잡하거나 복잡한 연산이 포함되어 있다면 코딩 도중에 테스트해볼 것

-실수 발견시 왜 그 버그가 발생하게 됐는지 이유를 찾을 것(깊이 생각하고 수정해야 함)

제자리 정렬 알고리즘 : 정렬 시 추가적인 메모리를 필요로 하지 않는 정렬 알고리즘을 말함

• 선택정렬/삽입정렬 - 제자리 정렬 알고리즘
• 퀵정렬/머지정렬 - 제자리 정렬 알고리즘 X

불안정/안정 정렬 알고리즘 : 같은 값일 경우 정렬 순서가 기존의 순서와 일치하지 않고 바뀌는 알고리즘

• 예를 들어 3, 2(1), 6, 8, 4, 2(2) 일 경우

불안정 정렬 알고리즘 : 2(2), 2(1), 3, 4, 6, 8

안정 정렬 알고리즘 : 2(1), 2(2), 3, 4, 6, 8

식으로 기존의 정렬 순서가 바뀌는 것을 불안정 정렬 알고리즘 이라고 함

• 정렬 순서를 정하는 값을 키(key) 라고 함