알고리즘 썸네일형 리스트형 퀵정렬 Divide and Conquer paradigm 사용 Partitioning 어떤 pivot이라고 하는 element를 기준으로 왼쪽은 작거나 같은것 오른쪽은 같거나 큰것 이것을 재귀로 호출 퀵 정렬은 pivot을 어떻게 잡느냐에 따라 성능에 영향을 미침. Soudo code QuickSort(A,p,r) If p 더보기 힙정렬 구현 힙이란 우선순위 큐를 표현 한 완전이진트리 기본적으로 i 번째 자식의 요소는 2*i번(왼쪽) 2*i+1이다. 최대 힙 트리(MaxHeapify)나 최소힙 트리를 구성해 정렬 삽입 Insert 트리의 끝부분에 값을 삽입하는 함수 upHeap 삽입된 값의 위치를 찾아주는 함수 삭제 DeleteMax 트리의 뿌리 부분에 존재하는 최대값을 제거 downHeap대소 관계에 의해 트리를 재구성 최대힙 정렬 예 N개의 노드에대한 완전 이진트리 구성 ->배열로 최대 힙 구성 부모노드가 자식노드보다 큰 트리 MaxHeapify 배열 마지막 값과 배열 첫번째 값을 교환 배열의 길이를 1줄인후 2,3반복() -> 2번을 수행하게 되면 배열의 첫번째 값에 가장큰 값 3번을 통해 큰값을 맨뒤로 보낸 후 맨 뒷값을 제외하고 2,.. 더보기 힙정렬 힙 구조 맥스 힙 특성 ( A[PARENT(i)]>=A[i] ) 부모 노드의 값은 항상 자식의 노드의 값보다 크다. 따라서 전체 트리의 Root 노드 값이 가장 크다. 또한 각 하위 트리 구조의 Root 노드가 가장 큰 값을 가진다. 최소 힙 특성 부모노드의 값보다 크다. - 힙구조 PARENT(i) Return[i/2] LEFT(i) Return[2i] RIGHT(i) Return2i+1 노드의 높이 Simple path vertax가 곂치지 않고 제일 쉽게 내려가는 경우 힙의 높이 O(logN) 2. 힙특성 관리 Max-Heapify 의 수행시간.,T(n) N을 하위 트리의 노드의 개수라고 할 때, '노드의 값을 바꿀때 수행시간: O(1) 힙의 높이 O(h)=O(lgn) 따라서 전체 수행시간은 : O.. 더보기 합병정렬 합병정렬 머지소트의 디자인 패턴 : divide- conquer Divide 단계에서 입력 값이 기준 값보다 작거나 같으면 정렬 그렇지 않으면 더 작은값으로 쪼갠다. Conquer 단계에서는 재귀로 더 작은값으로 쪼개진 하위 부분을 정렬 Combine 단계에서 합병을 통해 정렬 완성. 구현 배열의 원소가 없거나 하나가 있다면 return 함.// 정렬 완료 Conquer: 재귀적으로 나눠진 배열 을 divide와 정렬 Combine 정렬된 배열 합병 더보기 정렬 2016-05-18 오후 4:16 정렬이란?? 정렬을 n개의 숫자로 입력받아 점점 커지거나 작아지는 순서로 배열, 나열 하는것 오름차순 increasing order 내림차순decreasing order 선택정렬 설명을 하자면 단계적으로 설명하는게 효과적이다. 한마디로 "선택을 해서 정렬을 하는 알고리즘이다. " 그럼 무엇을 선택할래 ? 최소값 선택 오름차순 최대값 선택 내림차순 최소값이나 ㅅ최대값을 선택해서 정렬한다. - 최소값 선택정렬 정렬되지 않은 숫자중에 가장 작은 숫자 선택 선택한 숫자를 정렬되지 않은 숫자들 중 첫번째 숫자와 바꾸면 정렬된것이다. 다시 1번 부터 반복 정확성 증명 수학적 귀납법 이용 i 번째 선택한 숫자가 i번째 작은 숫자인지를 증명 성능분석 최고차 항을 세타로 표현 모든 숫자.. 더보기 그래프 알고리즘 - 그래프 알고리즘 무방향 그래프와 방향성 그래프 출처 : www.slideshare.net 무방향 그래프에서는 꼭지점 1에서 2의 변과 2에서 1의 변은 같다 방향그래프에서는 서로 다른 변이다. 방향그래프는 진입차수와 진출 차수로 구분한다. 꼭지점을 n이라하고 변의 개수가 n(n-1)/2개이면 완전그래프라 한다. - 그래프 표현법리스트형태로 저장 적은 메모리 공간, 느림행렬 저장 많은 메모리 공간, 빠른 - 탐색 방식최대 꼭지점의 개수방문한 노드를 표시하는 변수 - DFS깊이 우선 탐색 방식맨 아래까지 이동하면서 탐색 - BFS너비 우선 탐색인접한 꼭지점을 바로 방문하는 방식Queue를 만들어서 넣는 순서대로 방문 더보기 이전 1 다음
