분류 전체보기
-
[JAVA] Array.sort 와 Collections.sort 의 차이Language/Java 2020. 1. 13. 18:36
두개의 차이는 그냥 직관적으로도 정렬을 해주는 역할이고, Array.Sort는 배열을 정렬해주는 것이고 Collections.sort는 클래스의 객체를 정렬해주는 것이라고 생각이 든다. 파이썬에서는 sort가 있어서 너무 편했는데 자바는 없는 줄 알았지만 자바도 있었기 때문에 정리하려 한다. 1. Array.sort (오름차순) Array.sort는 java.util.Arrays에 포함되어 있다. 따라서 import를 시켜서 사용을 해야한다. 사용법에 대해서 알아보자. 위처럼 배열을 만들어서 java.util.Arrays를 import 시켜서 Arrays.sort(참조변수)를 하면 정렬이 된다. 정렬이 되는 기준은 오름차순으로 숫자 > 대문자 > 소문자 > 한글순 으로 정렬이 된다. 1-1) 배열 복사 ..
-
[JAVA] ArrayList와 LinkedList의 차이Language/Java 2020. 1. 12. 20:54
ArrayList vs LinkedList 차이 List 인터페이스의 구현체는 뭐가 있을까요? Stack, Vector, ArrayList, LinkedList가 있습니다. 이 중에서도 대표적인 클래스인 ArrayList, LinkedList 차이에 대해 정리해보겠습니다. ArrayList란? ArrayList는 중복을 허용하고 순서를 유지하며 인덱스로 원소들을 관리한다는 점에서 배열과 상당히 유사합니다. 배열은 크기가 지정되면 고정되지만 ArrayList는 클래스이기 때문에 배열을 추가, 삭제 할 수 있는 메소드들도 존재합니다. 하지만 추가했을 때 배열이 동적으로 늘어나는 것이 아니라 용량이 꽉 찼을 경우 더 큰 용량의 배열을 만들어 옮기는 작업을 하게 됩니다. 내부 코드를 보면서 ArrayList에 ..
-
퀵 정렬(quick sort)Computer Science/Data_Structure 2020. 1. 8. 22:36
퀵 정렬의 개념 퀵 정렬(quick sort)은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵정렬도 분할-정복(divide and conqure)에 근거한다. 퀵 정렬은 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵정렬하는 전형적인 분할-정복법을 사용한다. 그러나 합병 정렬과는 달리 퀵 정렬은 리스트를 다음과 같은 방법에 의해 비균등하게 분할한다. 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 처음에 리스트의 첫 번째 요소인 5를 피벗(pivot)으로 정하였다. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 ..
-
합병 정렬(merge sort) 란?Computer Science/Data_Structure 2020. 1. 7. 16:45
합병 정렬의 개념 합병 정렬(merge sort)는 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것이다. 합병 정렬은 분할 정복(divide and conquer) 기법에 바탕을 두고 있다. 분할 정복 기법은 대게 순환 호출을 이용하여 구현된다. 분할(divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 통합한다. 위의 과정을 그림으로 보면서 이해해보자. 다시 말하면, 위와..
-
버블 정렬(bubble sort) 란?Computer Science/Data_Structure 2020. 1. 7. 04:22
버블 정렬의 원리 버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이러한 리스트의 비교-교환 과정이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 이러한 비교-교환 과정은 전체 숫자가 전부 정렬될 때까지 계속한다. 바로 자바로 구현해보자. public class BubbleSort { public static void main(String[] args) { int[] list = {7, 4, 5, 1, 3}; int tmp = 0; // 버블 정렬 for (int i = list.length - 1; i > 0; --i) { for (int j = 0; j < i; +..
-
삽입 정렬(insertion sort) 란?Computer Science/Data_Structure 2020. 1. 7. 03:58
삽입정렬의 원리 삽입 정렬(insertion sort)은 손안의 카드를 정렬하는 방법과 유사하다. 우리는 카드 게임을 할 때, 새로운 카드가 들어오면 새로운 카드가 들어오면 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 한다. 삽입 정렬은 처음에 2번 째 위치의 값을 key로 정해서 시작한다. key 값을 자신의 왼쪽에 놓인 것들과 하나씩 비교하면서 자신의 위치를 찾으면 그 자리의 있는 것과 자리를 바꾸게 된다. 자바로 삽입 정렬을 구현해보자. 삽입 정렬의 복잡도 분석 삽입 정렬의 복잡도는 입력 자료의 구성에 따라서 달라진다. 최선의 경우는 먼저 입력자료가 이미 정렬되어 있는 경우는 가장 빠르다. 최악의 경우는 입력 자료가 역순일 경우이다. 최선의 경우 삽입 정..
-
선택 정렬(selection sort) 란?Computer Science/Data_Structure 2020. 1. 7. 02:07
선택 정렬의 원리 선택 정렬(selection sort)은 가장 이해하기가 쉬운 정렬 방법이다. 선택 정렬은 다른 추가 메모리를 요구하지 않는 정렬 방법인 제자리 정렬(in-place-sorting)을 이용한다. 초기 배열에서 최소값을 찾는다. 이 최소값을 배열의 첫번째 요소와 교환한다. 그리고 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다. 위의 절차를 (배열원소-1)만큼 반복하면 추가적인 배열을 사용하지 않고 정렬 가능하다. 이제 자바를 이용해서 선택 정렬을 구현해보자. 선택 정렬의 분석 선택 정렬의 성능 분석을 위하여 비교 횟수와 이동 횟수를 따로 구하여 보자. 먼저 비교 횟수를 구하기 위하여 두개의 for 루프의 실행 횟수를 계산해보자. 외부루프는..
-
해싱(Hashing) 이란?Computer Science/Data_Structure 2020. 1. 4. 16:08
오늘은 해싱의 개념에 대해서만 정리해보고자 한다 해싱(hashing) 이란? 선형 탐색이나 이진 탐색은 모두 키를 저장된 키 값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근한다. 이런 방법들은 최대 가능한 시간 복잡도가 O(logn)에 그친다. 이정도만 되어도 괜찮은 응용도 있지만, 어떤 응용에서는 더 빠른 탐색 알고리즘을 요구한다. 해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 해시 테이블(hash table) : 이렇게 키에 대한 연산에 의해 직접 접근이 가능한 구조 해싱(Hashing) : 해시 테이블을 이용한 탐색 더 효율적인 알고리즘은 없을까? 예를들어 O(1)의 시간안에 탐색할 수 있는건 없을까? 해싱은 O(1)의 시간안에 탐색을..