4. 알고리즘

4. 알고리즘 질문

복잡도

1. 시간 복잡도와 공간 복잡도란 무엇인가요?
2. Big-O 표기법을 설명해주세요.
3. O(1), O(log n), O(n), O(n log n), O(n²)의 예를 들어주세요.
4. 최선, 평균, 최악 시간 복잡도의 차이는 무엇인가요?
5. 상각 시간 복잡도란 무엇인가요?
6. vector의 push_back이 상각 O(1)인 이유는 무엇인가요?
7. 재귀 알고리즘의 공간 복잡도는 어떻게 계산하나요?

탐색·정렬

8. 선형 탐색과 이진 탐색의 차이는 무엇인가요?
9. 이진 탐색이 가능한 조건은 무엇인가요?
10. 이진 탐색 구현 시 발생하기 쉬운 버그는 무엇인가요?
11. 버블 정렬, 선택 정렬, 삽입 정렬을 설명해주세요.
12. 퀵 정렬의 동작 방식을 설명해주세요.
13. 퀵 정렬의 최악 복잡도는 왜 O(n²)인가요?
14. 병합 정렬의 장단점은 무엇인가요?
15. 힙 정렬의 특징은 무엇인가요?
16. 안정 정렬이란 무엇인가요?
17. 제자리 정렬이란 무엇인가요?
18. 거의 정렬된 데이터에는 어떤 정렬이 유리한가요?
19. 작은 데이터에는 삽입 정렬이 유리할 수 있는 이유는 무엇인가요?

그래프 알고리즘

20. DFS와 BFS의 차이는 무엇인가요?
21. DFS와 BFS는 각각 어떤 자료구조를 사용하나요?
22. 최단 경로 탐색에 BFS를 사용할 수 있는 조건은 무엇인가요?
23. 다익스트라 알고리즘을 설명해주세요.
24. 다익스트라에서 음수 간선을 사용할 수 없는 이유는 무엇인가요?
25. A* 알고리즘을 설명해주세요.
26. A*의 휴리스틱 함수는 무엇인가요?
27. A*가 항상 최단 경로를 보장하려면 어떤 조건이 필요한가요?
28. 플로이드-워셜 알고리즘은 언제 사용하나요?
29. 위상 정렬은 무엇인가요?
30. 위상 정렬은 어떤 그래프에서 가능한가요?
31. 최소 신장 트리는 무엇인가요?
32. 크루스칼과 프림 알고리즘의 차이는 무엇인가요?

게임 관련 알고리즘

33. 게임에서 상태 머신은 어떻게 구현하나요?
34. FSM의 장단점은 무엇인가요?
35. FSM 상태가 많아질 때 발생하는 문제는 무엇인가요?
36. 행동 트리와 FSM의 차이는 무엇인가요?
37. 길 찾기에서 NavMesh와 A*의 관계를 설명해주세요.
38. 충돌 검사에서 broad phase와 narrow phase의 차이는 무엇인가요?
39. 선분과 구의 충돌을 어떻게 계산하나요?
40. 레이와 삼각형의 교차를 어떻게 판정하나요?
41. 랜덤 드롭 확률 시스템을 어떻게 구현하나요?
42. 가중치 랜덤 선택은 어떻게 구현하나요?
43. 중복 없는 랜덤 선택은 어떻게 구현하나요?
44. 쿨다운 시스템을 어떻게 설계하나요?
45. 수천 개의 타이머를 효율적으로 관리하려면 어떻게 하나요?
46. 우선순위 큐를 타이머 시스템에 사용할 수 있는 이유는 무엇인가요?