CS지식
-
JAVA 자료구조 (리스트) - LinkedList 3 (기타작업)CS지식/자료구조 2024. 1. 3. 14:45
LinkedList 기타 작업 나머지 작업들을 하나씩 정리해보자. 리스트의 k번째 원소를 알려주는 함수 get(k)는 k번째 노드를 찾은 다음 그 노드의 원소를 리턴한다. 알고리즘 5-13 연결 리스트의 k번째 원소 알려주기 public T get(int k){ return getNode(k).item; } k번째 노드를 찾는 함수 getNode(k)는 여러 함수에서 필요한 보조 작업으로 코드는 다음과 같다. 노드의 인덱스는 0 ~ numItems -1 사이에 있지만 더미 헤드를 찾는 경우에도 지원하기 위해 k = -1이면 더미 헤드를 찾는 것으로 해석한다. 첫 번째 노드는 0번째 노드로 표기하고, 더미 헤드 노드는 -1번째 노드로 표기한다. public T getNode(int k){ if(k >= -..
-
JAVA 자료구조 (리스트) - LinkedList 2 (원소 삽입, 원소 삭제)CS지식/자료구조 2024. 1. 3. 12:12
연결리스트 2. 연결 리스트의 작업 원소 삽입 연결 리스트에서 중간 노드를 삽입하려면 삽입 노드의 바로 앞에 노드, 즉 직전 노드를 가리키는 레퍼런스preNode가 있어야 한다. [그림 5-15]의 예를 살펴보자 (a)와 같이 연결 리스트에서 원소 17과 35 사이에 원소 25를 삽입하려면 레퍼런스 preNode가 원소 25를 담고 있는 노드를 가리키도록 준비한다. 그런 다음 (b)와 같이 원소 17과 35노드 사이에 원소 25의 새 노드를 삽입한다. 이 작업을 위한 알고리즘은 다음과 같다. x는 삽입할 원소다. newNode.item = x newNode.next = preNode.next prevNode.next = newNode numItems++ 여기서 prevNode.next는 원소 35의 노드..
-
알고리즘 (정렬) - 고급 정렬 알고리즘(Quick Sort)2CS지식/알고리즘 2024. 1. 2. 16:41
고급 정렬 알고리즘 퀵 정렬(Quick Sort) 퀵 정렬은 평균적으로 가장 좋은 성능을 가져 현장에서 가장 많이 쓰는 정렬 알고리즘이다. 우선 [그림 4-6]을 예로 들어 설명을 시작한다. 첫째 줄에 정렬해야 할 원소가 10개인 배열이 주어졌다. 아무원소나 기준 원소로 삼아도 상관이 없는데 여기서는 맨 오른ㅉ고에 있는 원소 15를 기준 원소로 삼는다. (a)에서는 기준원소인 15를 중심으로 이보다 작은 원소들은 15의 왼쪽에, 나머지 원소들은 15의 오른쪽에 재배치한다. 이 결과 8,11,3은 왼쪽에, 31,48,20,29,65,73은 15의 오른쪽에 오도록 재배치되었다. (b)에서 왼쪽의 원소 3개와 오른쪽의 원소 6개를 각각 독립적으로 정렬한다. 왼쪽3개의 원소를 정렬할 때 15의 자리는 영향을 받..
-
알고리즘 (정렬) - 고급 정렬 알고리즘(Merge Sort)1CS지식/알고리즘 2024. 1. 2. 11:27
고급 정렬 알고리즘 선택정렬, 버블정렬, 삽입정렬 과 같은 기본 알고리즘은 모두 평균 ϴ(n²)의 시간이 소요된다. 하지만 앞으로 게시물에서 다룰 고급 정렬 알고리즘은 모두 평균 ϴ(n log n)의 시간이 소요된다. 병합 정렬, 퀵 정렬, 힙 정렬을 소개하는데 회악의 경우에도 병합 정령과 힙정렬은 ϴ(nlogn)이 소요되고, 퀵 정렬 ϴ(n²)이 소요된다. 이 중 퀵 정렬은 최악의 경우 때문에 성능이 가장 나빠 보일 수도 있으나 평균 성능은 어떤 정렬에도 뒤 떠러지지 않아 실무에서 가장 많이 사용된다. 병합 정렬(Merge Sort) 병합 정렬은 먼저 입력을 반으로 나눈다. 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다...
-
알고리즘 (정렬) - 기본적인 정렬 알고리즘(Bubble Sort,Insert Sort)CS지식/알고리즘 2023. 12. 29. 10:15
알고리즘 1. 버블 정렬(Bubble sort) 버블 정렬도 선택 정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복한다. 다만 제일 큰 원소를 오른쪽으로 옮기는 방법이 다를 뿐이다. 알고리즘 4-2 버블정렬 public int [] bubbleSort(int []A){ int temp = 0; int n = A.length; for(int i = 0; i A[j] ){ temp = A[j-1]; A[j-1] = A[j]; A[j] = temp; } if(j == n-1) n--; } } return A; } 알고리즘은 크게 두 개의 for 루프로 구성이 되어 있다. 첫 번째 for루프, 즉 1️⃣..
-
JAVA 자료구조 (리스트) - 배열리스트 2CS지식/자료구조 2023. 12. 28. 16:25
배열 리스트 2 2. 배열 리스트의 작업 원소 삭제 리스트에서 원소를 삭제할 때는 특정 위치의 원소를 삭제하게 할 수도 있고, 특정 원소를 삭제하게 할 수도 있다. [그림 5-11]은 리스트의 3번째 원소를 삭제하는 예다. 리스트에 총 9개의 원소가 저장되어 있어 변수 numItems 값은 9인 상태다. 3번째 원소인 17을 삭제하고 4~8번째 원소들을 왼쪽으로 시프트 한다. 알고리즘 5-3 배열 리스트의 k번째 원소 삭제하기 void remove(int k){ if(isEmpty() || k numItems-1) /* 에러처리 */ else{ for(int i = k; i < numItems-2l i++ item[i] = item[i+1]; // ◀ 왼쪽으로 시프트 numItems-..
-
JAVA 자료구조(리스트) - 배열리스트 1CS지식/자료구조 2023. 12. 27. 16:00
배열리스트 1. 배열 리스트의 객체 구조 [그림 5-5]에서 위쪽은 배열을 보는 물리적 관점이고, 아래쪽은 리스트를 보는 추상적 관점이다. 배열 item[0...] 에 원소들이 들어가 있다. ADT리스트 관점은 하부 구조를 특정하지 않는다. ADT에서 리스트는 원소를 리스트의 0번째 원소, 6번째 원소, 마지막 원소와 같이 추상적으로 본다. 배열을 이용해 리스트를 구현한다는 것은 이 추상적 관점을 물리적 배열에 대응시켜 주는 것이다. 예를 들어, 리스트의 0번째 원소를 배열의 item[0]에 대응시킨다. 마찬가지로 리스트 i번째 원소는 배열의 item[i]에 대응된다. 추상적 관점을 물리적으로 대응시킬 때 [그림 5-6]과 같이 배열을 역순으로 해석할 수도 있다. 배열로 구현한 리스트에 원소를 삽입하거나..
-
JAVA 자료구조 (리스트) - 리스트란CS지식/자료구조 2023. 12. 27. 13:57
리스트란 생활 속의 리스트 리스트는 대표적인 자료구조 중 하나로 자료구조&알고리즘을 공부하다 보면 아주 흔하게 만나게 될 것이다. 리스트는 '줄 세워져 있는 데이터 ' 또는 '죽 늘어선 데이터'를 의미한다. 리스트의 예는 풍부하다. 정수 리스트, 어떤 그룹에 속하는 사람 리스트, 서비스를 기다리는 사람 리스트, 선물 받고 싶은 목록을 적은 위시 리스트, 위험한 사람들을 적은 블랙 리스트, 선물 보낼 사람들 리스트 등 끝없이 예를 들 수 있다. 리스트의 작업 리스트를 관리하기 위해 필요한 작업을 생각해보자. 우선, 리스트에 새 원소를 삽입할 일이 많을 것이다. 이때 1)원소를 리스트의 맨 뒤에 넣을지 맨 앞에 넣을지 중간 어디쯤 넣을지 알려줘야 할 것이다. 또한 2)리스트에서 원소를 삭제할 때는 어디에 있..