홍시홍의 프로그래밍

1. 버킷 정렬 버킷 정렬 또는 버킷 소트(bucket sort)는 수많은 버킷에 배열 요소들을 분산시킴으로써 동작하는 정렬 알고리즘이다. 각 버킷은 그 뒤로 개별 정렬되는데, 이는 다른 정렬 알고리즘을 사용하거나 버킷 정렬 알고리즘을 반복 적용시켜 수행한다. 버킷의 정렬은 다음과 같이 이루어진다: 처음에 비어있는 버킷들의 배열을 배치한다. 분산: 원래의 배열을 살펴보고 각 객체를 버킷에 담는다. 비어있지 않은 각 버킷을 정렬한다. 수집: 순서대로 버킷을 방문하여 모든 요소를 원래의 배열에 위치시켜 놓는다. 내 해석 : 농작물을 분류할때 크기 별로 분류하듯이 첫번재 버킷에 크기 별로 분류하여 정렬하는 알고리즘 출처 : https://ko.wikipedia.org/wiki/%EB%B2%84%ED%82%B7..

1. 정의 컴퓨터 과학 분야 에서 서로소 집합(disjoint-set) 자료 구조, 또는 합집합-찾기(union–find) 자료 구조, 병합-찾기 집합(merge–find set)은 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다. 출처 : 위키피디아 내 해석 : 묶음으로 되어있지 않은 집합을 찾아내는 것, 사이클이 없음 한 노드의 부모를 찾거나 두 노드가 한 집합이 되도록 합치거나. 2. 구현 1) find(x) : x의 부모를 찾는 함수 - 경로 압축 : 시간 복잡도 상수 복잡도를 가진다고 함. 2) Union(a,b) : a와 b를 연결하는 함수(한 쪽으로 연결시켜줌) - 한 쪽으로 연결 시켜주는것이 헷갈리지 않음 ( 작은 쪽 or 큰 쪽) 3. 시간 복잡도 ..

1. 버블 정렬 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 출처 - 위키피디아(https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC) 나의 해석 : 현재 인덱스와 다음 인덱스를 비교해서 현재 인덱스가 크다면 한칸씩 교환해준다. 요구 사항 1. 배열 오름차순으로 구현 풀이 방법 전체 인덱스를 n번 연산하여 정렬한다. 1. 0~n번 인덱스까지 서로 인접한 인덱스 비교한다. 1.1 첫번째 정렬에서 제일 큰 인덱스 n번째 인덱스로 이동 1.2 두번째 정렬에서 2번째 큰 인덱스 n-1번째 인덱스로 이동 2. 1번을 n번 반족 시간 복잡도 1번째에서 n-1번 비교 2번째에서 n-2번 비교 n번째에서 1번 비교..

1. 삽입 정렬 삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 출처 - 위키피디아(https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC) 나의 해석 : 현재 인덱스를 시작으로 인덱스 -1 자리에서 부터 0번 인덱스까지 비교하여 key 값의 자리를 찾아주어 정렬한다. 요구 사항 1. 배열 오름차순으로 구현 풀이 방법 제일 앞 인덱스부터 하나 하나 탐색한다. 1. 비교 인덱스가 큰거라면 앞으로 이동(오른쪽) 2. 비교 인덱스가 작다면 스톱(현재 인덱스의 위치 찾음) 3. 2의 자리와 현재 인덱스..