Array는 index로 빠르게 값을 찾는 것이 가능함 LinkedList는 데이터의 삽입 및 삭제가 빠름 ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림 배열 int arr[10]; String arr[5]; 선언할 때 크기와 데이터 타입을 지정해야 함 메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하는 자료구조다. 계속 데이터가 늘어날 때, 최대 사이즈를 알 수 없을 때는 사용하기에 부적합 중간에 데이터를 삽입하거나 삭제할 때도 매우 비효율적 특정 인덱스에 새로운 값을 넣어야 한다면 원래 값을 밀어내고 덮어씌워야 함 인덱스가 존재하기 때문에 위치를 바로 알 수 있어 검색이 편함 → 이를 해결하기 위해 나온 것이 List arrayList 배열처럼 크기를 정하지 않아도 됨 배열에서..

연결 리스트(Linked List) 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성 연결 리스트(Linked List) 사용 이유 배열은 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있지만 제한 사항이 있음 1. 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당을 받아야 함 2. 새로운 요소를 삽입하는 것은 비용이 많이 듬 장점 동적 크기 삽입/삭제 용이 단점 임의로 액세스를 허용할 수 없음 → 즉, 첫 번째 노드부터 순차적으로 요소에 액세스 해야함 포인터의 여분이 메모리 공간이 목록의 각 요소에 필요 LinkedList 선언 LinkedList list = new LinkedList();//타입 미설정 Objec..

배열 사이즈 구하기 int[] arr = {1, 2, 3, 4, 5} int n = arr.length; 배열 요소의 최댓값 구하기 static int maxOf(int[] a) { int max = a[0]; for(int i=0; i max) max = a[i]; return max; } 배열 요소의 역순 정렬 // 배열 요소 a[idx1]과 a[idx2]의 값을 바꿈 static void swap(int[] a, int idx1, int idx2) { int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t; } // 배열 a의 요소를 역순으로 정렬 static void reverse(int[] a) { for(int i=0; i

분할 정복이란? 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식 평균 : Θ(nlogn), 최선 : Ω(nlogn), 최악 : O(nlogn) mergeSort public void mergeSort(int[] array, int left, int right) { if(left < right) { int mid = (left + right) / 2; mergeSort(array, left, mid); mergeSort(array, mid+1, right); merge(array, left, mid, right); } } 퀵정렬과의 차이점 퀵정렬 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort) 합병정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬..

선택 정렬 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 최소값을 찾아 정렬하는 방식 평균과 최악 모두 수행 시간 복잡도는 O(n2) Process (Ascending) 주어진 배열 중에 최소값을 찾음 그 값을 맨 앞에 위치한 값과 교체 (pass) 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체 void selectionSort(int[] arr) { int indexMin, temp; for (int i = 0; i < arr.length-1; i++) { // 1. indexMin = i; for (int j = i + 1; j < arr.length; j++) { // 2. if (arr[j] < arr[indexMin]) { // 3. indexM..

버블 정렬 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 인접한 두 개의 레코드 키 값을 비교하여 서로 교환하며 정렬하는 방식 평균과 최악 모두 수행 시간 복잡도는 O(n2) Process (Ascending) 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외됨 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘..