13개의 댓글이 있습니다.
-
-
freedomJ -
더불어서...
int** dp;
dp = new int*[change+1];
for(i=1 부터 change+1까지 i++) dp[i]= new int[numOfCoin+1];2차원 배열 동적할당 아래와 같이 하는 것 맞지 않나요?.. 동적할당하면 출력부(cout으로 dp를 출력하려고하면)에서 에러가 나네요..
힙이손상되었습니다. AOJproject.exe 어쩌고... 로드한 dll에 버그가 있을 수 있습니다...
대충 이런 에러메시지가 뜨는데요.. 음.. 구글링해보니 class파일에서 STL사용 잘못 했다는 내용도 있고.. 하는데, 저는 class 작성도 안했고, STL도 안썻고;; 더군다나 기본으로 제공되는 dll 이외의 dll은 로드하지도 않았습니다.;;
그래서 그냥 하드코딩으로 배열 선언했는데요 음...;;ps.
COINS문제 조건이 동전의 종류가 1에서100사이, 잔돈은 1에서 5000사이 인데요,
테이블을 dp[100][5000]; 이렇게 하니 메모리 오버가 되서 제 컴퓨터에서도 Run이 안되더군요;;;
그래서 dp[50][5000]햇는데 AC 떳습니다. ㅎㅎ;; 제약조건 안지키긴 했는데 운이 좋은 case라고 해야할까요;
13년 전 link
-
-
-
hyunhwan -
AC를 받은 다른 소스코드들을 확인해 보았을 때에는 거스름돈이 0원일 경우에는 1을 반환하게 하는 코드들은 대부분 통과했습니다.
자세한 내용은 확인해하지 않았지만, 몇가지 올바르지 못한 구현이 보여서 몇자 적습니다.
- int dp[100][5000]; 이라고 main() 내에 선언을 하게 되면, 일반적으로 stack 영역에 memory가 할당되게 됩니다. 그런데 일반적으로 할당 되어 있는 stack 영역의 capacity는 작기 때문에, 저렇게 선언할 경우 stack 영역의 capacity를 초과하게 되어 RTE가 발생하게 됩니다. 따라서 이 경우는 앞에 static keyword 를 붙이거나, 전역 변수를 사용하여 선언한 배열이 heap 영역(일반적으로 stack 영역보다 큰 capacity가 할당되어 있습니다)에 위치하도록 선언해 주는 것이 좋습니다. 일반적으로 stack에는 int 배열은 크기 10,000!~100,000 정도가 잡힐 것이고, heap에는 보통 크기 100,000,000 가량의 int 배열이 잡힐 것입니다. 자세한 것은 직접 실험을 해보시는 게 좋을 것 같네요.
또한 dp배열의 경우 동전에 대해서 0원~5,000원을 거슬러주는 경우에 대한 경우의 수를 저장하는 역할을 하게 되는데, 배열이 [5000] 과 같이 잡혀 있으면, 0이상 4,999에서는 올바르게 동작할 것이지만, 5,000에 대해서는 할당된 범위를 벗어나기 때문에 올바르게 동작하지 않을 것입니다. 따라서 int dp[100][5001]이 아마 freedomJ 님이 원하시는 선언일 것 같습니다. 제 추측으로는 위의 0원에 대한 경우를 0으로 하는 것 땜에 올바른 답이 나오질 않는 것이 아닌, 배열의 잘못된 참조로 인해서 답이 제대로 저장이 안되었지만 0으로 처리함으로 인해서 '운좋게' 답이 나온 것은 아닌가 하는 생각이 듭니다. 정확한건 시간 날 때 확인을 해봐야 할 것 같습니다 :)
13년 전 link
-
-
-
hyunhwan -
RTE에 대해서는 JongMan님께서 직접 답변을 달아주시길 기대합니다.
하나 이야기를 더 해보자면, AOJ와 같은 종류의 문제를 풀 때 일일이 배열 크기에 대해서 동적으로 메모리를 잡는 것은 보통 지양을 하는 것이 좋고, 입력의 최대 size에 대해 필요한 만큼 배열을 잡아서 사용하는 것을 권장합니다. 특히 C/C++ 같은 언어에서는 할당/해제 시에 자잘한 실수를 하기 쉽기 때문에 많은 주의를 요하기도 하고, 그 외에 여러가지 이유가 있긴 합니다만, 이에 대해서는 따로 기회가 되면 설명을 하도록 하겠습니다.
마지막으로 정 동적 배열을 쓰려고 하실 경우에는 new로 선언을 하지 마시고 STL vector를 사용하시는 것을 권합니다,
13년 전 link
-
-
-
freedomJ -
리베님// stack과 heap에 그런 Memory Capacity차이가 있었군요!! 전혀 몰랐던 사실이고... stack 소화량이 작았다는것도 몰랐습니다 ;; (초기화 타이밍때문에 실수가 잦아서 전역변수를 거의 사용하지 않아 그럽니다. ;)
컴퓨터와 컴파일러마다 조금씩 차이가 있겠지만, 제 컴퓨터 비스2008 기준으로 main안에서 int[5000][60]정도하면 메모리할당을 못주고, static을 붙임으로써 heap공간에 선언하게되면 int[10000][10000]도 선언이 됩니다. 10000*10만 선언하려고 하니까 "배열의 전체 크기는 0x7fffffff바이트를 초과할 수 없습니다." 라고 뜨네요 :) ... 리베님 이런 지식 알게해주셔서 감사합니다. 0x7fffffff바이트 = 2,147,483,647bytes = 2의 32제곱bytes = 2의 22제곱 Kbytes = 2의 12제곱Mbytes = 4Gbytes( heap 정말 대단하군요 -_-)리베님 말씀대로 하드코딩 5001로 할당해야하는데 잘못했군요; 동적할당할때는 change+1로 할당했는데..; 하드코딩할때는 습관적으로 저렇게 잘못코딩했네요.;
나중에 알게된 사실이지만...; 0원일경우는 문제에서 Constraint로 고려하지 않았더군요;;
동적배열 -> 하드코딩 , 0원으로 초기화 2가지를 동시에 수정하고 제출해서 AC받고서는 후자가 잘못된것으로 착각했나 봅니다..두번째 글에 리베님 충고사항 감사합니다. 저는 MaxSize로 정적으로 선언해버리면 (해당 Test Case에 대해서) 메모리낭비라 생각하여 동적 할당을 하려 했는데 정확히 알지 못하고 한것이 독이 되어버렸군요..; 메모리 할당/해제 하는데 Time도 걸릴테니...
13년 전 link
-
-
-
Taeyoon_Lee -
좀 논점을 벗어나긴 하지만.. 요즘같은 세상에 동적 배열을 쓸 일이 있는 지 모르겠네요..'ㅅ'? 저는 대회용 코드(?)에나 업무용 코드에나 항상 STL vector를 쓰는데.. 업무용 코드에도 동적 배열은 본 기억이 안 나구요.. 혹시 어떤 경우에 쓸 일이 있는지 아시는 분 답변 좀...
13년 전 link
-
-
-
Taeyoon_Lee -
helloneo // 그렇군요.. 하긴 STL을 쓸 수 없는 환경도 있겠군요.
13년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
freedomJ
DP로 풀었는데요..
0원 일때 잔돈이 될 수 있는 가지 수는 1로 해야 table 채울때 계산이 옳게 되는데; ;
답은 WA를 뱉어내네요 ..;
혹시나 해서 table 채운 후에 0으로 바꿔 준후 submit 하니 AC떴습니다..
개념의 차이 이고 생각하기에 따라 조금씩 달라지는 개념인 것같은데요..
잔돈의 종류 2개(1원, 10원)이고, 0원일때 잔돈의 종류는 1가지로 해야하는가, 0가지로 해야하는가?
잔돈의 종류 0개이고, 0원일때 잔돈의 종류는 1가지로 해야하는가, 0가지로 해야하는가? (이건 0가지가 옳다고 생각합니다만? 여러분의견은 어떠신가요?)
조금 철학적인가요?... 음...; 어렵네요
13년 전