빠른 합(분할 정복 합) - 구름LEVEL
빠른 합(분할 정복 합)
Quiz Info
Quiz Info
빠른 합(분할 정복 합)
100points
Participant
61
Solved Rate
90.1%
0
1

이번 문제를 통해 분할 정복의 기본에 대해 배우고 실습해보도록 하겠습니다.

부분 문제의 답을 재귀 호출로 구하고 각 부분 문제의 답을 통해 전체 문제의 답을 구하는 분할 정복 알고리즘은 대게 3가지 구성 요소를 가지고 있습니다.

1. 문제를 더 작은 문제로 분할( Devide )

2. 각 문제의 답을 원래 문제에 대한 답으로 병합( Merge )

3. 더 이상의 분할이 필요하지 않은 작은 문제( Base case )

1 부터 n 까지의 합을 구하는 문제를 분할 정복 알고리즘으로 해결하는 프로그램을 작성하십시오.

* Sum(n)을 잘라 2개의 부분 문제인 Sum(n/2)로 만들고 이를 처리하는 형태로 문제를 해결할 것을 권장합니다.


이 방법으로 문제를 해결한다면 재귀 방법에 비해 호출 회수가 훨씬 적다는 장점이 있습니다. ( O(log n)만큼 소요 )


입력

양의 정수

출력

1부터 입력값까지 모든 정수의 합


Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
10
Output
55
Example 2
Input
100
Output
5050
⋇ Please keep the input and output formats carefully
Quiz Info
Q & A
Q&A forum that anyone can ask and answer.
Share your questions and answers with other students and grow together!

Registered Questions(0)