Programming2009.04.04 16:45
 루프 불변성의 개념이 계속 헷갈린다... for 문에 들어가는 3개의 식과 비슷한 의미 인거 같긴 한데...

이걸 계속 알아보다가 다음의 3개의 글을 찾았다. 루프 불변성에 대해서 알아보고 있다면 다음 글들이 도움이 될것 같다.


http://blog.naver.com/soonchan86/130023452408

http://kin.naver.com/detail/detail.php?d1id=1&dir_id=10104&eid=SNrxjFB+YKL9IbR5XPWfyWcgQZksjxXC&qb=bG9vcCBpbnZhcmlhbnQ=&pid=fnNHoloi5UlssvNPEO0sss--364302&sid=SPc5opUv90gAADcell4

http://en.wikipedia.org/wiki/Loop_invariant

루프 불변성은 알고리즘이 정확한지를 귀납법을 통해서 증명하는 것이라고 한다.

loop를 돌면서 항상 참인 코드가 실행되는것인가 뭐 그런거 같은데...

좀더 알아볼 필요가 있을거 같다
신고
Posted by 초프(초보 프로그래머)
Programming2009.03.29 12:10

f(),g() 는 함수이며, c는 상수이다.

θ(세타) :  g(n)을 f(n)의 점근적으로 정확한 한계(asymptotically tight bound)
θ(g(n)) = {f(n) : 모든 n>=n0에 대해 0<=c1g(n)<=f(n)<=c2g(n)인 양의 상수 c1, c2, n0이 존재 한다}

Ο(빅-오, 오) : 점근적 상한
Ο(g(n)) = {f(n) : 모든 n>=n0 에 대해 0<=f(n)<=cg(n)인 양의 상수 c, n0이 존재한다}

Ω(빅-오메가, 오메가) : 점근적 하한
Ω(g(n)) = {f(n) : 모든 n>=n0 에 대해 0<=cg(n)<=f(n) 인 양의 상수 c,n0이 존재한다}

ο(리틀-오) : 점근적으로 여유있는 상한
ο(g(n)) = {f(n) : 임의의 양의 상수 c>0 에 대해 그리고 모든  n>=n0 에 대해 0<=f(n)<=cg(n)인 양의 상수 n0 이 존재한다}

ω(리틀-오메가) : 점근적으로 여유있는 하한
ω(g(n)) = {f(n) :  임의의 양의 상수 c>0 에 대해 모든 n>=n0에 대해 0<=cg(n)<f(n)인 양의 상수 n0이 존재한다}

신고
Posted by 초프(초보 프로그래머)
Programming2009.03.19 18:42

QuickSort 의 시작은 임의의 수를 pivot 이라고 정하면서 시작된다.

int data[] = {6, 9, 14, 4, 7, 3, 1, 10};

이런 값들의 List 가 있을경우 6을 pivot을 정한다고 가정하면 j가 [1]~[7] 으로 움직인다고 하자

그리고 i=0 으로 초기화 되어있다. 그럼 j는 1부터 커지면서 pivot 인  6보다 작은 수가 있는지 찾는다.

만약 작은 수가 있는 j를 발견하면 ++i 와 j를 바꾼다. data[++i] 와 data[j] 를 바꾸는 것이다.

그럼 처음으로 바뀌는 번호가 4와 9가 된다. j는 3 이고 i는 ++i가 되어서 1인 경우이다.

이렇게 반복해서 [7]까지 가면 pivot, pivot >  x, pivot < x 이와 같은 순서로 놓이게 된다.

그럼 pivot 위치를 중간에 높이게 하면된다. 이때 쉽게 바꾸는 방법은 위에서 사용한 i를 쓰면 마지막으로

작은 수를 옮긴 위치를 알수 있기때문에 한번에 바꿀수가 있다

QuickSort를 c언어로 작성하여 첨부파일에 포함하였다.
신고
Posted by 초프(초보 프로그래머)
Programming2009.03.12 20:10


테스트 파일은 삽입정렬과 같지만 인스턴스생성해주는 부분만 바뀌었습니다.

두 조각으로 계속 나누다가 마지막에 하나가 남으면 다시 위로 병합하면서 정렬하는 병합정렬

이번에는 삽입정렬과는 다르게 생성자를 따로 만들지 않았다.
정렬할때 매개변수로 바로 입력값을 넣게 하였다.
실제로 사용자가 쓸수 있는 메소드는 단 하나 sort 메소드



테스트는 수업시간에 나온 예제 숫자입니다. 삽입정렬과 같은 숫자네;;

9 1 3 2 7 5 4 8  <-- 입력값
1 2 3 4 5 7 8 9  <-- 정렬후

신고
Posted by 초프(초보 프로그래머)
Programming2009.03.12 19:35

 


오늘 배운 삽입정렬이다.

InsertionSort.class 가 삽입정렬 클래스 입니다.
sort_test.class 는 정렬 테스트를 위한 메인함수가 있는 클래스 입니다.

다른 정렬도 배우는 대로 추가할까 합니다.

멤버변수 data는 배열인데... 오타네요;; int data[] 이게 맞아요;

생성자와 정렬메소드를 제외하고는 외부에서 쓸필요가 없으므로 private로 접근제한 하였습니다.
생성자 함수로 정렬할 배열값을 입력하고 sort() 메소드를 호출하므로써 모든 과정이 끝납니다. sort() 는 정렬된 배열을 리턴합니다.


수업시간에 예제로 나온 숫자들로 테스트 하였습니다. 다른 숫자는 테스트안해봐서... 정확성을 뭐라 말할 수가 없네요;;

9 1 3 2 7 5 4 8  <--- 입력값 
1 2 3 4 5 7 8 9  <--- 정렬후

신고
Posted by 초프(초보 프로그래머)
Programming2009.03.06 21:49

이게 맞는지 모르겠지만 -_-;

오른쪽에 현재의 값보다 모두 작은 수인 것만을 뽑아낸것이 RDE 인가 그런가 보다 -_-;



10,9,5 는 오른쪽에 13 이 있으므로 RDE가 안되고

13 은 오른쪽에 모두 13 보다 작은 값이므로 RDE 이다.

2,7,1 은 8 때문에 RDE가 안된다.

8 은 오른쪽에 모두 8 보다 작으므로 RDE 이다.

4 는 6 때문에 안되고 6,3은 RDE 이다.

과제는 아니지만.. 그냥 해봤음;;
신고
Posted by 초프(초보 프로그래머)
Programming2008.07.01 00:23
사용자 삽입 이미지

친구가 풀던 문제인데.... 편입 기초수학에서 배우던 부분을 적용시켜 봤음;

테스트는 밑에 주소로 하면됨;

p1, p2, p3는 좌표를 입력하는 것임

콤마를 구분으로 x좌표,y좌표 입니다.

그리고 삼각형안에 있는것만 표시되고 선과 겹치는건 표시가 안됩니다;

빨리만든다고 허접해졌네요;

안허접해도 별로 달라질건 없는 실력이지만;;

http://family7914.cafe24.com/test/three.php?p1=10,10&p2=25,15&p3=15,25
신고
Posted by 초프(초보 프로그래머)