반응형 💻 programming/algorithm4 퀵 소트 (Quicksort) - c/c++ 20세기에 발견된 가장 중요한 알고리즘 중 하나 Mergesort와 함께 가장 많이 사용되는 정렬 알고리즘 재귀호출을 사용하며, Mergesort와 달리 파티션이라는 작업을 통해 어느정도 정렬한 뒤 재귀호출 수행 기본 아이디어 배열을 섞는다 파티션을 나눈다 : j를 기준으로 왼쪽에는 a[j]보다 작은 원소, 오른쪽에는 작지 않은 원소가 오도록 이동시킨다 : 여기서 j는 피벗 (pivot)에 해당한다 왼쪽 파티션과 오른쪽 파티션을 정렬한다 소스코드 /* C implementation QuickSort */ #include void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } int partition (int arr[], int low, int high) .. 2021. 5. 5. 기초 기호 표 (Elementary Symbol Table) 기초 기호 표 (Elementary Symbol Table) I. 기호 표 (Symbol Table) 기호 표 (Symbol table)는 추상적 개념에 연산을 추가하기 위해 고안된 자료구조로, 컴파일러 또는 인터프리터와 같은 언어 변환기에서 사용하고 있습니다. 이번 강의에서는 기호 표 자료구조를 위한 메서드와, 구현 방법에 대해 알아보겠습니다. I-1. Basic symbol table API 기호 표의 기본 메서드는 다음과 같습니다. key와 value 저장하기 - void put (key, value) 주어진 key로 value 검색하기 - value get (key) 주어진 key로 value 삭제하기 - void delete (key) 모든 key 내용 불러오기 - Iterable keys() .. 2021. 3. 26. 기본 정렬 (Elementary Sort) 기본 정렬 (Elementary Sort) 1. Comparable Interface 어떤 자료를 정렬하기 위해서는 대소관계를 판단할 수 있어야 합니다. Java에서는 대소관계를 판단할 수 있는 함수를 가지고 있다는 것을 보증하기 위해 Comparable Interface를 사용합니다. 이 인터페이스는 compareTo( )라는 메서드를 가지는데, 두 객체의 대소관계를 판단하여 작음(-1), 같음 (0), 큼(1)을 반환합니다. 1.1 Total order 객체의 크기가 비교 가능하려면 다음 규칙을 만족해야 합니다 v ≤ w 이고 w ≤ v 이면 v = w이다 v ≤ w 이고 w < x 이면 v ≤ x이다 v ≤ w 거나 w ≤ v 이다 1.2 Sort algorithm (c++) c++은 quick s.. 2021. 2. 26. 최대 합 부분 배열 (Maximum sub-array problem) 최대 합 부분 배열을 찾는 세 가지 방법에 대해 알아보자, 먼저 최대 합 부분 배열이란, 배열의 부분 배열들 중 원소의 합이 최대가 되는 부분 배열을 의미한다. 아래 예시에서는 arr[2 .. 6]이 최대 합 부분 배열이다. Largest Sum Contiguous Subarray - GeeksforGeeks (1) 전체 탐색: O(n^2) 가장 기본적인 방법으로 부분 배열의 시작을 i, 배열의 끝을 j라고 하고 이중 반복문을 이용하여 전체 탐색한다. int getMaxSumOfSubarrayWithBruteForce(const vector& arr) { int maxSum = -1; int tmpSum = 0; for(int i = 0; i < arr.size(); i++) { tmpSum = 0; f.. 2021. 2. 26. 이전 1 다음 반응형
