자료구조 & 알고리즘 (3) 썸네일형 리스트형 [알고리즘] 이진 탐색(Binary Search) 알고리즘 이진 검색 알고리즘(binary search algorithm)오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 됨단점 : 검색 원리상 정렬된 리스트에만 사용할 수 있음 (오름차순 정렬)장점 : 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠름 즉, 무언가 찾고자하는 것이 있을 때 사용하는 알고리즘임 자바로 구현 방법1. 반복문으로 구현 // 반복문 구조 public static int binarySearch(int arr[], int target).. [자료구조] 비선형 자료구조 : 우선순위 큐 - 연습문제 연습문제1. 정수로 이뤄진 배열 중 k번째로 큰 정수 찾아내기 정수로 이뤄진 배열 numbers에서, k번째로 큰 정수를 찾아내기. 방법1. 우선순위 큐를 통하여 우선적으로 큰 수부터 출력 후에 k번째 출력을 찾아내기 minHeap으로 풀어주기 이렇게 위에서부터 아래로 내려가면서 오름차순으로 정리된 힙 구조를 Min-Heap이라고 함 PriorityQueue -> Min Heap 구조를 바탕으로 함 poll() : 큐에서 가장 상단에 있는 것을 출력, 우선순위 큐에서는 우선순위로 되어있는 것부터 출력 peek() : 가장 상단에 있는 것 출력(여기서는 부모노드 출력) public class Practice1 { public static int solution1(int[] nums, int k) { Pri.. [자료구조] 비선형 자료구조 : 우선순위 큐 우선순위 큐(Priority Queue) 일반적인 큐(Queue) : FIFO(First In, First Out)의 형식, 먼저 들어온 것이 먼저 나가는 형식의 자료구조 우선순위 큐(Priority Queue) : 우선순위가 존재하며, 우선순위가 높은 것 부터 나가고, 동일한 우선순위에서는 FIFO의 형식의 자료구조 우선순위 큐 구현에 자주 사용: 배열, 연결리스트, 힙(Heap) 복잡도 측면에서 힙(Heap)을 자주 사용함 Queue에서의 함수 - enqueue() : 데이터를 입력하는 함수 - dequeue() : 데이터를 출력하는 함수 java에서 우선순위 큐를 구현 // 비선형 자료구조 - 우선순위 큐 // 연결 리스트를 이용한 우선순위 큐 // 자바 기본 PriorityQueue import .. 이전 1 다음
