O(1)의 시간복잡도를 가지는 정렬 알고리즘 알려주세요!

Question

편입면접을 봤는데 교수님이 위에 제목에 쓴것처럼 물어보셨습니다 제가 생각하기로는 O(1)가지는 알고리즘이 없어서 해쉬테이블이나 정렬되지않는 배열의 경우를 말씀드렸는데 혹시 이게 답이아니라면 명확한 답변이 궁금합니다!

김대현 · Accepted Answer

회사 면접이든, 학교 면접이든, 가끔 답이 없는 걸 물어보는 경우가 있습니다. 없는 답이나 잘못된 질문에  어떻게 대처하는지를 묻는 겁니다. 사실 어찌보면 한두 질문 쯤은 그런 질문이 더 유용할 수도 있겠습니다. 학교 시험을 떠난 현실 세계에는, 답이 없는 경우가 더 많고, 질문을 잘못 잡아서, 엉뚱한 답을 찾거나 헤매게 되는 경우가 많으니까요.

그런게 있다고 아는 척 딴 소리를 했으면 안 좋은 점수를 받았을 테고, 뭔가 창의적인 답변을 했다면 재미 점수를 받았을 수도 있고, 아니면 그런 게 없는 걸로 안다고 조리있게 설명했으면 된 거일 겁니다.

재미삼아, ChatGPT에게도 물어봤습니다. 다행히(?), 그리고 심심하게도 없다고 하네요.