"백그라운드 앱은 왜 알아서 꺼질까?"
스마트폰을 쓰다 보면 한 번쯤 겪는 일이 있습니다. 한참 전에 열어둔 앱으로 돌아가니 처음 화면부터 다시 켜지는 경험이요. 메모리가 부족하니까 운영체제가 가장 오래 안 쓴 앱을 슬그머니 종료해버린 거죠.
이 동작을 직접 만들어 본다고 해봅시다. 규칙은 단순합니다.
- •메모리에는 최근 사용한 앱 최대 N개만 살려둔다.
- •앱을 새로 켜는데 자리가 없으면 → 가장 오래 안 쓴 앱을 종료한다.
- •앱으로 전환하면 → 그 앱은 다시 '방금 쓴 앱' 이 된다.
예: N=3에서
MAP → CAM → MSG순으로 켜면 메모리는[MSG, CAM, MAP]. 여기서 MAP으로 전환하면 MAP이 맨 앞으로 올라와[MAP, MSG, CAM]. 이제 새 앱 WEB을 켜면 가장 뒤에 있던 CAM이 종료됩니다.
눈치채셨나요? 이 "최근 N개만 유지" 규칙이 바로 LRU(Least Recently Used) 캐시입니다.
가장 먼저 떠오르는 풀이 (그리고 그 한계)
가장 단순하게는 배열(리스트) 하나로 풀고 싶어집니다. 사용 순서대로 줄을 세워두는 거죠.
앱을 쓸 때마다: 그 앱을 배열에서 찾아 맨 앞으로 옮긴다
자리가 없으면: 배열 맨 뒤를 잘라낸다순서는 깔끔하게 유지됩니다. 하지만 "그 앱을 배열에서 찾는" 그 한 줄이 문제예요. 앱이 N개라면 매번 최대 N칸을 훑어야 하고, 맨 앞으로 옮기느라 뒤 원소들을 줄줄이 미뤄야 합니다. 동작 하나가 O(n). 호출이 10만 번이면 금세 느려집니다.
그럼 반대로 해시맵은 어떨까요? 이름으로 찾는 건 O(1)로 순식간입니다. 그런데 결정적인 게 빠졌습니다. 해시맵은 순서를 기억하지 않아요. "지금 살아있는 앱 중 가장 오래된 게 누구지?"에 답할 수가 없습니다. 종료할 앱을 고르지 못하는 거죠.
| 방법 | 이름으로 찾기 | 가장 오래된 앱 알기 |
|---|---|---|
| 배열만 | O(n) ❌ | O(1) ✓ |
| 해시맵만 | O(1) ✓ | 불가능 ❌ |
한쪽은 검색이 느리고, 한쪽은 순서를 모릅니다. 둘 다 필요한데 말이죠.
왜 "해시맵 + 이중 연결 리스트"일까?
여기서 발상의 전환이 필요합니다. 두 자료구조의 장점만 합치면 되지 않을까요?
- •이중 연결 리스트로 사용 순서를 표현합니다. 맨 앞(HEAD)은 방금 쓴 앱, 맨 뒤(TAIL)는 가장 오래된 앱. 이중(앞/뒤 양방향) 연결이라 노드 하나를 어디서든 O(1)에 떼고 붙일 수 있습니다.
- •해시맵으로 "앱 이름 → 그 노드의 위치"를 저장합니다. 그래서 리스트를 처음부터 훑지 않고도 원하는 노드로 O(1)에 점프할 수 있습니다.
이 둘이 만나면 마법 같은 일이 벌어집니다.
- •앱 전환/재실행 → 해시맵으로 노드를 찾아(O(1)) 그 노드를 HEAD 뒤로 이동(O(1)).
- •메모리 초과 → TAIL 바로 앞 노드를 제거(O(1))하고 해시맵에서도 지운다.
모든 동작이 O(1). 배열의 "순서는 알지만 느린" 약점과 해시맵의 "빠르지만 순서를 모르는" 약점이 서로를 정확히 메워줍니다. 공간은 앱 N개분, 즉 O(N)이고요.
이 패턴은 운영체제의 페이지 교체, 데이터베이스·CDN 캐시, 브라우저 뒤로가기 기록 등 "제한된 공간에 최근 것만 유지" 가 필요한 곳마다 등장합니다. 코딩테스트 단골 주제이기도 하죠.
직접 눈으로 확인하기
해시맵에서 앱을 찾고, 그 노드가 리스트 맨 앞으로 끌려 올라가고, 메모리가 꽉 차는 순간 맨 뒤 앱이 종료되며 빠져나가는 전 과정을 단계별 시각화로 준비했습니다. 해시맵과 연결 리스트가 함께 변하는 모습, switchTo가 적중/미적중하는 순간까지 한눈에 보입니다.