송홍엽 데이터 구조 프로젝트 파일( sparse matrix의 transpose, Max subsequence sum 4가지 알고리즘, List bucket sorting )

소개

sparse matrix의 transpose를 구하는 프로그램,
Max subsequence sum( 랜덤으로 숫자를 발생시켜 연속된 배열에 입력하고 가장 합이 커지는 합을 구하는 것)
을 4가지 서로 다른 알고리즘을 통해 구하고 각각의 알고리즘에서 걸리를 시간을 측정함, List에 여러가지 숫자를 입력시키고, bucket sorting을 함, 그리고 중복된 숫자를 삭제하여 같은 숫자를 한번씩 입력하게 함.

목차

(Ⅰ) 강의자료

(1) 문제 접근 방법
(2) 세부적 풀이
(3) 소스 분석
(4) 결과 분석
(Ⅱ) 문제

(1) 문제 접근 방법
(2) 세부적 풀이
(3) 소스 분석
(4)결과 분석

(Ⅲ) 게시판의 data1.txt 와 data2.txt를 이용하여 다음을 수행하시오.

(1) 문제 접근 방법
(2) 세부적 풀이
(3) 소스 분석
(4) 결과 분석

본문내용

(Ⅰ) 강의자료
1. 문제
sparse matrix의 transpose를 구하는 프로그램 작성 및 수행.

(1) 문제 접근 방법
matrix의 transpose를 구하는 것이기 때문에 언뜻 보면 단순히 matrix를 변수로 하고 이 matrix의 원소를 입력하여 transpose를 구하는 프로그램을 짤 수 있지만, sparse matrix는 특히 원소에 0이 많은 matrix를 말한다. 따라서 matrix를 통째로 변수로 하는 것은 데이터가 들어가는 용량을 낭비하는 결과를 초래할 수 있다. 그래서 이 matrix의 원소들을 하나의 array로 하고 이 어레이는 각각 원소, 원소의 행과 열을 포함하는 구조체로 만들기로 했다.

<중 략>

(2) 세부적 풀이
이를 위해 4가지 알고리즘을 생각해야 하는데 그 알고리즘은 다음과 같다.
①알고리즘1
알고리즘 1에서 a[500]에 rand 함수로 데이터를 넣는다. 연속된 숫자들의 합을 계산하기 위해 합을 재시 시작할 시작점 i와 끝점 j를 정할 것이다. for문 두개를 가지고 sum이라는 변수에 숫자들을 더해 나간다. for문이 끝나고 만들어진 sum과 그 이전과 비교해 만들어진 Maxsum을 비교해 가장 큰 Maxsum을 찾는다.
②알고리즘2
알고리즘 1에서는 시작점을 정하고 마지막 점을 정하여 그 사이의 원소들을 모두 더하였다. 하지만 이 경우 시작점이 같은 sum들에서 같은 계산이 중복된다. 알고리즘2에서는 이렇게 중복되는 계산들없이 시작점에서 출발하는 i가 증가함에 따라 바로 sum이 나온다. 중복되는 계산을 줄여서 알고리즘 2는 알고리즘 1보다 상대적으로 빠르다.

<중 략>

start= clock();
for(i = 0;i<100; i++) algorithm3();
end = clock();
printf("알고리듬3을 돌린시간은 %f입니다\n\n", (double)(end-start)/CLOCKS_PER_SEC);

start= clock();
for(i = 0;i<100; i++) algorithm4();
end = clock();
printf("알고리듬4을 돌린시간은 %f입니다\n\n", (double)(end-start)/CLOCKS_PER_SEC);

참고자료

· 없음