오랜만에 알고리즘 공부를 해보자
아주 간단한 알고리즘이다 1부터 100까지 혹은 n부터 m까지의 더하는 알고리즘이다.
솔직히 아주 간단하다. 하지만 여러 방법으로 접근해보자
그게 목적이다 ㅎㅎㅎ
일단 우리가 흔히 쓰는 1부터 100까지의 합이다 소스를 보자
int sum = 0;
for (int i = 1; i <= 100; i++) {
sum += i;
}
System.out.println(sum);
흔히 쓰는 방법이라 따로 설명은 생략하겠다.
참고로 자바8에선 더 간단해졌다.
System.out.println(IntStream.rangeClosed(1, 99).sum());
위와 같이 하면 된다.
하지만 여기서는 알고리즘 자체를 생각해보는 시간이기에 생략하겠다.
이번엔 천재수학자 가우스가 발견한 덧셈이다.
누구나 들으면 아하 이러겠지만 어렸을때 이방법을 생각해낸 자체가 정말 천재인듯 싶다.
예를 들어 1부터 10까지의 합을 구하고 싶다고 가정하자.
그러면 이런방식으로 할 수 있겠다.
1,2,3,4,5,6,7,8,9,10
1과 10을 더하면 11
2와 9를 더하면 11
3과 8을 더하면 11
4와 7을 더하면 11
5와 6을 더하면 11
그럼 11을 5번 더하면 그게 1부터 10까지의 합이다.
공식으로 보자면
(n + 1) * (n / 2)
위와 같은 공식이 성립할 것이다.
코드로 보자면 아래와 같다
int n = 10;
System.out.println((n + 1) * (n / 2));
근데 여기에선 문제점이 있다. 만약 n이 짝수 일 경우에는 상관없지만 홀수인 경우에는 알고리즘이 성립하지 않는다.
int n = 9;
System.out.println((n + 1) * (n / 2));
실제 1부터 9까지의 합은 45이나 위와 같은 코드를 실행 하였을 경우에는 40이 나온다.
그러면 짝수일 경우에는 위와 같이 하면 되고 홀수 인 경우에는 어떻게 해야 될까
만약 1부터 9까지를 예를 들어보자
1,2,3,4,5,6,7,8,9
그럼 일단 마지막 숫자인 9를 잠시 잊고 있자
1부터 8까지 짝수 알고리즘을 실행하고 나머지 9를 더하면 1부터 9까지 합이 될 것이다.
static int sum(int n){
if(n % 2 == 0){
return (n + 1) * (n / 2);
}else{
return n * ((n - 1) / 2) + n;
}
}
위와 같이 n에 1을 빼서 계산하면 된다. ((n + 1) - 1) 은 n이 된다.
좀더 고민을 해보자.
홀수나 짝수나 공식을 똑같다. n에다 1을 빼주고 마지막만 n을 더해주면 되는 것이다.
static int sum(int n){
if(n % 2 == 0){
return (n + 1) * (n / 2);
}else{
return sum(n - 1) + n;
}
}
재귀를 이용해서 구했다. 홀수일 경우에는 sum에다 1을 빼주고 n만 더해주면된다.
1부터 n까지의 합이 이렇게 많은 알고리즘이 있다.
마지막으로 우리가 고등학교?때 배운 수열이다.
맞나 고등학교때 배운게... 중고등학교때 수학 공부를 많이 했어야 되는데..
아무튼 수열의합을 이용해서 구해보자
인터넷에 쳐보면 등차수열의합이 자세히 설명 되어있다.
a를 첫째항 d를 공차라 하자. 공차란 두수의 차를 말한다.
공식의 증명은 인터넷으로...
n * {2a + (n - 1) * d} / 2
등차수열의합은 위와 같은 공식을 성립한다.
만약 10까지 합을 구한다하면
10 * {2 + (10 - 1) * 1} / 2
계산을 해보면 10 * 11 / 2 따라서 55가 나온다.
홀수인 1부터 9까지를 해보자
= 9 * {2 + (9 - 1) * 1} / 2
= 9 * 10 / 2
= 45
아주 잘 된다.
소스를 보자
int a = 1;
int n = 10;
System.out.println(n * (2 * a + (n - 1) * 1) / 2);
등차수열의합으로 100부터 200까지의 2배수의합 등 여러가지를 구할 수 있다.
수학은 참 아름답단말야..ㅋㅋㅋㅋ
이렇게 간단하게 1부터 n 혹은 n부터 m까지의 합을 알아봤다.
수학 기호를 어떻게 쓰지...흠