[💬] 코드몽키 벗어나기 - 10

[차별없는차단(pnacrd8pn5la)]

코드몽키를 벗어나기 위해 첫번째 책으로 SICP를 정독중. 

여태까지 요약 하면, 

프로그래밍 언어를 이해해가 위해서는 

그 프로그래밍 언어가 어떻게 프로시저와 데이터를 표현하는지를 이해해야 한다. 

그러기 위해 가장 기본적인 단위와 기본적인 프로시져를 배웠고, 

그것들을 활용해서 조금 더 복잡한 표현을 어떻게 하는가를 배웠고, 

그 복잡한 표현이 얼마나 효율적인지 평가하는 방법을 배웠다. 

오늘은 계속해서, 조금 더 복잡한 표현을 연습하는 챕터를 요약 정리한다. 

-----------------------------------------------------------

Exponentiation (제곱) 에 대해서. 

제곱을 계산하기 위해서는 가장 직관적인 방법은 recursive 한 방법이다. 

 

이것을 Lisp로 나타내면 아래와 같다. 

보면 알다시피, 이것은 Linear recursive 이므로, n이 커지면 계산수도 그거에 비례해서 늘어나고, 

재귀 함수도 그만큼 불러야 하므로 저장공간도 n 만큼 필요하게 된다. 

그러니까 이거의 계산 스텝은 O(n), 계산 공간도 O(n) 이라고 할 수 있다. 

이것을 리니어 이터레이션으로 바꾸면 아래와 같이 바꿀수 있다. 

보면 알다시피 중간계산을 저장하지 않으므로 계산 스텝은 똑같이 O(n)이나 저장공간은 O(1) 인것을 알 수 있다. 

리커젼과 이터레이션의 그림 설명은 여기를 참조. 

https://gall.dcinside.com/mgallery/board/view?id=game_dev&no=108191

이러한 계산들을 더욱더 효율적으로 하기 위해 여러가지 꼼수가 존재한다. 

예를 들어서 가장 비효율적인게 이거라면 

그걸 약간 더 효율적이게 한다면 이런걸 생각해 볼 수 있겠고 

이걸 일반화 하면 아래와 같이 된다. 

코드로 표현하면 아래와 같다 

오호... 이게 이런식으로 표현이 되는구나... 

예를 들어서 2^8을 계산한다고 하면 

(exp 2 8)

-> (square (exp 2 4))

-> (square (square (exp 2 2)))

-> (square (square (square (exp 2 1))))

-> (square (square (square (* 2 exp(2 0)))))

-> (square (square (square (* 2 1))))

-> (square (square (square (2))))

-> (square (square (4))))

-> (square (16))

-> 256

이리 된다는 거시구만.

이것은 공간도 계산 스텝도 O(log n) 인 모양. 

이 재귀함수를 iterative 로 바꾸는 방법은 연습문제로 있는데 패스. 

여튼 오늘도 매우 기본적인 내용이었구요. 

아직도 몸이 다 낫질 않았으므로 오늘은 여기까지 

[노인급피지컬(2kya47bhpeeg)]

5짤 같은건 분할 정복?에서 아이디어를 가져온 건가요? 유용하네요. 결국 재귀는 호출을 여러번 해야되니까 그만큼 잡아먹는 메모리가 크고 그걸 그나마 메모리라도 덜 잡아먹게 하기 위해서 반복문으로 가고 반복문에서 계산 단계/메모리를 더 줄이기 위해서 분할 정복을 도입해내는 건가요? 제가 이해한 게 맞는지 잘 모르겠어요 ㅋㅋ;