나다김강니

최소 신장 트리신장 트리 : 그래프의 모든 정점을 포함하는 트리최소 신장 트리 : 가중치가 있는 그래프에서 간선의 가중치 총합이 가장 작은 신장 트리  프림 알고리즘(Prim algorithm) - 정점 기준그리디 알고리즘으로, 임의의 정점을 시작점으로 트리를 확장하면서 최소 신장 트리를 생성하는 방식이다. 💡 프림 알고리즘 과정시작점부터 뻗어 나가는 간선 중 가장 작은 가중치를 가진 노드로 연결한다.시작점과 연결한 노드에서 뻗어 나가는 간선 중 가장 작은 가중치를 가진 노드로 연결한다.반복한다.  크루스칼 알고리즘(Kruskal algorithm) - 간선 기준그리디 알고리즘으로, 간선을 오름차순으로 정렬한 뒤 가중치가 낮은 간선을 선택하면서 최소 신장 트리를 생성한다. 💡 크루스칼 알고리즘 과정..

버블 정렬(bubble sort)양옆에 위치한 두 값을 비교하면서 크기 순으로 정렬한다. ⏰ 시간 복잡도 계산배열의 n번째 요소(마지막 요소)를 정렬하는 데 n-1번 비교한다.배열의 n-1번째 요소를 정렬하는 데 n-2번 비교한다.=> (n-1)+(n-2)+(n-3)+ ··· + 2 + 1 = n(n-1) / 2 시간 복잡도 : O(n2)   선택 정렬(selection sort)배열을 순회하면서 배열의 앞에서부터 차례대로 각 인덱스에 들어갈 값을 선택해 위치시킨다.예) 오름차순 : 배열의 첫번째 자리에 최솟값, 두번째 자리에 최솟값 다음으로 작은 값 ⏰ 시간 복잡도 계산(오름차순)배열의 첫 번째 요소를 찾는데 n-1번 비교한다.배열의 두 번째 요소를 찾는데 n-2번 비교한다.=> (n-1)+(n-2)+..

선형 자료구조선형 자료구조는 연속적으로 데이터가 나열되는 자료구조를 나타낸다. 배열(array)정해진 크기만큼 데이터가 일렬로 저장되는 정적 자료구조 🔍 용어   요소(element)각각의 데이터   인덱스(index)데이터를 가리키는 번호  🔍 연산   연산설명시간복잡도   접근특정 인덱스에 접근O(1)   검색데이터를 검색O(n)   삽입특정 위치에 데이터 삽입O(n)   삭제데이터 삭제O(n)  연결 리스트(linked list)대표적인 선형 자료구조의 하나로 배열과 달리 크기가 정해져 있지 않은 동적 자료구조이다. 🔍 용어   노드(node)데이터와 다음 노드가 저장된 주소값을 가짐   헤드(head) 포인터첫 번째 노드를 가리킨다.   테일(tail) 포인터마지막 노드를 가리킨다.  🔍 ..