본문 바로가기

분류 전체보기20

이진 탐색(Binary Search) 이란 ? 이진 탐색 ? 이진탐색은 정렬되어 있는 리스트에서 특정한 데이터를 빠르게 탐색하는 알고리즘 순차 탐색(Sequential Search) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 가장 기본적인 형태의 데이터 탐색 알고리즘 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소의 데이터를 확인해 가며 탐색한다. 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이다 이진 탐색(Binary Search) 기본적으로 리스트 데이터가 정렬되어 있어야 사용할 수 있는 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는것이 특징이다. 이진 탐색은 한 번 확인할 때마다 확인할 원소의 개수가 절반씩 줄어든.. 2023. 6. 14.
계수 정렬(Counting sort) 계수 정렬(Counting sort) 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작 정렬 알고리즘 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다. 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장한다. 계수 정렬 동작 정렬할 데이터: [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] 1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다 2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가 시킨다. 3. 2번의 과정을 모든 데이터에 대해서 반복 한다. 4. 최종적으로 인덱스 별 카운트를 구한다. 원.. 2023. 6. 14.
퀵 정렬 (Quick sort) 퀵정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정 한다. 퀵 정렬이 빠른 이유 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(N㏒N)를 기대할 수 있습니다. 너비 X 높이 = N * ㏒N = N㏒N 퀵 정렬의 시간 복잡도 퀵 정렬은 평균의 경우 O(N㏒N)의 시간 복잡도를 가집니다. 최악의 경우 O(N²)의 시간 복잡도를 가집니다. array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(arr.. 2023. 6. 13.
컬렉션 프레임워크란(Collection Framework)? Collection Framework ? 컬렉션 프레임워크(collection framework)란 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합을 의미한다. 데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현 해놓은 것이다. JDK 1.2 이전까지는 Vector, Hashtable, Properties와 같은 컬렉션 클래스들을 서로 각자 다른 방식으로 처리해야 했으나 JDK 1.2부터 컬렉션 프레임 워크가 등장하면서 다양한 종류의 컬렉션 클래스가 추가되고 모든 컬렉션 클래스를 표준화된 방식으로 다룰 수 있도록 체계화되었다. 컬렉션 프레임워크 주요 인터페이스 데이터를 저장하는 자료 구조에 따라 핵심 인터페이스를 정의하고 있다. Li.. 2023. 6. 13.

티스토리툴바