[자료구조] 만두의 연결 리스트(Linked List)와 Soft Delete
토요일 아침 알고리즘 스터디에서 새롭게 배운 문제 풀이 방식인데, 연결 리스트에 Soft delete를 접목하여 계산 시간을 최적화하는 아이디어이다. (이 스터디에 관심 있는 사람들의 연락을 기다리겠다.)
일단 해당 알고리즘 문제에 대해서 간략하게 소개하자면 객체를 관리하는 메서드를 5가지 정의하는 문제이다. 메서드들은 다음과 같다.
1. 객체를 추가하는 메서드
2. 객체를 삭제하는 메서드
3. 특정 객체의 데이터를 변경하는 메서드
4. 특정 그룹의 객체들의 데이터를 모두 변경하는 메서드
5. 특정 그룹의 가장 큰 데이터를 가진 객체를 조회하는 메서드
그냥 보기에는 단순하게 CRUD를 구현하면 되는 문제 같지만 5번 메서드를 제외한 나머지 메서드의 호출 횟수는 100,000번 이하라는 조건 때문에 1번부터 4번까지의 메서드에서 최대한 O(1)에 가깝도록 성능 최적화가 필요했다. 처음에는 그룹을 기준으로 잡아서 그룹이 Key, 객체 리스트가 Value인 해시맵에 관리하면 된다고 생각했다. 그런데 삭제, 수정에서 결국 어딘가에서는 순회를 해야 하는 문제가 있었고 시간은 제한시간보다 훨씬 느렸다. 여기서 해결방법으로 스터디원이 알려준 아이디어를 훔쳐서 모두에게 소개해보도록 하겠다.
Soft Delete가 뭐지?
논리적인 삭제
데이터를 삭제해도 메모리에는 데이터가 저장되어 있는 것
Soft Delete는 메모리에는 데이터가 남아있어서 삭제되었다고 생각해도 실제로는 삭제되지 않은 것이다. 보통 Soft Delete는 데이터베이스에서 사용하는 개념이지만 이번에는 알고리즘에 적용해 보겠다. 최적화를 하면서 문제가 된 부분은 수정과 삭제에서 특정 객체를 찾기 위해 순회해야 한다는 것이었다. 그렇다면 어떻게 구현해야 할까?
간단한 구현으로 알아보자
버전을 기록해서 Soft Delete를 하면 된다. 객체를 저장할 자료구조는 후술 할 메서드의 최적화를 위해서 연결 리스트를 사용했다.
먼저 객체에 버전을 기록한다.
public class Data {
int id;
int version;
}그리고 객체의 버전을 기록하는 배열을 작성한다. 이 문제에서는 객체에 정수 아이디가 존재해서 index를 아이디라고 생각했다.
| index | 1 |
| version | 1 |
객체를 추가하는 메서드
삽입은 새로운 노드를 리스트의 꼬리 부분에 붙히면 된다.
객체를 삭제하는 메서드
삭제하는 메서드는 보통 구현할 때 메모리에서 데이터를 삭제하는 Hard Delete로 구현한다. 처음 접근을 객체를 저장하는 리스트에서 삭제하도록 구현해서 원하는 객체를 삭제하기 위해서 순회해야 하는 문제가 있었다. 하지만 Soft Delete로 구현하면 간단하게 해결된다. 단순히 버전을 관리하는 배열에서 해당 객체의 버전을 음수로 바꿔주면 삭제했다는 뜻이 된다.
| index | 1 |
| version | -1 |
실제 메모리에는 여전히 이전 버전으로 객체가 남아있고, 추후에 해당 객체를 탐색할 때 버전을 기록하는 배열과 비교해서 유효한 객체인지 판단하면 된다.
특정 객체의 데이터를 변경하는 메서드
특정한 객체의 데이터를 변경할 때도 Soft Delete를 삭제하면 순회할 필요가 없다. 이전 구현으로는 배열에 저장된 특정 객체를 찾아서 값을 변경해주었는데, 이제 메모리에는 버전이 1 증가한 객체를 새로 저장하고 버전을 관리하는 배열의 버전 값도 1 증가하면 된다. 이전의 객체는 여전히 메모리에 남아있지만 버전 배열의 버전과 달라 유효하지 않은 객체가 된다.
| index | 1 |
| version | 2 |
| 메모리에 존재하는 객체 | {id: 1, version: 1}, {id: 1, version:2} |
| 논리 상으로 존재하는 객체 | {id: 1, version: 2} |
특정 그룹의 객체들의 데이터를 모두 변경하는 메서드
이 메서드에서는 해시맵과 연결 리스트의 특징을 이용했다. 제약조건에서 데이터가 최소 1에서 5까지 다섯가지 밖에 되지 않았기 때문에 데이터를 Key, 객체를 Value로 하는 배열로 데이터가 저장된 상태였다.
데이터를 2에서 1로 바꾸기 위해서는 리스트의 head를 변경할 데이터의 리스트 마지막에 이어붙혀주면 된다.
특정 그룹의 가장 큰 데이터를 가진 객체를 조회하는 메서드
이 문제에서는 한 테스트 케이스에서 실행횟수 100회 제한이 있어서 시간을 크게 신경 쓰지 않고 브루트 포스로 구현해도 괜찮다.
글을 마치며
사실을 고백하자면 이론상으로만 정리한 문제이고 아직 정확한 구현은 안 했다. 😅 그래서 정확히 아이디어를 이해하고 있는 건지 검증되지는 않았다.
구현을 안 해본 걸 감안하더라도 이 문제에 대해서 공부하면서 배운 점이 많은 것 같다. 알고리즘 문제 내의 아이디어와 자료 저장구조는 너무 문제 풀이만을 위한 코드라서 그대로 개발 코드에 적용할 수는 없겠지만, 이런 경우에서 자료구조가 생각보다 시간적인 부분에서 많은 영향을 미쳤다. 실제로 개발을 하면서 언제부터인가 무지성으로 배열과 리스트에 데이터를 관리했었는데, 데이터에 맞는 자료구조 사용이 성능을 크게 끌어올릴 수 있는 것을 체감할 수 있었다.