[sw정글 1주차] 짜릿짜릿한 N-Queen, 재귀마스터가 되다

🚀SW정글 1.5주차

N-queen을 비롯한 기타 난이도-중 문제를 모조리 뿌셔버렸다. N-queen을 답안지를 보지 않고 재귀함수로 구현을 할 때에는 정말 짜릿한 쾌감이 들었다. 나보다 훨씬 빠르고 정확히 문제를 풀어낸 사람이 넘쳐난다는 사실을 잘 알고있지만, 들썩이는 어깨를 주체할 수 없었다. 무슨말을 하든 잘 받아주는 옆자리의 JH를 붙잡고 자랑이라도 하고싶었다. 모래성과 같은 확신에 찬 기분을 잠시 내려두고 다시 마지막 문제를 향해 나갔다.

근 몇일을 돌아보면 정렬과, 재귀를 파고들었던 것 같다. 라고 말했습니다. 라고 말했습니다. 라고 말했습니다. 라고 말했습니다. 와 같이 옆자리의 GY를 미치게 하는, 재귀트라우마 유발 문제도 있었으며, 이들을 돌파하며 알게 된 지식들을 공유하고자 한다.

스택

📚스택

옆자리의 JH가 DFS를 스택으로 만들기 위해 열심히 stack클래스를 작성하였으나… 파이썬의 list는 stack 자료구조이다. 세상에서 가장 편리한 stack이다. ‘그걸 누가몰라?’ 라고 하겠지만, 모두가 잊고 있었다. 바꿔말하면 list는 스택이므로

’’’ 96 -> [97,98,99] <- 100 ‘’’

96을 왼쪽으로 삽입하려면, 100을 삽입할 때 보다 훨씬 높은 시간복잡도를 가지게 된다. 그래서 아래처럼 deque로 넣어주어야 한다.

#import
from collections import deque
list => deque
appendleft(96)

아래는 deque로 넣었을 때의 시간복잡도 이다.
| Deque | List | | ———- | ——– | | appendleft | 그냥삽입 | | O(1) | O(n) |

그렇다. 길이가 있는 리스트에 왼쪽에 자주 삽입할 때, 그냥삽입하면 바보다!! 그래도 꽤 번거롭기 때문에 더 좋은 방법이 있을 것 같기도 하다.

이러한 스택 구조 특성 때문에, 재귀함수를 구현할 때 스택으로 구현하기도 한다.

재귀함수

🤖재귀함수

공포의 재귀함수이다. 책으로 한번 슥~ 흝고 가니까 재귀함수 문제들을 비교적 손쉽게 풀고 넘어갈 수 있었다. (시간을 조금 많이 들여서)재귀 과정을 손으로 하나하나 그려보고 나니 아래와 같은 문제는 허허~ 하면서 슥슥 풀 수 있었다.

백준 17478 문제

결국 재귀를 손코딩으로 해결할 수 있으면, 재귀를 stack으로 표현할 수 있으면 이를 완벽하게 이해했다고 생각했으며 후에 공부할 탐색 문제들에 대해서도 지식습득을 쉽게 할 수 있을 것 같았다.

일단 permutation으로 슥 풀어보고 싶은 욕구가 들끓었지만 잠시 참아내고 한땀한땀 재귀를 호출하였다. 를 호출하였다. 를 호출하였다. 를 호출하였다.

permutation과 일반 recursive function을 실험해 보았다. 10!의 결과를 뽑아보았는데 다음과 같았다.

재귀	permutation
2.4362480초	0.00001520초

10!의 양을 계산하는데, 엄청난 차이가 났다. 약 16만배 차이가 났다. 그렇다면 굳이 프로그래밍에 해당 재귀를 넣는 경우는 너무 과하게 숫자가 커지는 경우에 조건으로 넣어줄 수 있지 않을까 싶다. 학부 4학년 때, Optimization수업에서 knapsack problem과 Traveling sales man problemdm을 해결할 때가 기억났다. n이 조금만 커져도 경우의 수가 폭발적으로 늘어났는데, 이를 조금 덜어줄 수 있는 방법 중 하나가 되지 않을까 싶다.

재귀함수를 호출할 때, 중복에 대한 체크를 하기 위해 데이터를 수정하는 과정에서 16만배라는 차이가 생기지 않았나 추측했으며, 그럼에도 불구하고 재귀함수로 호출 중 특정 조건을 줌으로써 문제를 풀어야 하는 경우가 있지 않을까라고 추측한다. 손코딩과, 알고리즘 문제들을 풀며 느낀 재귀함수를 단 한문장으로 정리해보자면, 결국 재귀함수는… “어떤 문제를 동일한 종류의 더 작은 문제로 나누고 그 작은 문제를 해결하는 것” 이다.

🐍재귀함수와 순열조합

다음은 나의 알고리즘 문제코드와 그 실행시간이다.

백준10971번	재귀	permutation
메모리	600 MB	100 MB
실행속도	1000ms	2000ms
나의 코드	재귀 정답코드	순열 정답코드

위에서 permutation 함수가 훨~씬 빠르게 경우의 수를 연산함을 보았다. 하지만 위의 표를 보면 이야기가 달라진다. permutation 함수를 사용한 경우가 메모리도 더 많이 차지하고, 시간도 더 많이 걸렸다 왜 그럴까?

💽메모리

일단 메모리를 더 많이 사용하는건 당연하지 않을까라는 생각이다. 수많은 조합을 직접 계산하고 이를 메모리의 한 구석에 들고있으니 말이다.

⏰시간

시간은 왜 더 많이 사용할까? 심지어 permutation 함수가 경우의 수를 계산하는데 16만배 더 빠름에도 불구하고 말이다. 의심할 수 있는곳은 단 한군데다. 바로 메모리에 접근하는데 걸린 시간이다. 엄청나게 긴 list가 있고, 각각의 list요소에 접근하는데는 O(n)의 코스트가 든다. 비록 해당하는 조합은 빠르게 만들었지만, 개별 요소에 접근해서 연산을 하려고 할 때 시간이 걸리기 때문에, 결과적으로 재귀함수를 이용한 풀이가 두배 더 빠른 결과값을 낸게 아닐까 싶다.

🐍재귀함수와 꼬리재귀

재귀함수는 여러가지 방법으로 표현될 수 있다. 재귀함수는, 우리가 익히아는 함수속에서 함수를 호출하는 방법이 있을 수 있고, stack으로 구현할 수도 있으며, while과 for문과 같은 반복문으로도 호출할 수 있다.

결론부터 말하자면 for문으로 호출하는게 가장 좋다

다음은 재귀함수에 대해 (파이썬의 창시자인)귀도반로섬이 말한 내용(링크) 이다.

요컨데 반복되는 함수 호출 속에서, tail elimination이 일어날 수 있다는 것이다. 코딩공부 동기 겸 죽음의 룸메이트인 chobae와 함께 CS에 관해 열띤 토론을 주고받은 결과, 꼬리재귀를 최적화 시켜주는 방법이 있다는 것을 알게 되다. 꼬리재귀란

재귀함수가 재귀함수를 부르고… 재귀함수가 재귀함수를 부르고… 부르고… 부르고…. 부…..ㄹ….

위와같이 길~게 꼬리가 형성되는데, 이를 최적화 해줄 수 있다는 것이다.

위의 그림은 꼬리재귀 최적화를 쉽게 이해할 수 있는 그림이다. 무한에 가까운 그 꼬리를, 컴퓨터에게 단순 “재귀” 두글자로 알려줄 수 있는 것이다.

def fact1(n):
if n == 1:
return 1
return n \* fact1(n-1)

def fact2(n, res):
if n == 1:
return res
return fact2(n-1, res\*n)

fact1(500)
fact2(500,1)

위처럼 재귀함수를 계산할 때 함수의 인자로 넣어주게 된다면, 함수가 또 하나의 함수를 부르고, 또 부르는게 아니라 하나의 for문처럼 인식을 한다는 것이다. C언어에서 위처럼 최적화를 했다는 사람도 있었지만, 결과적으로 파이썬에서는 작동하지 않았다. 위의 두 함수를 실행시켜본 결과속도에서 차이가 나지 않았다

그렇다. 파이썬에서는 꼬리재귀 최적화를 해주지 않는 것이다.

(로컬 파이썬 3.10 및 구글colab환경에서 테스트)함

그럼에도 의심을 떨치기 힘들어 검색하던 와중, 람다함수를 통해 파이썬 꼬리재귀 최적화 처럼 사용할 수 있는 방법을 알아낸 사람(링크)을 찾을 수 있었다. 글을 읽어보면 알겠지만 상당히 복잡해진다.

하지만 우리가 알아야 될 사실이 있다. 애초에 for문으로 재귀함수를 작성하면 된다.

또한 어렵사리, 꼬리재귀가 최적화 된 재귀함수처럼 만들어서 쓴다고 한들 이점이 별로 없다. 일단 Time-complexity는 동일하다. 그리고 Space-complexity도 동일하다. 약간의 space를 더 줄일 수 있다고 주장하는 사람들도 있지만, 검색결과 명확한 근거와 해답이 없는 부분인 것 같다.

그렇다. 파이썬에서 어렵사리 구현한 꼬리재귀 최적화는 이점이 불분명하고, 애초에 for문을 통한 재귀함수를 구현하면, 스택이 쌓임으로써 발생하는 문제들(귀도반 로썸이 설명한 tail elimination)을 예방할 수 있다.

파이썬과 pypy

🤔파이썬과 pypy

백준 10989번 문제를 푸는 와중, pypy에서는 안풀리고 python에서는 풀리는 경험을 했다. 통상적으로 시간초과가 나올 때, python3에서 pypy3로 실행 코드를 옮기면 문제가 풀렸던 경험들을 했다.

그렇다면 왜 파이썬으로 풀릴 때도 있고, pypy로 풀릴 때도 있을까? 결론부터 말하자면 파이썬은 적은 메모리와 느린 실행속도, pypy는 많은 메모리와 빠른 실행속도를 보여준다. 메모리초과가 뜨면, python3로 문제풀이를, 시간초과가 뜬다면 pypy3의 사용을 고려 해 볼 수 있는 것이다.

그렇다면 왜 pypy3는 빠르면서, 한편으로는 메모리를 많이 차지하는 것일까? 문법도 똑같은데 말이다.

답은 언어 구조가 다르기 때문이다. 간편하지만 실행시간이 오래걸리는 파이썬의 단점을 보안하기 위해 만들어 진 것이 pypy이며, 이는 JIT컴파일 방식을 사용한다. JIT(Just In Time)은 말 그대로, 실행하는 순간!! 즉석으로 컴파일을 하는 방식이다. 그리고 자주쓰이는 코드를 미리 캐싱해 두기 때문에, (인터프리터 방식을 쓰는)파이썬3 보다 훨씬 빠른 시간을 보여주는 것이다.

그렇다면 아주아주 간단한 코드라면 자주쓰이는 코드를 캐싱이건 뭐건 사용하지 않으므로 메모리 측면에서 훨씬 우세하다. 또한 컴파일언어로써의 장점을 가져갈 수도 없으니, 메모리와 속도측면 모두 파이썬이 빠를 ‘수’도 있는 것이다. 하지만 일반적인 경우, 일정 line 이상의 코드들을 실행하면 (메모리는 항상 pypy가 많이 잡아먹고)pypy3가 무조건 더 빠르다.

더 깊숙히 pypy공식 웹 사이트(링크)에서는 pypy는 python과 highly compatible하다고 한다. 그렇다면 perfectly complatible하지는 않다고 생각할 수 있을 것 같다. 리눅스에서는 프로세스가 어떻게 매핑을 할것인지에 대해 madvise()를 콜함으로써 커널에 알려준다. 이러한 콜을 통하여 시스템의 동작 방식을 최적화 시킨다.(리눅스, OSX, BSD는 이러한 방식으로 call이 이루어 진다.) MADV_DONTNEED와 MAV_FREE가 어찌저찌 동작을 하는데… 결국 간단히 말을 줄여보자면, 동작하다가 메모리가 모자라면 알아서 메모리 사용량을 줄여준다. (메모리가 부족하면 사용하지 않는 페이지를 MAV_DONTNEED에 추가함으로써 RES를 강제로 줄여줌)

우연히 알게 된 꿀팁

✚추가사항

오버플로우를 방지하기 위해서

int m = (a+b)/2

위와 같은 평균을 구하는 코드를,

int m = a + (a-b)/2

이렇게 사용하는 방법을 고려 할 수도 있다고 한다

---

😵배우면서 깨달은 내용을 정리해 보았습니다. 오개념을 아래 댓글에 달아주시면 감사하겠습니다😵

🌜 Thank you for reading it. Please leave your comments below😄

맨 위로 이동하기

swjungle survive 카테고리 내 다른 글 보러가기