Algorithm repo 이용 제안 about algorithms HOT 3 CLOSED

가장 효율적이라고 말씀하시는 부분이 헷갈렸었는데 잘 정의해주셔서 감사합니다.
문제의 다양한 접근에 대한 토론이 건강하게 잘 이루어지면 좋을 것 같네요.
알겠습니다 :)

from algorithms.

좋은 제안 주셔서 감사합니다.
Runtime, Memory Usage에 대한 정보는 어떻게 공유하는 것이 좋을까요?

from algorithms.

Runtime 이나 memory usage 는 위의 접근방법 따라서 많이 달라지고
특히나 언어에 따라서 천차만별입니다.

제가 가장 빠른 시간이나 메모리 사용량을 보았던 것은
같은 언어 내에서 얼마나 효율적으로 작성 했는지 보려했다기 보다는
저와 다른 방법을 갖고 있을 가능성이 있어서 보았던 것 입니다.

결론적으로 언어가 다르다면 두가지 요소는 굳이 볼 필요가 없고
풀이 접근 방법을 비교하는 것이 좋습니다. (코드를 보면 대충 어떻게 풀려고 했는지 티가 납니다)

예를 들어볼까요?
가장 간단한 피보나치 수열을 보도록 하죠

// 재귀
def fibo(n):
    if n <= 0:
        return n
    return fibo(n-1) + fibo(n-2)

참고: 시간복잡도
참고: 시간복잡도 표현
참고: 피보나치 시간복잡도
참고: Memozation - 메모제이션

재귀 함수로 호출 할 경우 시간 복잡도를 계산한다면 $O(n^2)$의 시간복잡도를 갖습니다.
이 재귀함수 호출을 메모제이션(Memozation)을 통해서 알고리즘의 효율을 개선 한다면 아래와 같은 코드를 얻을 수 있습니다.

// memozation
dic = { 0:0, 1:1 }
def fibo(n):
    if n in dic:
        return dic[n]
    dic[n] = fibo(n - 1) + fibo(n - 2)
    return dic[n]

이렇게 메모제이션을 통해서 개선된 알고리즘은 시간복잡도 $O(n)$의 상수 시간복잡도를 갖습니다.
하지만 메모리 사용량은 당연히 증가하고 실행시간은 비슷하게 떨어질 것 입니다.
(실행시간이 알고리즘의 time complexity를 보장하지 않습니다. 하지만 프로그램의 runtime timeout의 척도는 될 수 있습니다. 이는 채점프로그램 또는 컴파일러 마다 달라질 수 있는 문제입니다.)

결론적으로 공유해야 하는 가장 중요한 것은 문제의 접근 방법입니다.
위의 예시에 따라서 문제를 재귀로 구현할지, 메모제이션으로 구현할지를 봐야하는 것이죠.
또 메모제이션을 구현하더라도 사람마다 다르게 구현이 됩니다.

이는 토론의 영역이며 효율성을 개선할 수 있는 중요한 논쟁이 됩니다.
물론 접근방법이 같다면 드라마틱한 효과를 보기는 힘들 것입니다.

말투가 굉장히 이론적? 논문쓰는듯한 말투인데 글적다보면 습관적으로 이렇게 적네요 ㅋㅋ
어쨋든 다시말해서 2번 풀이 접근 방법이 가장 중요합니다. 3번은 코드공유가 아니라 접근 방법에 대한 것도 같이 공유를 해야 겠네요.

기교는 TDD와 Pair programming을 통해서 익히고 펀더멘탈은 알고리즘을 같이 공부한다면 비약적인 실력상승을 이루어 낼 수 있을것 같습니다.

from algorithms.