algospot   10달 전

일단 소스 accept은 받았는데, 껄끄러운 점이 있어서 질문드립니다.

문제에서 나오는 상태공간은 총 9!=362880개 입니다. 즉, 큐에 들어갈수있는 갯수는 362880개라고 감안(최소이므로 재방문 방지)하도록 하죠.

그래서 아래 코드와 같이 큐의 크기를 362880개라고 잡으면, 메모리 초과가 걸립니다. 

질문1) 메모리 계산법, ex)a[10만]-> 몇 MB? 이런식

질문2) 큐의 크기를 300000개로 바꾸니 accept 되었는데, 이건 솔직히 최악의 큐에 꽉차는 경우가 없어서 망정이지 뽀록?이라고 생각합니다.

            즉, 문제가 발생하는 것은 struct 안에 [3][3]의 크기 9가 있어서 362880*9만큼의 메모리 소요가 발생하니깐, struct안을 정적배열 말고

            동적배열을 쓰는 식으로 해야할 것 같은데, void* 식으로 주소값만 받으니 '식은 수정할 수 있는 lvalue' 이런 오류가 뜨는 등등 좀 난잡해             집니다.

            accept 하신 또다른분들의 메모리 관리법을 질문드립니다.


yukariko   10달 전

g[3][3]을 int형 변수 1개로 압축할 수 있습니다.

algospot   10달 전

int x=g*[3][3] 로 표현할수있는

서로 다른 x가 9!개 있다고 쳐도, 그걸 다시 a[3][3]에 담을려면 번역과정이 있어야하는데,

압축된 x를 a[3][3]에 번역하는 과정은 어떻게 해결할수있나요?

namnamseo   10달 전

9진수로 생각할 수 있을 것 같습니다.9^9 = 387420489은 int에 들어가거든요.

메모리 계산법은, char이 1 byte, int가 4 bytes 인 걸 생각하시면 됩니다.
전 백만 개 단위를 생각해요.
int 백만 개 ≒ 4 MB
char 백만 개 ≒ 1 MB
백만(10^6)이 mega-이기 때문에 가능합니다.
말씀하신 362880의 경우 int로 잡으면 백만보다 작거나 같기 때문에 4MB 이하의 메모리를 먹고, 결국 해결할 수 있죠.

yukariko   10달 전

일단 변수하나를 배열로 교환해서 쓴다고 해도 시간은 더 걸릴지라도 메모리는 9배 줄어들것입니다.

그러나 배열로 교환해야할 필요는 없습니다. 

퍼즐을 움직이는 것은 0뿐이니

0의 위치와 그 위치에 따른 이동 방향만 정해진다면 3×3의 2차원으로 생각하지 않고 1차원으로 생각할 수 있죠.

algospot   10달 전

아 그런데, 9^9-1크기의 메모리를 check배열을 만들면 메모리 엄청 소모 되지 않나요?

yukariko   10달 전

https://www.acmicpc.net/source/829254

제 코드의 direction배열이

현재 0의 위치에서 이동가능한 위치정보를 담고있습니다.

이동은 정수하나와 decimal배열을 통해 상수시간에 처리할 수 있습니다.

algospot   10달 전

수학적으로 생각지 못한 접근이네요

감사합니다 배웠습니다~

댓글을 작성하려면 로그인해야 합니다.