일렬의 연속적으로 나열되어 있는 정수들로 이루어진 합의 값들 중 최대의 값을 지니는 찾는 프로그램을 작성하여라.

소개글

1. 아래의 세 가지 알고리즘을 가지고 시간복잡도를 분석하시오

방법 1) 모든 구간 i, j (i ≤ j) 에 대하여 구간 [i, j]의 정수들 ai, ..., aj의 합을 구하여 이들 합 중 최대값을 찾는다.

방법 2) 모든 구간 i, j (i ≤ j)에 대하여 구간 [i, j]의 정수들 ai, ..., aj의 합을 구할 때, 구간 [i, j-1]의 합을 이용한다.

방법 3) 모든 i에 대하여 i에서 끝나는 구간 중 합이 최대인 것을 구하여 S[i]에 저장한다.
S[i] = S[i-1] + ai if S[i-1] > 0이면
= ai 그렇지 않으면.

2. 위의 각 방법을 구현한 후, 이를 다음의 각 n에 대하여 수행 시간을 측정하여 그래프로 나타내시오.

N = 10, 100, 500, 1000, 2000, 5000, 10000, 20000

목차

□ 문제정의
□ 문제 해결방법 & 분석
□ 수행결과
□ 결 론
□ 소스 코드

본문내용

□ 문제정의

일렬의 연속적으로 나열되어 있는 정수들로 이루어진 합의 값들 중 최대의 값을 지니는 찾는 프로그램을 작성하여라.

1. 아래의 세 가지 알고리즘을 가지고 시간복잡도를 분석하시오

방법 1) 모든 구간 i, j (i ≤ j) 에 대하여 구간 [i, j]의 정수들 ai, ..., aj의 합을 구하여 이들 합 중 최대값을 찾는다.

방법 2) 모든 구간 i, j (i ≤ j)에 대하여 구간 [i, j]의 정수들 ai, ..., aj의 합을 구할 때, 구간 [i, j-1]의 합을 이용한다.

방법 3) 모든 i에 대하여 i에서 끝나는 구간 중 합이 최대인 것을 구하여 S[i]에 저장한다.
S[i] = S[i-1] + ai if S[i-1] > 0이면
= ai 그렇지 않으면.

2. 위의 각 방법을 구현한 후, 이를 다음의 각 n에 대하여 수행 시간을 측정하여 그래프로 나타내시오.

N = 10, 100, 500, 1000, 2000, 5000, 10000, 20000


□ 문제 해결방법 & 분석

1. 방법 1 : 문제 정의에서 나타내는 첫 번째 알고리즘은 총 3개의 loop를 이용한다. 가장 상위에 있는 loop는 i부터 j까지 순차적으로 하나씩 증가한다. 그리고 그 하위에 있는 loop는 그 바로 위의 상위 loop처럼 i부터 j까지 순차적으로 하나씩 증가한다. 그리고 제일 하위에 있는 세 번째 loop는 첫 번째 loop가 가리키고 있는 수부터 두 번째 loop가 가리키고 있는 수까지 또 순차적으로 증가하면서 그에 해당하는 수(배열의 인덱스 값을 이용)를 계속 더해준다. 그래서 지금 더해서 나온 값이 현재 저장하고 있는 가장 큰 값보다 크다면 그 값을 대체시킨다.

참고 자료

없음