스택(Stack) 입력과 출력이 한 곳(방향)으로 제한 LIFO(Last In First Out, 후입선출) : 가장 나중에 들어온 것이 가장 먼저 나옴 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법에 사용 push와 pop할 때는 해당 위치를 알고 있어야 하므로 기억하고 있는 ‘스택 포인터(SP)’가 필요함 스택 포인터는 다음 값이 들어갈 위치를 가리키고 있음 (처음 기본값은 -1) private int sp = -1; 1) push() : 데이터 넣음 public void push(Object o) { if(isFull(o)) { return; } stack[++sp] = o; } 스택 포인터가 최대 크기와 같으면 return 아니면 스택의 최상위 위치에 값을 넣음 2) pop() : 데이터 ..

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..