반응형 전체 글44 선택정렬(SelectionSort) - 선택 정렬 검색 범위에서 가장 작은 값을 찾아 왼쪽으로 이동시키는 정렬 방법이다. 버블 정렬 처럼 2중 for 문을 사용하기 때문에 시간 복잡도는 O(n^2)이며 그렇기 때문에 계산하는 시간이 느리다. 선택 정렬은 시간복잡도는 버블 정렬과 동일하지만 버블 정렬보다 성능이 좋다(조금) public class SelectionSort { public static void selectionSort(int[] list) { int indexMin, temp; for (int i = 0; i < list.length - 1; i++) { indexMin = i;// 범위중 가장 작은값 index for (int j = i + 1; j < list.length; j++) { if (list[j] < list[i.. 2020. 6. 1. 버블정렬 (BubbleSort) - 버블정렬(BubbleSort) 가장 기본인 정렬 방법 중 하나이다. 인접한 값을 비교하여 정렬하는 방법이다. 2중 for 문을 사용하기 때문에 시간 복잡도는 O(n^2)이며 그렇기 때문에 계산하는 시간이 느리다. public class BubbleSort { public static void bubbleSort(int[] arr) { int temp = 0; for(int i = 0; i < arr.length; i++) { for(int j= 1 ; j < arr.length-i; j++) { if(arr[j] 2020. 6. 1. Java 자료구조 - List, Set, Map - Collection 이란? Collection은 자료구조 List, Set 의 구현 객체이다(Interface). 하지만 Map 같은경우 List, Set과 달리 Key-Value 라는 구조적인 차이가 있어 Collection Interface를 구현(상속)하지 안고 별도로 정의하고 있다. List, Set 상속 관계 // ArrayList public class ArrayList extends AbstractList public abstract class AbstractList extends AbstractCollection implements List public abstract class AbstractCollection implements Collection // HashSet public c.. 2020. 5. 30. 2진 탐색 트리 알고리즘 (Binary Search Tree) - 용어 정리 노드(node) : 네트워크에서 연결 포인트 혹은 데이터 전송의 종점, 재분배점 등을 의미한다. 루트(Root) : 2진트리를 구성하는 최상위 노드 브랜치(Branch) : 노드와 노드를 연결 하는 선 레벨(Level) : 트리의 깊이를 의미한다. 서브 트리(SubTree) : 트리를 구성하는 트리(트리안에 있는 다른 트리) - 2진 탐색 트리 자식 노드가 최대 2개를 가질 수 있다. 왼쪽 자식 노드는 부모 노드보다 값이 작다. 외른쪽 자식 노드는 부모 노드보다 값이 크다. 입력 : 35 -> 18 -> 68 -> 7 -> 3 -> 12 ... 1. 35입력 비교할 부모 Node 값 없으무로 Root Node입니다. 2. 18 이 들어오고 부모노드인 35 와 비교 합니다. 작으면 왼쪽 크면.. 2020. 5. 26. 2진 탐색 알고리즘 (Binary Search Algorithm) - 2진 탐색 알고리즘 (Binary Search Algorithm) 2진 트리 알고리즘은 값이 정렬되어 있을 때 사용 가능한 검색 알고리즘 입니다. 순차(선형) 검색 알고리즘과 달리 리스트 앞부터 순차적으로 값을 찾는 방법이 아니무로 리스트가 길이가 길수록 순차 검색 알고리즘보다 빨리 검색 할 수 있습니다. 위 그림을 보면서 설명 하도록 하겠습니다. 리스트 길이는 10이고 그 중 정수 17을 찾는 방법입니다. 1. 찾고자 하는 범위에 중간의 Index 값(11)을 확인 합니다. -----> 2번째 List 그림 2. 1번에서 찾은 값(11)이 찾고자하는 값(17)이 아닐경우 1번에서 찾은 값(11)과 찾고자하는 값이(17) 비교하여 찾는 값이 크면 왼쪽의 범위를 배제하고, 작을 경우 오른쪽 범위를 배제.. 2020. 5. 26. 순차 검색 알고리즘 (Sequential Search) - 순차 검색 == 선형 검색 알고리즘 순차 검색 알고리즘은 단어 그대로의 알고리즘 입니다. 리스트에서 맨 앞에서부터 끝까지 차례대로 찾고자 하는 값을 찾는 방법입니다. 검색 방법 중 가장 단순한 방법이자만 리스트의 길이가 길어질 수록 검색하는데 시간이 오래걸리고 비효율적인 방법입니다. 시간 복잡도는 O(n) 입니다. ※ 1차 for문을 O(n) 이라고 표현 합니다. public class SequentialSearch { /** * 순차 탐색 * * O(n) 의 시간 복잡도를 가진다. * * for 문은 O(n) 의 시간 복잡도를 가진다. * * @param intList 검색 대상 * @param target검색할 값 * @return검색된 값 index */ static int searchIndex.. 2020. 5. 26. 이전 1 2 3 4 5 6 7 8 다음 반응형
