LeetCode 문제를 풀다가 In-place 알고리즘 방식으로 해결해야해서 학습한 내용이다.
In-place Algorithm
Definition
한국어로 제자리 알고리즘이라고 부른다.
위키에 따르면 CS에서 제자리 알고리즘은 자료구조를 추가로 사용하지 않고 입력을 변환하는 알고리즘이다. 여기서 자료구조란 배열, 객체, 스택 등이다.
보통 추가적인 변수를 위해 약간의 추가 저장 공간은 허용된다.
일반적으로 알고리즘이 실행되면서 입력값이 출력값으로 덮어써지는데 입력값을 출력값으로 교체하거나 요소의 위치를 바꾸는 방식으로 업데이트된다.
제자리란 의미는 가장 엄격하게는 함수 호출 및 포인터까지 포함하여 고정된 양의 추가 공간만 가지는 것을 의미한다.
An in-place algorithm is an algorithm that does not need an extra space and produces an output in the same memory that contains the data by transforming the input ‘in-place’. However, a small constant extra space used for variables is allowed.
( 제자리 알고리즘은 추가적인 저장 공간을 필요하지 않고 입력을 변환한 데이터가 동일한 메모리에 포함된 출력을 생산하는 알고리즘이다. 하지만, 변수를 위한 작은 일정한 추가적인 공간은 허용된다. )
Example
배열을 역순으로 변환하고자 할때 이를 수행하는 간단한 방법은 동일한 크기의 새 배열을 만들고 기존 배열의 각 항목을 복사하는 방식이다.
function reverseArray(arr,n)
{
let rev = new Array(n);
for (let i = 0; i < n; i++)
rev[n - i - 1] = arr[i];
}이 방법은 새 배열을 위한 O(n)의 추가적인 저장 공간이 필요하기 때문에 제자리 알고리즘 방식이 아니다.
function reverseArray(arr,n)
{
for (let i = 0; i < n / 2; i++)
arr[i] = __(arr[n - i - 1],
arr[n - i - 1] = arr[i]);
}위 방법은 요소를 교체하기 위한 O(1)의 추가적인 저장 공간만 필요하기 때문에 제자리 알고리즘 방식이다.
버블 정렬, 빗 정렬, 선택 정렬, 삽입 정렬, 힙 정렬, 셸 정렬 등을 비롯한 많은 정렬 알고리즘이 배열을 제자리에서 정렬된 순서로 재배열한다. 이러한 알고리즘에는 몇 개의 포인터만 필요하다.
