문제를 푸시다보면 다양한 에러를 만나실텐데요.
오늘은 백준알고리즘 1697번을 풀면서 발생한 메모리 초과에 대해서 글을 써보려고 합니다.
메모리 초과가 발생하는 이유를 간단히 말씀드리자면 '스택 오버플로우'가 발생하기 때문입니다.
문제를 푸시면서 가장 많이 접할 수 있는 경우는 다음 두 경우라고 생각합니다.
1. 너무 많은 변수들을 배열 등에 저장할 경우.
2. DFS 등에서 재귀적 호출을 통해 너무 많은 함수들을 호출할 경우.
저 같은 경우에는, 백준 알고리즘 1697번에서 1번에 의한 메모리 초과가 발생하였는데요.
시작점으로부터 도착점까지 도달할 때 까지, (시작점-1, 시작점+1, 시작점*2)에 해당하는 값들을 탐색하는 과정에서 실수를 했습니다.
시작점 = 5, 도착점 =17을 기준으로 처음 들어간 (5-1,5+1,5*2)에 대해서 다음 싸이클 값들이 어떻게 저장되는지 출력한 것인데요.
아래 스크린샷을 보시면, 하나의 경우의 수에 대하여 계속해서 3가지의 새로운 경우의 수가 들어가고 있습니다.
해당 문제의 시작점과 도착점이 될 수 있는 정수의 범위가 0~100,000 이었으니, 시작점이 1이고 도착점이 100,000일 경우 엄청나게 많은 값들이 큐에 저장되었겠죠?
이로 인해, 계속해서 메모리 초과가 발생하였습니다.
메모리 초과에 대한 해결 방안은 다음과 같습니다.
1. 배열에 너무 많은 값들이 들어가는 경우에는 값이 들어갈 수 있는 범위 제한 및 들어가는 데이터 수를 제한 하는 조건 등을 통해서 해결하실 수 있습니다.
1697번을 예시로 들자면,
Max = 10 ** 5
visitedCnt = [0]*(Max+1)배열을 선언할 때, 적당한 크기로 배열의 사이즈를 할당합니다.
for i in pos:
if 0 <= i <= Max and not visitedCnt[i]:
visitedCnt[i] = visitedCnt[idx] + 1
queue.append([i,visitedCnt[i]])두번째로는 들어갈 수 있는 값들의 범위를 지정하여 무한 루프를 방지해주고, 해당 값을 처리한 적이 있는지 확인하여 중복된 데이터가 처리되지 않도록 하였습니다.
위, 두가지 방법을 통해 메모리 초과를 해결 할 수 있었습니다.
2. 재귀 등으로 인한 너무 많은 함수 호출로 인한 메모리 초과의 경우에는 다음과 같습니다.
첫번째로는 재귀가 너무 많은 횟수가 반복되지 않도록 적절한 조건 설정 해주어 메모리 초과가 발생하지 않도록 하는 방법이 있고,
두번째로는 재귀함수를 반복문으로 푸는 것입니다.
재귀함수를 통해 호출된 함수는 메모리 영역의 스택에 저장되는데, 동일한 함수여도 호출 될 때마다 스택영역에 계속해서 메모리가 할당되게 됩니다. 너무 많은 함수가 호출이 된다면 스택 영역의 메모리를 초과하게 되는 '스택 오버플로우'가 발생합니다.
즉, 핵심은 스택 영역의 메모리를 초과하지 않게 사용하는 것이죠.
첫번째 방법은 스택 영역을 활용하되 사용하는 메모리 영역을 초과하지 않게 하는 방법이고, 두번째 방법은 아예 스택 영역을 사용하지 않는 방법입니다.
메모리 초과라는 문제에 대해 조금이나마 도움이 되었으면 좋겠습니다.
읽어주셔서 감사합니다.