[생물정보학 알고리즘] 1 부터 n 까지 합 구하기 - 파이썬 알고리즘 공부, 자바 알고리즘 학습

 

안녕하세요 한주현 입니다.

오늘 부터 생물정보학 알고리즘에 대해서 포스팅 해보고자 합니다.

포스팅 계획은

간단한 알고리즘에서 부터 재귀, 탐색, 정렬, 그래프 그리고 생물정보학 알고리즘 까지 정리하는 것을 목표로 하고 있습니다.

목차 (계속하여 업데이트될 예정)

1. 1 부터 n 까지 합 구하기 - korbillgates.tistory.com/190

2. 배열에서 최대값, 최소값 찾기 - korbillgates.tistory.com/204

오늘 알아볼 알고리즘은 “1 부터 n 까지 합 구하기” 입니다.

알고리즘 생각

1 부터 n 까지의 합은 단순하게 생각하여 합을 모으는 변수를 두고

1, 2, 3, ..., n 을 더해 봅시다.

파이썬 스크립트

def oneToN(num):
    sum_val = 0
    for i in range(1, num+1, 1):
        sum_val += i
    return sum_val
 
print(oneToN(10))  ## 55

자바 코드

//OneToN_Sum.java
class OneToN_Sum {
    public static int calc(int num) {
        int sum_val = 0;
        for(int i=1 ; i<=num ; i++) {
            sum_val += i;
        }
        return sum_val;
    }
}
 
//OneToN_Sum_Tester.java
class OneToN_Sum_Tester {
    public static void main(String[] args) {
        System.out.println(OneToN_Sum.calc(10));  // 55
    }
}

알고리즘 평가

1 부터 n 까지 순차적으로 연산이 진행됩니다. 즉, 프로그램을 실행하게 되면 n회 만큼의 연산을 수행합니다.

Big O notation으로 보았을 때 O(n) 입니다.

알고리즘 개선

알고리즘 생각

1 부터 n 까지의 합을 S라고 하고 아래와 같이 순서를 앞 뒤로 하여 두 번을 쓴 다음에

S = 1, 2, 3, … , n

S = n, n-1, n-2, … , 1

-------------------------

두 줄을 합치면..

2S = (n+1) + (n+1) + (n+1) + … + (n+1)

2S = (n+1) * n

가 되어

S = ((n+1) * n) / 2

로 식이 나옵니다.

고등학교 수학 시간 때 배운기억이 납니다.. ㅎㅎ

파이썬 스크립트

def oneToN_rev(num):
    return ((num + 1) * num) / 2
 
print(oneToN_rev(10)) # 55.0

자바 코드

//OneToN_Sum_rev.java
class OneToN_Sum_rev {
    public static int calc(int num) {
        return ((num + 1) * num) / 2;
    }
}
 
//OneToN_Sum_rev_Tester.java
class OneToN_Sum_rev_Tester {
    public static void main(String[] args) {
        System.out.println(OneToN_Sum_rev.calc(10)); // 55
    }
}
 

알고리즘 평가

n이 늘어남과는 상관없이 단 한번의 연산이 진행됩니다.

Big O notation으로 보았을 때 O(1) 입니다.

오늘은 1 부터 n 까지 합 구하기 알고리즘에 대해서 알아보았습니다.

모든 소스 코드는 아래 github 페이지에서 만나실 수 있습니다. 

https://github.com/KennethJHan/Algorithm_Study/tree/master/OneToN_Sum

그럼 다음에 만나요~~ 

기부 버튼을 만들었습니다

단지 $1 의 작은 정성도 저에게는 큰 힘이 됩니다

기부해주신 분들을 기억하며

더 좋은 내용으로 보답해 드리겠습니다 :)

Donate 버튼은 paypal 결제로 paypal 계정이 없으시더라도

카드로도 기부 가능하십니다 :)

Use your credit card or bank account (where available). 옆의 continue 를 누르시면 됩니다

한주현 드림