Study Blog

지난 글에서 퀵 정렬에 대해 살펴보았다.https://vibeee.tistory.com/47 [정렬 알고리즘] 퀵 정렬퀵 정렬이란? - 일반적으로 사용되는 아주 빠른(quick) 정렬 알고리즘 - Charles A. R Hoare에 의해 고안됨 - 중심 축이 되는 값(피벗)을 선택하여 그룹을 나누어가는 방법 - 재귀적으로 호출하여 진행하vibeee.tistory.com 퀵 정렬에서의 피벗퀵 정렬의 경우 피벗을 선택하는 방법에 따라 성능이 달라지기 때문에 결국 피벗을 선택하는 방법이 성능을 좌우한다고 볼 수 있다. 아래 예시를 통해 피벗을 선택하는 예시를 살펴보자.먼저 위와 같은 배열이 있을 때, 맨 앞 원소(8)를 선택한다고 해보자.만약 8이 피벗으로 선택된다면, 0~7과 8이 있는 두 가지 그룹으로 나..

퀵 정렬이란?- 일반적으로 사용되는 아주 빠른(quick) 정렬 알고리즘- Charles A. R Hoare에 의해 고안됨- 중심 축이 되는 값(피벗)을 선택하여 그룹을 나누어가는 방법- 재귀적으로 호출하여 진행하는 것이 기본적인 형태 퀵 정렬은 아래와 같이 진행된다.먼저 키가 168cm인 학생 A를 선택해서 피벗으로 삼고 이 학생을 기준으로 168cm 미만인 그룹과 168cm 이상인 그룹으로 나누고, 이 과정을 반복해서 피벗을 선택하여 나누기를 반복하여 모든 그룹이 1명씩 남으면 정렬이 완료된다. 피벗은 다른 말로 중심축이라고도 하는데, 임의로 선택할 수 있고, 선택된 피벗은 2개로 나눈 그룹 어디에 넣어도 상관이 없다. 배열을 두 그룹으로 나누기1) 피벗, pl(왼쪽 커서), pr(오른쪽 커서) 선택..

https://vibeee.tistory.com/284 검색 알고리즘 - 해시법해시법해시법을 이용하면 검색과 더불어 데이터의 추가·삭제도 효율적으로 수행할 수 있다.해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다. 원소 갯수가 13vibeee.tistory.com 지난 포스팅에서 소개했던 것처럼 해시 충돌이 발생할 때 해결하는 방법으로 체인법 외 오픈주소법이 있다.오픈 주소법오픈 주소법은 충돌이 발생했을 때 재해시(rehashing)를 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시법(closed hashing)이라고도 한다. 원소 추가하기아래 그림은 18을 추가하는 과정에서 충돌이 발생하는 상태를 보여준다. 이럴 때 재해시를 수행할 수 있다. 재해시를 위한 해시 함수..

해시법해시법을 이용하면 검색과 더불어 데이터의 추가·삭제도 효율적으로 수행할 수 있다.해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다. 원소 갯수가 13인 경우 키를 원소 갯수에 나누면 아래와 같이 해시값을 구할 수 있다. 위 표에서 해시값 부분에서 새로 원소를 구해 저장한 배열을 해시 테이블이라고 하며, 해시 테이블은 아래와 같이 구해지게 된다. 이와 같이 키를 해시값으로 변환하는 과정을 해시 함수라고 하며, 일반적으로 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용한다.해시 테이블에서 만들어진 원소를 버킷(Bucket)이라고 한다.(위 그림에서 0~12의 인덱스를 가진 배열) 해시 충돌위 해시 테이블에 18이라는 값을 추가하려고 할 때, 18을..

이진 검색 알고리즘을 사용하기 위한 조건→ 배열의 데이터가 정렬되어 있어야 한다.이 조건을 만족한다면 이진 검색은 선형 검색보다 빠르게 검색할 수 있다. 따라서 이진 검색은 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘이다. 이진 검색 알고리즘의 작동 원리검색 범위의 맨 앞, 맨 끝, 중앙의 인덱스를 각각 pl, pr, pc라고 칭하고,검색을 시작할 때 pl은 0, pr은 n - 1, pc는 (n - 1) // 2로 초기화한다.(pl은 배열의 맨 앞, pr은 배열의 맨 끝, pc는 배열의 중간의 인덱스를 잡아줘야 하기 때문) 1. a[pc] a[pl]~a[pc]는 key보다 작은 것이 분명하므로 검색 대상에서 제외한다.검색 범위는 중앙 원소 a[pc]보다 뒤쪽..