- 문제 : https://www.acmicpc.net/problem/2164
- PR : https://github.com/moonlight-duck/study-algorithms/pull/8
백준 2164번 문제에 대해서 답은 도출했지만, 메모리 초과와 시간 초과 관련해서 겪은 이슈에 대해서 작성해봅니다.
1. 메모리 초과
시도한 방법)
class로 Queue 자료형을 만들어서 맨위에 카드버리는 함수(discardTop) 맨위에 카드 맨뒤로 옮기기 함수(moveToBack)를 만들어서 while 문으로 Queue 데이터가 1개 나올때까지를 반복하도록 로직을 작성하였습니다.
메모리 초과 이슈 발생)
아마 원인은 slice때문인 것 같습니다. slice는 배열의 일부를 잘라내서 새로운 메모리에 할당하여 반환하는 함수 입니다. for문에서 discardTop, moveToBack함수를 실행할때마다 slice 함수가 실행되는데 이때 계속 메모리를 새로 할당하여 메모리 초과 이슈가 발생하는 것 같습니다.
IF) N이 500,000이라면, 기존 배열과 거의 동일한 크기의 새로운 배열이 메모리에 계속 할당됩니다. 이전 배열은 가비지 컬렉션의 대상이 되지만, 이 과정이 매우 빈번하게 일어나면서 메모리 사용량이 급증하여 결국 제한을 초과하게 됩니다.
2. 개선시도 1
[백준:251001] 큐 문제(작성중) by min-99 · Pull Request #8 · moonlight-duck/study-algorithms
📌 문제 정보 문제 링크 : https://www.acmicpc.net/problem/2164 카테고리 (예: 구현, 탐색, DP) : 큐 ✏️ 풀이 방법 결과 (성공/실패) : 풀이 시간 : 풀이 방법 : 참고한 글 링크 : ⭐ 비고 추천 여부 : 추가
github.com
slice를 제거하고, 순수하게 javascsript에서 지원하는 shift 함수로 수정하였습니다. 굳이 Queue 자료형을 선언할 필요도 없을 것 같아서 이 부분또한 제거하였습니다.
결과) 이번에는 시간초과가 발생하였습니다..(간단한 문제라고 생각했는데 이렇게 통과하기 어려울 줄이야 😂)
3. 개선시도 2
원인) shift()가 내부적으로 동작하는 방법
1) 첫 번째 칸에 있던 데이터 제거
2) 뒤에 있는 모던 요소들이 한 칸씩 앞으로 이동 (인덱스 재조정)
=> 이 과정에서 배열의 길이가 n개라면, n-1가 모두 앞으로 이동해야 함으로, 시간복잡도는 거의 n에 비례하고, 이에 대한 시간 복잡도는 O(n)이 발생하게 됩니다.
+ 이전에 공부한 O(n)에 대한 시간 복잡도 이슈(시간초과)
시도한 방법)
리서치로 다른 사람들은 어떻게 푸는지를 검색해보고 되었습니다. 그 결과 data는 변경하지 않고 head로 데이터를 읽는 위치만 저장하여 이를 해결한 방법을 보게 되었습니다.
[백준:251001] 큐 문제(작성중) by min-99 · Pull Request #8 · moonlight-duck/study-algorithms
📌 문제 정보 문제 링크 : https://www.acmicpc.net/problem/2164 카테고리 (예: 구현, 탐색, DP) : 큐 ✏️ 풀이 방법 결과 (성공/실패) : 풀이 시간 : 풀이 방법 : 참고한 글 링크 : ⭐ 비고 추천 여부 : 추가
github.com
결과)
4. 문제를 풀고 느낀점
- 유지보수 측면에서 본다면, 첫번째로 시도한 방식이 제일 좋은 방향이 아닌가라는 생각이 들었습니다. 왜냐하면 문제의 요구사항을 그대로 클래스로 추상화하는 방식이 좋다고 생각했습니다. 각 동작이 메서드로 명확히 분리되어 있어 가독성이 높고, 향후 수정이 필요할 때도 용이한, 소위 '잘 설계된 코드'라고 생각했습니다.
- 다만, slice 함수로 인해 매번 새로운 배열을 생성하는 메모리 이슈가 발생할 수 있음에는 동감합니다. 저는 이 부분과 shift(시간초과)를 보면서 모든 것에는 비용이 따른다른 점을 다시금 깨달았습니다. 좋은 코드 = 개발자가 잘 이해할 수 유지보수성이 좋은 코드. 라는 부분이 자리잡아있고, 문제를 풀면서 개발자의 편리함속에 숨겨진 '숨겨진 비용'을 이해하는 것이 체득화가 잘 안되어 있다는 점을 보게 되었습니다.
- 또한, '큐'문제라는 생각에 사로잡혀, 반드시 큐 자료구조를 직접 구현해야 한다는 고정관념도 자리잡고 있었던 것 같습니다. 그러나 이 문제를 잘 해결할 수 있는 핵심은 큐의 개념을 적용하는 것이었고, 배열과 포인터(인덱스)를 응용하는 것만으로도 충분했습니다.
- 단순히 정답을 맞히는 것을 넘어, 코드의 가독성과 성능 사이의 균형을 고민하고, 고정관념에서 벗어나 유연하게 문제를 바라보는 과정 전체가 이번 문제를 통해 얻은 가장 큰 수확이었다고 생각해서 이부분에 대해서 글로 남기고 싶었습니다.
감사합니다 :)
'알고리즘' 카테고리의 다른 글
| 최근접점찾기(Closest Pair) - 분할정복 (0) | 2025.10.16 |
|---|---|
| 합병정렬 - 분할정복 알고리즘(백준 2750문제) (1) | 2025.10.06 |
| 백준 연결리스트 문제 - 시간초과 해결과정(23309번) (0) | 2025.09.29 |
| 백준 연결리스트 문제풀이 접근 (1406번) (0) | 2025.09.28 |
| 백준 Typescript 알고리즘 프로젝트 세팅하기 (1) | 2025.09.26 |