[c언어] 수열의 부분 합(Prefix Sum) 구하기 - 어떤 방법이 더 빠르고 정확할까
수열의 부분합 구하기! 중고등학교 수학시간에 많이 했던 일이죠. 어떤 수열 X가 a, b, c, d ... 와 같은 식으로 있다면 부분합(Prefix Sum, 혹은 Scan) S는 다음과 같이 계산됩니다.S1: a S2: a + b S3: a + b + c S4: a + b + c + d수학시간에서는 이 부분합 수열의 일반항을 구하는 일을 주로 했지만, 컴퓨터 과학에서는 이 수열의 각 항을 빠르고 효율적으로 (또 정확히) 계산하는 방법에 대해 논하게 됩니다. 이 부분합을 구해서 어디에 쓰나 싶지만, 의외로 여러 분야에서 널리 쓰이고 있습니다. 대표적인 사례로 누적분포(cumulative distribution)을 구하는 작업이 있겠습니다. 이는 특정 임의 분포에서 표본을 추출하는데 자주 사용됩니다. 예를..
프로그래밍/테크닉
2020. 7. 12. 19:01
