next_permutation : 3단계 최적화를 하면서 분석해 보자.
코딩 테스트에서 next_permutation의 사용 빈도는 상당히 높을 겁니다. 특히 역량 테스트라고 불리는 것에서는요. 구현이 들어가면 대략 50% 정도는 조합, 순열 등에서 나오는데요. 그 때, 이전 순열이라던지 다음 순열을 구하기 위해서 쓰는 함수가 저 함수입니다. 이전 순열은 데이터를 조금 변형을 하면 구할 수 있고요. 그러면 이 함수가 어떻게 구현이 되어 있을까요? 만약에 레퍼런스 없이 구현하라고 하면 어떻게 해야 할까요? 단계별로 이해해 봅시다. 사실 이 함수의 복잡도는 O(n)입니다. 왜 그렇게 나올 수가 있는 것인지, 상대적으로 비효율적인 구현 방법으로 먼저 구현해 보고 이야기 하도록 하겠습니다. O(n^2)의 핵심 접근은, 결정 함수입니다. 이게 무슨 어려운 것이냐라고 생각하실 수도 있..
레퍼런스/분석
2019. 8. 19. 17:59
최근댓글