시간복잡도4

• 

  힙 정렬(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.

• 

  힙(Heap)과 이진탐색트리(Binary Search Tree) 힙(Heap)- 트리구조 중 하나로 우선순위 큐를 구현할 때 사용됩니다. (다익스트라에서도 사용됨.)- 우선순위 큐의 특징 : 데이터를 자유롭게 추가 가능, 꺼낼 때는 가장 작은 데이터를 꺼냅니다. - 힙은 노드들로 구성되어 있습니다.각각의 노드들은 부모와 자식으로 이루어져 있고, 부모는 최대 2개의 자식 노드를 가질 수 있습니다.- 부모 노드의 데이터가 자식 노드의 데이터보다 항상 작아야합니다. ex) 새로운 수를 힙에 추가하는 예시.1) 새로운 숫자를 힙의 가장 끝에 추가합니다.2) 만약 부모 노드가 존재한다면, 부모 노드와 데이터를 비교 후 숫자가 더 작다면 그 둘의 위치를 바꿔줍니다.3) 계속 그렇게 해서, 더 이상 부모보다 작지 않을 경우, 정렬은 종료됩니다. ex) 숫자를 하나 꺼낼때의 예시... CS 지식/자료구조_알고리즘 2025. 1. 9.

• 

  List(리스트)와 Array(배열) List(리스트)- 리스트는 데이터를 일직선으로 줄줄이 정렬한 데이터 구조입니다.장점 : 데이터의 추가, 삭제 쉬움단점 : 데이터 조회 느림 - 데이터들은 각각 포인터를 가지고, 이 포인터는 각각 데이터의 다음 데이터의 메모리 주소를 가리킵니다. - 리스트는 포인터를 이용하므로 메모리상에서 연결된 위치에 있을 필요가 없습니다. 따라서 분산되어 배치됩니다. - 데이터 추가 방법A와 B 데이터 사이에 C라는 데이터를 추가할 때, A의 포인터가 C의 메모리 주소를 가리키게 하고,C의 포인터가 B의 메모리 주소를 가리키게 하면 끝이다. - 데이터 삭제 방법A와 B와 C가 연결되어 있을 때, B를 제거하고자 한다.A의 포인터를 C의 메모리주소를 가리키면 해결된다. 따라서 List에서의 시간복잡도는 다음과 같다.데.. CS 지식/자료구조_알고리즘 2025. 1. 7.