in place 알고리즘에 대해서 간단하게 알아봅시다.
정렬 알고리즘을 배우면서, stable 한지 그렇지 않은지는 많이 본 거 같습니다. 그런데 in-place 한지 여부도 분명 다룬 거 같았습니다. 그런데, 저는 이 부분에 대해서 잘 신경을 쓰지는 않았는데요. 쉽게 간과할 정도로 무지했던 셈입니다. 정리할 겸 겸사겸사 알아보도록 하겠습니다. 먼저, in place 알고리즘은 추가적인 메모리를 쓰지 않는 알고리즘? 그런데 아주 약간의 메모리를 써도 되는 알고리즘 정도로 문서에서 언급하고 있어요. 제가 보는 교과서에서는 constant한 공간을 쓰면 in-place 알고리즘이라고 언급하고 있습니다만, 대충 인풋 크기에 비해 정말 작은 메모리를 쓴다. 정도로만 이해하고 넘어가셔도 좋겠네요. 대충 input size가 500만 정도라고 생각해 보면, int나 l..
자료알고/알고리즘
2021. 9. 27. 04:21
최근댓글