bbayu   2년 전

예전에 문제를 풀다가 depth가 2만정도 이상가니 스택오버플로우가 발생하는걸 알았습니다.

지금 이 문제에서도 n이 10만이므로 dfs를 돌리면 10만까지 파고들 수 있기 때문에 스텍오버플로우가 발생할 것 같아서

문제를 읽었을때 dfs로 하면 안되겠다 라는 생각을 하였습니다.

그런데 답을 보니 dfs로 구현을 하는것이고요.. 음? 재귀를 구현할떄 depth를 어느정도의 기준을 두고 생각해야할까요????

cubelover_dev   2년 전

스택 메모리 제한은 문제에 주어진 메모리 제한과 동일합니다. 메모리 제한을 초과하지 않는 범위 내에서는 재귀를 몇 번이고 들어가도 됩니다.

다만 예외적으로, 파이썬과 같은 언어에서는 내부적으로 재귀 횟수에 제한이 있습니다. 이런 경우 제한을 풀 수 있는 방법을 사용하거나, 다른 언어를 사용해야 합니다.

bbayu   2년 전

재귀를 구현함으로써 스택메모리량을 추정할 수 있는 방법이 있을까요???

재귀가 메소드이다보니 어느정도로 스택메모리가 쌓이는지 감을 잘 못잡겠습니다.

bbayu   2년 전

그리고 문제에 주어지는 메모리 제한은 힙, 정적메모리를 다 합친 용량 아닌가요?

cubelover_dev   2년 전

네 메모리 제한은 스택, 힙, 정적 메모리를 모두 합친 것의 제한입니다. 스택 메모리에 따로 제한이 있지는 않다는 얘기였습니다.

재귀를 한 번 들어갈 때 레지스터의 값과 return address을 스택에 푸시하니 사용하는 변수의 개수에 따라 스택에 어느 정도 쌓이는지를 유추할 수 있기는 한데, 컴파일러가 최적화를 어떻게 하느냐에 따라서 사용하는 레지스터의 개수가 달라지기 때문에 정확한 예측은 어렵습니다. 

djm03178   2년 전

보아하니 자바를 주로 사용하시는 것 같은데, 자바도 자체적인 제한이 기본적으로 있는 것으로 알고 있습니다.

bbayu   2년 전

cubelover_dev

네 감사드립니다. 정확한 예측은 어려우니.. 꾸준한 연습밖에 답이 없어보이네요. 


djm03178  

제 자바를 자주 사용하고 있습니다. 자체적인 제한이 있는지 한번 알아보겠습니다.

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