본문 바로가기

알고리즘

(7)
루프 불변성 ( loop invariant ) 루프 불변성의 개념이 계속 헷갈린다... 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 루..
점근적 표기 f(),g() 는 함수이며, c는 상수이다. θ(세타) : g(n)을 f(n)의 점근적으로 정확한 한계(asymptotically tight bound) θ(g(n)) = {f(n) : 모든 n>=n0에 대해 0
퀵정렬(quick sort) 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 이와 같은 순서로 놓이게 된다. 그럼 p..
병합정렬 (Merge Sort) 테스트 파일은 삽입정렬과 같지만 인스턴스생성해주는 부분만 바뀌었습니다. 두 조각으로 계속 나누다가 마지막에 하나가 남으면 다시 위로 병합하면서 정렬하는 병합정렬 이번에는 삽입정렬과는 다르게 생성자를 따로 만들지 않았다. 정렬할때 매개변수로 바로 입력값을 넣게 하였다. 실제로 사용자가 쓸수 있는 메소드는 단 하나 sort 메소드 테스트는 수업시간에 나온 예제 숫자입니다. 삽입정렬과 같은 숫자네;; 9 1 3 2 7 5 4 8
삽입정렬 (Insertion Sort) 오늘 배운 삽입정렬이다. InsertionSort.class 가 삽입정렬 클래스 입니다. sort_test.class 는 정렬 테스트를 위한 메인함수가 있는 클래스 입니다. 다른 정렬도 배우는 대로 추가할까 합니다. 멤버변수 data는 배열인데... 오타네요;; int data[] 이게 맞아요; 생성자와 정렬메소드를 제외하고는 외부에서 쓸필요가 없으므로 private로 접근제한 하였습니다. 생성자 함수로 정렬할 배열값을 입력하고 sort() 메소드를 호출하므로써 모든 과정이 끝납니다. sort() 는 정렬된 배열을 리턴합니다. 수업시간에 예제로 나온 숫자들로 테스트 하였습니다. 다른 숫자는 테스트안해봐서... 정확성을 뭐라 말할 수가 없네요;; 9 1 3 2 7 5 4 8
알고리즘 - Right Dominant Elements 이게 맞는지 모르겠지만 -_-; 오른쪽에 현재의 값보다 모두 작은 수인 것만을 뽑아낸것이 RDE 인가 그런가 보다 -_-; 10,9,5 는 오른쪽에 13 이 있으므로 RDE가 안되고 13 은 오른쪽에 모두 13 보다 작은 값이므로 RDE 이다. 2,7,1 은 8 때문에 RDE가 안된다. 8 은 오른쪽에 모두 8 보다 작으므로 RDE 이다. 4 는 6 때문에 안되고 6,3은 RDE 이다. 과제는 아니지만.. 그냥 해봤음;;
[알고리즘] 삼각형안에 들어가는 점 찾기 친구가 풀던 문제인데.... 편입 기초수학에서 배우던 부분을 적용시켜 봤음; 테스트는 밑에 주소로 하면됨; p1, p2, p3는 좌표를 입력하는 것임 콤마를 구분으로 x좌표,y좌표 입니다. 그리고 삼각형안에 있는것만 표시되고 선과 겹치는건 표시가 안됩니다; 빨리만든다고 허접해졌네요; 안허접해도 별로 달라질건 없는 실력이지만;; http://family7914.cafe24.com/test/three.php?p1=10,10&p2=25,15&p3=15,25