제자리 알고리즘(in‑place algorithm)은 추가적인 메모리를 거의 사용하지 않고 입력 데이터를 직접 변형하여 문제를 해결하는 알고리즘을 말한다. 일반적으로 알고리즘이 사용하는 보조 메모리의 크기가 입력 크기에 비해 상수 수준(constant space, O(1))이거나, 입력 크기의 로그(log N) 수준 이하인 경우 제자리 알고리즘이라고 한다.
특징
- 공간 효율성: 외부 배열이나 리스트 등을 별도로 할당하지 않으며, 입력 배열 자체를 재배열하거나 필요한 경우 몇 개의 임시 변수만 사용한다.
- 시간 복잡도와의 관계: 제자리 구현이 가능하다고 해서 반드시 시간 복잡도가 낮은 것은 아니다. 경우에 따라 제자리 버전이 비제자리 버전에 비해 실행 시간이 증가할 수 있다.
- 복원성: 입력 데이터를 원래 상태로 복구해야 하는 경우가 아니라면, 제자리 알고리즘은 입력 데이터를 파괴적으로 변형한다는 점에 유의한다.
주요 예시
| 문제 | 비제자리 구현 | 제자리 구현 |
|---|---|---|
| 정렬(예: 퀵소트, 힙소트, 삽입정렬) | 추가 배열을 사용해 복사 | 입력 배열 내부에서 요소를 교환 |
| 배열 회전(예: 회전 알고리즘) | 임시 배열에 복사 후 복사 백 | 반전(reverse) 연산을 이용한 제자리 회전 |
| 문자열 뒤집기 | 새 문자열 생성 | 두 포인터를 이용해 제자리 교환 |
| 그래프 탐색(DFS) | 스택을 별도로 할당 | 재귀 호출 스택 사용(재귀 깊이 제한에 따라 메모리 사용이 달라질 수 있음) |
구현상의 고려사항
- 인덱스 관리: 제자리 연산은 인덱스가 겹치지 않도록 주의해야 하며, 종종 두 포인터 기법(two‑pointer)이나 사이클 교환(cycle swapping) 등을 활용한다.
- 오버플로우 위험: 임시 변수 수가 제한적이므로, 큰 데이터 타입(예: 64비트 정수)을 다룰 때는 연산 중 오버플로우가 발생하지 않도록 검증이 필요하다.
- 재귀 사용: 재귀 기반 제자리 알고리즘은 호출 스택을 이용하므로, 입력 크기에 따라 스택 오버플로우가 발생할 위험이 있다. 이 경우 반복적(iterative) 구현으로 전환한다.
관련 용어
- 제자리 정렬(in‑place sort): 정렬 과정에서 추가적인 배열을 사용하지 않는 정렬 알고리즘. 예: 퀵소트, 힙소트, 삽입정렬 등.
- 제자리 변환(in‑place transformation): 데이터 구조를 새로운 형태로 변환하면서 별도의 메모리를 할당하지 않는 변환 작업.
참고 문헌
- Cormen, Thomas H., et al. Introduction to Algorithms, 3rd ed., MIT Press, 2009. – 제자리 알고리즘 및 제자리 정렬에 관한 설명.
- Knuth, Donald E. The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison‑Wesley, 1998. – 제자리 정렬 기법에 대한 상세 논의.
※ 위 내용은 널리 인정받는 컴퓨터 과학 교과서와 학술 자료에 기반한다. 추가적인 최신 연구나 구현 사례에 따라 구체적인 메모리 사용량은 달라질 수 있다.