Binary Search 이진 탐색(binary search)은 정렬된 데이터 집합을 이분화하면서 탐색하는 방법이다. 예를들어 비유하면, 가나다순으로 정렬되어 있는 전화번호부에서 임의의 사람에 대한 전화번호를 찾는 경우다. ① 중간에 위치한 데이터인 11과 찾고자 하는 15가 같은지 비교한다. ② 중간에 위치한 데이터인 11보다 찾고자 하는 데이터인 15가 크므로 중간 데이터 11의 오른쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다. ③ 탐색 영역의 중간에 위치한 데이터인 17과 찾고자 하는 15가 같은지 비교한다. ④ 중간에 위치한 데이터인 17보다 찾고자 하는 데이터인 15가 작으므로 중간 데이터 17 왼쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다. ⑤ 탐색 영역의 중간에 위치한 데이터인 15와 찾고자 하는 15가 .. 2023. 2. 22. Linear Search (선형 탐색) 선형 탐색(linear search)은 순차 탐색(sequential search)이라고도 하는데, 주어진 데이터 집합에서 원하는 데이터를 처음부터 순차적으로 비교하면서 찾는 방법이다. 예를 들어 비유하면, 무작위로 모여진 명함 중에서 원하는 사람의 명함을 찾는 경우를 들 수 있다. ① 첫 번째 데이터인 15와 찾고자 하는 3이 같은지 비교하는데, 다르므로 다음으로 이동한다. ② 두 번째 데이터인 11과 찾고자 하는 3이 같은지 비교하는데, 다르므로 다음으로 이동한다. ③ 세 번째 데이터인 1과 찾고자 하는 3이 같은지 비교하는데, 다르므로 다음으로 이동한다. ④ 네 번째 데이터인 3과 찾고자 하는 3이 같은지 비교하는데, 같으므로 원하는 데이터를 찾고 탐색을 종료한다. 만약 마지막까지 원하는 데이터를 .. 2023. 2. 19. Bubble Sort (버블 정렬) 버블 정렬(bubble sort)은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식이다. ① 첫 번째 데이터인 15와 두 번째 데이터인 11을 비교해 큰 데이터를 뒤로 위치시킨다. 15가 크므로 둘의 위치를 바꾼다. ② 두 번째 데이터인 15와 세 번째 데이터인 1을 비교하는데, 앞에 위치한 15가 크므로 둘의 위치를 바꾼다. ③ 마찬가지 방식을 적용해 세 번째 데이터인 15와 네 번째 데이터인 3의 위치를 바꾼다. ④ 마찬가지 방식을 적용해 네 번째 데이터인 15와 마지막 데이터인 8의 위치를 바꾼다. 가장 큰 데이터인 15가 가장 뒤에 위치하게 된다. ⑤ 처음부터 다시 시작한다. 첫 번째 데이터인 11과 두 번째 데이터인 1의 크기를 비교하는데 앞에 위치한 11이 크.. 2023. 2. 15. Selection Sort (선택 정렬) 선택 정렬(selection sort)은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다. ① 가장 작은 데이터인 1을 가장 앞에 위치한 15와 교환한다. 가장 작은 데이터가 가장 앞에 위치하게 된다. ② 첫 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 3을 두 번째 데이터인 11과 교환한다. ③ 첫 번째, 두 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 8을 세 번째 데이터인 15와 교환한다. ④ 첫 번째, 두 번째, 세 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 11을 네 번째 데이터인 11과 교환한다. 같은 데이터이므로 위치의 변화는 없다. ⑤ 데이터들에 대한 정렬이 완료된다. JAVA Code int in.. 2023. 2. 14. Big-O Notation (점근 표기법) 1. Big-O Notation(점근 표기법)이란? 알고리즘의 시간 복잡도를 나타내는 방법에는 여러 가지가 있다. 그들 중 현재 가장 널리 쓰이는 표기법이다. 점근 표기법은 큰 수의 법칙을 적용하여 트랙잭션의 최악의 경우를 택하여 시간 복잡도를 표현한다. 'f = 5n+8', 'g = 2n' 이라면, n이 ∞로 갈 때, 이 둘은 수렴하므로 O(n)로 같은 취급을 하는 것이다. 가장 보편화된 방법이지만 이론적인 느낌이 강하기 때문에, 본인의 데이터에 따라 시간 복잡도를 따져볼 필요가 있다. 2. 자료구조별 트랜잭션 시간 복잡도 3. 정렬 알고리즘 시간 복잡도 2023. 2. 13. 이전 1 다음 반응형
