in-place 알고리즘

[mdgarden]

발단

LeetCode 41번 문제
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.
라는 제한이 나옴

이게 무슨 말인지 모르고 엥 배열 하나 더 추가하면 짱쉬운거아닌가? 이게 왜 하드지? 하고 보니 배열을 더 추가하면 안되는거였음

해석

runs in O(n) time = 주어진 배열을 한번만 순회해야한다
and uses O(1) auxiliary space. = 공간 복잡도가 O(1)이어야 한다. = 추가적인 메모리를 사용하면 안된다. = 새로운 배열을 생성하면 안된다

[mdgarden]

"in-place" 알고리즘은 공간 복잡도를 O(1)로 유지하면서도 주어진 문제를 해결할 수 있게 해주지만, 원본 데이터를 변경한다는 점에서 주의가 필요할 수 있습니다. 때로는 원본 데이터를 보존해야 하는 경우가 있기 때문에, 이러한 상황에서는 원본 데이터의 복사본을 만들거나 다른 방법을 고려해야 할 수 있습니다. 하지만 복사본을 만드는 행위 자체가 추가 공간을 사용하는 것이므로, 공간 복잡도 O(1)의 제한 아래에서는 원본 배열을 직접 수정하는 방법이 적합한 접근법입니다.