정렬알고리즘3

• 

  이진 탐색 (Binary Search) 탐색의 방법은 크게 두가지가 있는데, 선형 탐색과 이진 탐색이 있습니다.그 중 이진 탐색 방법에 대해 작성을 해봤습니다.  이진 탐색(Binary Search)- 정렬된 상태에서 사용할 수 있습니다.배열의 정 중앙값을 선택해 그 값보다 작으면 왼쪽 배열, 크면 오른쪽 배열에서 재귀를 돌려 결국 원하는 값을 탐색할 때 사용하는 방법입니다. ex) int[] arr = {1,2,3,4,5,6,7,8,9} 에서 이진 탐색으로 숫자 6을 찾아라.1) 중앙값인 5보다 원하는 값이 크기 때문에 우측 배열을 재귀로 돌아야 합니다. {6,7,8,9}2) 중앙값인 7보다 원하는 값이 작으니 좌측 배열을 재귀로 돌아야 합니다. {6}3) 중앙값인 6과 원하는 값인 6이 일치하기 때문에 종료된다.3번째 만에 원하는 값을 탐.. CS 지식/자료구조_알고리즘 2025. 1. 13.

• 

  힙 정렬(Heap Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort) 이번에는 정렬 중에서도 시간 복잡도가 조금 더 빠른 정렬들을 가지고 왔습니다. 힙 정렬, 병합 정렬, 퀵 정렬이렇게 총 3가지 정렬을 설명 드리겠습니다. 힙 정렬(Heap Sort)- 아래의 링크에 있는 힙에 대해 공부하고 오면 이해하기 매우 편하십니다.https://naknak.tistory.com/123 힙(Heap)과 이진탐색트리(Binary Search Tree)힙(Heap)- 트리구조 중 하나로 우선순위 큐를 구현할 때 사용됩니다. (다익스트라에서도 사용됨.)- 우선순위 큐의 특징 : 데이터를 자유롭게 추가 가능, 꺼낼 때는 가장 작은 데이터를 꺼냅니다. -naknak.tistory.com  - 힙은 트리 형태의 구조로, 우선순위 큐를 구현하는데 주로 사용됩니다.- 보통의 힙은 꺼낼 때 가장 작.. CS 지식/자료구조_알고리즘 2025. 1. 12.

• 

  버블 정렬(Bubble Sort) vs 선택정렬(Selection Sort) vs 삽입정렬(Insertion Sort) 버블 정렬과 선택정렬, 그리고 삽입정렬은 정렬 중 가장 기초적인 정렬들 입니다.우선 버블 정렬부터 살펴보겠습니다. 버블 정렬(Bubble Sort)- 오른쪽에서 정렬을 시작하여 왼쪽으로 가며, 본인의 값이 왼쪽의 값보다 작을 경우 위치를 변경해주는 정렬입니다.- 한 사이클이 지나면 맨 왼쪽의 값은 항상 가장 작은 값이 됩니다. 따라서 다음 사이클은 맨 좌측 값 하나를 제외하고 돌립니다. ex) int[] arr = { 3, 2, 1 }이고, 버블 정렬을 통해 정렬하라고 하면,1) 2와 1을 비교합니다. 2가 더 크므로 둘의 위치를 교체해줍니다. => {3, 1, 2}2) 3과 1을 비교합니다. 3이 더 크므로 둘의 위치를 교체해줍니다. => {1, 3, 2}3) 3과 2를 비교합니다. 3이 더 크므로 둘.. CS 지식/자료구조_알고리즘 2025. 1. 11.