Kim'sWorlds

객제지향언어 객체지향언어란? 작은 문제들을 해결할 수 있는 객체들을 만든 뒤, 이 객체들을 조합해서 큰 문제를 해결하는 상향식(Bottom-up) 해결하는 개발언어다. 객체지향언어의 주요 특징 -코드의 재사용성이 높다.  새로운 코드를 작성할 때 기존의 코드를 이용하여 쉽게 작성할 수 있다. -코드의 관리가 용이하다. 코드간의 관계를 이용해서 적은 노력으로 쉽게 코드를 변경할 수 있다. -신뢰성이 높은 프로그래밍을 가능하게 한다. 제어자와 메서드를 이용해서 데이터를 보호하고 올바른 값을 유지하도록 하며, 코드의 중복을 제거하여 코드의 불일치로 인한 오동작을 방지할 수 있다. 클래스와 객체 클래스의 정의 : 클래스란 객체를 정의해 놓은 것이다. 클래스의 용도 : 클래스는 객체를 생성하는데 사용된다. 객체의 정의 : 실제로 존재하는 것 사물 또는 개념 객체의 용도 : 객체가 가지고 있는 기능과 속성에 따라 다르다. 객체와 인스턴스  예를들어 자동차클래스로부터 만들어진 객체를 자동차클래스의 인스턴스라고 한다. 같은 의미이지만, 객체를 모든 인스턴스를 대표하는 포괄적인 의미를 가지고 있다. 인스턴스는 어떤 클래스로부터 만들어진 것인지를 강조하는 보다 구체적인 의미를 가지고 있다.  자동차는 인스턴스다 라기보다 자동차는 객체다. 라는 쪽이, 자동차는 자동차 클래스의 객체다라기 보다는 자동차는 자동차 클래스의 인스턴스다 라고 하는게 좋다.  클래스를 인스턴스화 시키면  인스턴스(객체)가 된다. 객체의 구성요소 속성 : 멤버변수, 특성, 필드, 상태 기능 : 메서드, 함수, 행위 예를들어 자동차의 속성에는 자동차의 브랜드, 차종, 차량 크기 등이 있다. 자동차의 기능에는 전진, 후진, 음악틀기 등이 있다. 인스턴스의 생성과 사용, 변수 https://github.com/happydhKim/MyDataStructureAlgorithm/blob/ma...

위상 정렬 (Topoligical Sort) DAG에 속해 있는 알고리즘  - 어떤 일을 하는 순서를 찾는 알고리즘 이다. - 1-> 2 이런 식의 그래프가 있다고 하면, - 2를 하기 전에 1을 먼저 해야 하는 알고리즘이다. - BFS와 비슷한 알고리즘 위의 그림을 예로 들겠다. A에서 D로 가고 싶다. 하지만 D를 가르키는 간선이 두개가 있다.(정점 A와 C에서 나온 간선) 위상 정렬은 이 두개의 간선을 먼저 탐색을 해야지 D를 검색 할 수 있는 것이다. 어디에 쓰일 수 있을까? 기본적으로 선행과목을 예시로 들 수 있다. 가령 과목 D를 듣고 싶다. 과목 D를 듣기 위해선 우선 적으로 A와 B 그리고 C과목 까지 들어야 D과목을 들을 수 있다. 위상정렬 기본적인 자바 코드 Queue<Integer> q = new LinkedList<Integer>(); for (int i = 1; i &lt;= n; i++) { if (inDegree[i] == 0) { q.add(i); } } for (int k = 0; k &lt; n; k++) { int x = q.remove(); System.out.print(x + " "); for (int y : a[x]) { inDegree[y] -= 1; if (inDegree[y] == 0) { q.add(y); } } }

힙 정렬  Heapsort 힙 정렬 (Heapsort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다. 최대 힙을 구성한다. 최대 힙이란 부노드가 자노드보다 큰 트리를 말하는데, 단말 노드를 자노드로 가진 부노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다. 2와 3을 반복한다. 이진 트리를 최대 힙으로 만들기 위하여 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어 지므로  {\displaystyle O(\log n)} 의 수행시간이 걸린다. 구성된 최대 힙으로 힙 정렬을 수행하는데 걸리는 전체시간은 힙 구성시간과  {\displaystyle n} 개의 데이터 삭제 및 재구성 시간을 포함한다. 시간 복잡도는 = (log n+log(n-1)+...+log 2) = (log n+log(n-1)+...+log 2)+(log n+log(n-1)+...+log 2) = O(n*log n) 따라서 힙 정렬은 일반적인 경우  {\displaystyle O(n\log n)} 의 시간복잡도를 가진다. 위키 피디아 참조. 자바 코드 public class JAVAHeap{ public static void main(String[] args) { int[] arr = { 69, 10, 30, 2, 16, 8, 31, 22 }; HeapSort(arr); } public static void HeapSort(int[] arr...

버블정렬 BubbleSort 단순한 알고리즘으로 거품으로 비유를 하지만 개인적으로 물고기가 팔짝팔짝 뛰는 것을 연상했다. 1. 인접한 두 인덱스를 비교해서 정렬이 되어있지 않을경우 정렬한다. 2. 리스트 처음부터 끝까지 이런식의 정렬을 하고 나면 제일 마지막 리스트에는 제일 큰 값(또는 작은 값)이 저장된다. 3. 다시 처음 리스트부터 마지막 리스트 이전 리스트까지 서로 이웃한 인덱스를 비교해가며 정렬한다. 4. 위 방법으로 계속해서 정렬한다. 쉽게 말해 인접한 두 수를 비교해서 큰 수 혹은 작은 수를 뒤로 보내는 형태이다. 이해하기 쉬운 동영상 자바 코드 public class BubbleSort { public static void main(String[] args) { int[] data = { 4, 54, 2, 8, 63, 7, 55, 56 }; int temp; int cnt = 0; System.out.print("======정렬 전===============\n"); for (int m = 0; m < data.length; m++) { System.out.print(data[m] + ", "); } for (int i = data.length; i > 0; i--) { // for (int j = 0; j < i - 1; j++) { cnt++; if (data[j] > data[j + 1]) { temp = data[j]; data[j] = data[j + 1]; data[j + 1] = temp; } } } System.out.print("\n\n======Bubble Sort=========\n"); for (int k = 0; k < data.length; k++) { ...

이진탐색 Binarysearch 이진탐색(binary search)는 정렬되어 있는 자료들의 집합에서 특정 자료를 찾고자 할 때 많이 사용되며 매우 빠른 탐색 알고리즘이다. 이미지 출저 : http://anster.tistory.com/152 위의 그림 처럼 임의의 숫자가 가능한지 아닌지를 알아내기 쉬운 방법이다. JAVA 코드 public class Binarysearch { public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; binarySearch(2, arr); } public static void binarySearch(int iKey, int arr[]) { int mid; int left = 0; int right = arr.length - 1; while (right >= left) { mid = (right + left) / 2; if (iKey == arr[mid]) { System.out.println(iKey + " is in the array with index value: " + mid); break; } if (iKey < arr[mid]) { right = mid - 1; } else { left = mid + 1; } } } }

퀵 정렬 QuickSort -임의의 숫자를 기준(Pivot)으로 작거나 같은 값을 지닌 숫자는 앞으로, 큰 값을 지닌 숫자는 뒤로 가도록 하여 작은 값을 갖는 숫자와 큰 값을 갖는 숫자로 분리해가며 정렬 -데이터가 실시간으로 입력되고 있을 때 효율적 이해하기 위한 동영상 JAVA 코드 public class QuickSort {         public void sort(int[] data, int l, int r){         int left = l;         int right = r;         int pivot = data[(l+r)/2];                 do{             while(data[left] < pivot) left++;             while(data[right] > pivot) right--;             if(left <= right){                   int temp = data[left];                 data[left] = data[right];                 data[right] = temp;                ...

병합정렬 MergeSort   -보통 데이터가 엄청 많을때 사용하는 방식 -쪼갠 후에 쪼개진 아이끼리 순서를 맞춰줘서 병합 후에 다시 맞추고 가는 방식 이해를 위한 동영상 자바 코드 public class MergeSort { public static void main(String[] args) { //1. 입력 : 원본 데이터가 정렬되어있다고 가정, 오름차순 int[] first = {1, 3, 5}; int[] second = { 2, 4 }; int[] mearge = new int[first.length + second.length]; // MEARGE될 배열 int i = 0, j = 0, k = 0; //i : first 인덱스 , j : second 인덱스, k : mearge 인덱스 int m = first.length; int n = second.length; //2. 처리 while(i < m && j < n){ if(first[i] <= second[j]){ mearge[k++] = first[i++]; }else{ mearge[k++] = second[j++]; } } while(i<m){ mearge[k++] = first[i++]; } while(j<n){ mearge[k++] = second[j++]; } //3. 출력 for(int p = 0; p< mear...

삽입정렬 InsertionSort 가장 큰 ( 작은 ) 값을 시작으로 보내고 , 남은 데이터를 적당한 위치에 삽입하며 정렬 된 영역을 키워간다 . 이해하기 쉬운 영상 자바 코드 public class InsertionSort {   public static void main(String[] args) {     int[] index = { 4, 1, 3, 5, 2 };     int i, j, temp, in;     for (i = 1; i < index.length; i++) {       in = index[i];       for (j = i - 1; (j >= 0) && (in < index[j]); j--) {         index[j + 1] = index[j];       }       index[j + 1] = in;     }     for (i = 0; i < index.length; i++) {       System.out.print(index[i] + " ");     }   } }

선택정렬 SelectionSort 가장   큰 ( 작은 )  값을   끝으로   보내고 ,  작아진   영역에서   동일한   처리를   반복해   나간다 .  교체작업을 한다. 간단한 예로 3,5,7,9,1,4 로 구성된 배열이 있다고 하자. 1 까지   확인   후에  9 를   맨   뒤로   보냄 ( 4 와   교환 )   결과 :   3,5,7,4,1,9 다음   다시  1 까지   검사   후   가장   큰   값   맨   뒤로   보냄 가장 큰 값이었던 9 전으로 이동  결과 : 3,5,1,4,7,9 다음 결과 : 3,4,1,5,7,9 다음 결과 : 3,1,4,5,7,9 마지막 결과 : 1,3,4,5,7,9 쉬운 이해를 돕기 위한 동영상 자바 코드 public class SelectionSort { public static void main(String[] args) { int indexMin, temp; for (int i = 0; i < list.length - 1; i++) { indexMin = i; for (int j = i + 1; j < list.length; j++) { if (list[j] < list[indexMin]) { indexMin = j; } } temp = list[indexMin]; list[indexMin] = list[i]; list[i] = temp; } } }...