1. C3조 과제물 발표 2. 과제수행일지조원소개조장 박태원소 속C3 조자료조사김슬기, 김남희프로그래밍정준용, 허규준과제수행기간13 일 312 시간주 제 연구제목배열을 이용한 파스칼의 삼각형 n행 m열의 값, P(n,m) 계산하기 배열을 이용해 파스칼의 삼각형을 구성하는 숫자들의 행렬값 n, m을 입력받아 해당 행렬 에 존재하는 숫자의 값을 계산해 출력하는 프로그램의 알고리즘을 작성하고, 해당 알고리 연구배경즘의 프로그램 소스를 작성해 시간 복잡도와 공간 복잡도를 직접 계산해 봄으로써 배열의 사용법과 시간 복잡도, 공간 복잡도에 관한 내용을 이해하고 프로그램 개선에 응용할 수 있는 능력을 기를 수 있다.참 고 자 료참고 서적C로 쓴 자료구조론(저자 : 이석호, 교보문고 2nd) http://skmagic.tistory.com/164 : 시간 복잡도의 정의와 유형, 계산법 소개 http://blog.naver.com/cat8815?Redirect=Log&logNo=60005751431 : 시간, 공간 복잡도의 정의와 계산법 소개 http://loudon23.blog.me/20017968979?Redirect=Log&from=postView : 알고리즘의 복잡도표 http://www.scienceall.com/dictionary/dictionary.sca?todo=scienceTermsView&classid= &articleid=256188&bbsid=619&popissue참고 URL: 파스칼의 삼각형의 형태와 규칙 소개 http://blog.naver.com/wilber96?Redirect=Log&logNo=124490423: C언어 2차 배열을 이용한 파스칼 삼각형의 구현 http://whoknowwhat.blog.me/30039570929 : 배열을 이용한 무한 자리수의 출력 http://cafe.naver.com/cafec.cafe?iframe_url=/ArticleRead.nhn%3Farticleid=9373 : 무한자 리수 출력 알고리즘을 이용한 팩토리얼 계산기(해당 url질문글에 대한 카페스탭 itoma님의 답변내 용) http://blog.daum.net/glsgnphoenix220/498 : c언어를 이용한 nCr값 계산기 소스 과제의 수행 첫째날 2012년3 월8 일 목요일회의 주제 조원 자기소개 및 역할분담, 과제 파악 조장 : 박태원회의 내용 자료조사 : 김남희, 김슬기 프로그래밍 : 정준용, 허규준 3. 이상과 같이 이번 프로젝트의 역할분담을 실시했습니다.서로가 준비한 자료가 그리 많지 않았기에 프로젝트 내용이 제시된 pdf파일에 제시된 파스칼의 삼각형 성질을 토대로 어떻게 하면 n행 m열에 존재하는 숫자값을 출력할 수 있을지에 대해 논의를 시작했습니다.∘파스칼의 삼각형은 P(n,m)으로 나타낼 수 있음. 여기서 n은 행이고 m은 열이다.- m=1 or m=n일 때, P(n,m) = 1- P(n,m)=P(n-1,m-1)+P(n-1,m)PDF에 제시된 위의 두 가지 내용을 힌트를 사용해 배열을 가지고 어떻게 하면 파스칼의삼각형 n행 m열의 숫자값을 구할 수 있을까에 대해 논의를 하던 중 파스칼의 삼각형을 배열을 이용해 나타내는 방법을 이해하기 위해 우선 다른 사람들이 파스칼의 삼각형을 나타내기 위해 어떤 방법을 사용했는지에 대해 프로그래밍 팀과 알아보기로 했습니다.http://blog.naver.com/wilber96?Redirect=Log&logNo=124490423(2차 배열을 이용한 파스칼의 삼각형 구현 소스)우선, 그 당시에 찾은 2차 배열을 이용한 파스칼의 삼각형 구현 소스를 응용해서 행렬값[P(n,m)]을 구할 수 있지 않겠냐는 의견에 따라 아래와 같은 형태의 방법으로 P(n,m)을 구할 수 있는 방법을 함께 생각해 봤습니다.1000x1000사이즈의 배열을 지정한다↓ 파스칼의 삼각형 행렬의 값인 P(n, m)을 구하기 위한 n, m을 입력한다.↓ m=1이거나 m=n이라면 1을 출력한다. 그렇지 않다면, 아래로 진행한다.↓지정된 배열값에 파스칼의 삼각형의 행렬이 들어가도록 이중 for문을 이용한 파스칼의 삼각형 형태 구현↓ n행 m열에 해당하는 배열의 계산이 끝난 경우n행 m열에 해당하는 배열값 [P(n,m)] 출력프로그래밍 팀은 위처럼 간략하게 만들어진 알고리즘을 바탕으로 다음 수업시간까지 프로그램 소스를 작성해 어떤 문제점이 발생하는지 찾아보기로 했습니다.한편, 교재에 수록된 공간 복잡도(space complexity)와 시간 복잡도(time complexity)를설명하는 내용만으로는 복잡도에 대해 조원들이 완벽하게 이해하기 어렵다고 판단해 직접계산하는 자료조사팀인 남희와 슬기가 과정이 담긴 예제와, 이해하기 쉽게 내용이 정리된자료를 찾기로 했습니다.- 복잡도(complexity)에 대한 이해부족문제점- 파스칼의 삼각형에 대한 이해부족반성정해진 수업 내용을 듣고 그저 암기하는 것이 아니라 과제 수행에 필요한 내용을 직접 찾 - 2 - 4. 아서 익히고 응용해야 한다는 점에서 이전까지 해왔던 수업 방식에 비해 까다롭고, 어렵게 느껴졌습니다. 첫 수업이다 보니 과제 해결에 대한 준비도 많이 미흡했고 서로의 역할을 분담하는데 만도 오랜 시간을 사용해 버려서 과제의 요지를 파악하고 이를 해결할 수 있는 알고리즘을 구상하는데 필요한 시간을 제대로 분배하지 못했습니다. 다음 회의 전에는 좀 더 많은 자료들을 준비해서 알고리즘의 구상과 그 개량에 중점을 둘 수 있게 준비하도록 했습니다. 둘째날2012 년3 월13 일목요일회의주제시간, 공간 복잡도에 대한 조사내용 발표, 프로그램 소스 초안 발표 및 개량방안 제시 슬기와 남희가 조사해온 복잡도에 관한 내용을 함께 공부하고 주말간 제작해 온 프로그램 소스의 시간, 공간 복잡도를 직접 계산해 보기로 했습니다. 시간 복잡도의 정의 - 어떤 알고리즘을 실행하는데 얼마나 오랜 시간이 걸리는가 - CPU성능과 관계가 있습니다. 시간 복잡도의 세가지 표기법 - 세타[Θ(~)] 표기법 : 알고리즘 실행 시간의 평균적인 결과를 나타내는 표기법. - 오메가[Ω(~)] 표기법 : 알고리즘 실행 시간에 있어서 최선의 결과를 나타내는 표기법. - 빅오[O(~)] 표기법 : 알고리즘 실행 시간에 있어서 최악의 결과를 나타내는 표기법으로 가장 보편화되어 사용되고 있습니다. 빅오[O(~)] 표기법이 주로 쓰여지는 이유 - 평균적으로 10의 수행시간을 가지는 프로그램 소스라도 최악의 경우 100의 수행시간을 가지게 된다면 평균적으로 20의 수행시간을 가졌지만 최악의 경우에도 20의 수행시간을회의내용 유지할 수 있는 프로그램 소스에 비해 우수하다고 할 수 없기 때문입니다. 시간 복잡도의 계산 예제해당 명령의 실행 횟수를 계산해 오른쪽에 적습니다.사례)void Func(int *a, n){ int i=0, j=0;//1 for (i = 0 ; i < n-1 ; i++) //nfor(j=i+1; j다음으로 진행↓ n-1Cm의 값을 배열 a[0]에 저장↓ 배열을 이용한 a[0]값의 저장↓for문을 통한 배열 a[]의 역순 출력참고자료 – 팩토리얼 계산기 소스#include #define CboxAGE_MAX 5000 // 배열 최대값 지정int main(void){ int a, i, j; unsigned long int block[CboxAGE_MAX]; // 배열 지정 block[0]=1; // 동기화 for (j=1; jr; i--) {for (j=0; j0) printf("%05d x10^%d +n", box[j], j*5); printf("%05dn", box[0]); return 0;}//for문을 이용한 결과값의 출력해당 소스는 팩토리얼 계산기의 소스를 응용해 for문을 통한 계산식 내부에서 n행 m열에해당하는 결과값을 계산한 후 그 결과값을 배열 box[]에 10^5단위로 끊어 저장하고 해당배열을 역순으로 출력함으로서 n행 m열의 값에 해당하는 P(n,m)을 출력할 수 있도록 하는 형태를 하고 있습니다.회의 중점은 해당 소스의 개량안과 공간복잡도의 계산에 대한 내용을 위주로 진행되었으며회의 결과 if문을 이용한 구절을 추가해 잘못된 변수가 입력되었을 경우 프로그램이 강제종료되도록 하고 그 외에 프로세스에 큰 영향을 미치지 못하는 불필요한 변수들을 제거하는 것으로 프로그램의 개량에 대한 내용을 마치고 공간복잡도의 계산을 실시하도록 결정되었습니다.- 공간복잡도에 대한 이해 미숙문제점- 잘못되었거나 1000행 밖의 값이 입력되더라도 계산을 진행한다. - 9 - 11. 2차 배열을 통해 파스칼의 삼각형의 P(n,m)값을 구하려 했던 이전의 방식에 비해 적은 메반성모리 사용량을 가지게 되었다고 예상하고 있으나 공간 복잡도에 대한 이해 미숙으로 해당소스의 공간복잡도를 계산하지 못했습니다. 결과 발표#include #define MAX 300int main(void){ int n,r, i, j,cnt=0,k=1; unsigned long int box[MAX]; box[0]=1; for (j=1; jr) { r=n-r; }프로그램 소스 for(i=n; i>r; i--) {for (j=0; j0) {printf("%05d x10^%d +n", box[j], j*5); } printf("%05d입니다.n", box[0]); return 0;} - 10 - 12. 알고리즘 개요시간 복잡도- O(904+a(1000행 500열 출력시 while반복횟수))(n-r) + 917) = O(n)복잡도 계산공간 복잡도 - 602n-602r+6좀 더 시간을 두고 알고리즘을 개량 할 수 있었다면 더 좋은 결과를 낼 수 있었을 것 같아아쉬움이 남습니다. 하지만 이번 프로젝트 중에 가장 아쉬웠던 점은 조원들의 C언어에 대 최종 반성한 이해도가 전체적으로 낮다는 점인데 앞으로의 과제를 수행해 나가면서 좀 더 공부해 다음 프로젝트부터는 좀 더 좋은 결과를 낼 수 있었으면 좋겠다고 생각합니다.- 11 -