🌈 백엔드/자료구조 썸네일형 리스트형 자료구조_정렬 ③ 삽입정렬 [1] 삽입정렬 (1) 삽입정렬 개념 카드정렬 insertion 정렬 기존의 정렬된 데이터에 새로운 데이터가 삽입될때 정렬된 데이터들과 삽입할 데이터를 비교하여 데이터가 삽입될 위치를 찾아서 정렬하는 방식 (2) 삽입정렬 과정 주어진 정렬을 오름차순으로 정렬한다 . 삽입정렬 방법을 사용한다 첫번째 쓰루패스에서 정렬에서 삭제하고 임시공간으로 이동한다 8과 임의공간 4 를 비교했을때 8이 더 크면 8을 빈공간으로 오른쪽으로 시프트 한다 임의공간에 있는 4를 빈공간을 삽입한다 두번째 쓰루패스에서 인덱스 2를 삭제하고 임의공간으로 이동한다 8과 임의공간에 있는 2를 비교했을때 8이 더 크면 8을 빈공간으로 오른쪽으로 시프트하고 빈공간의 옆인 4가 임의공간의 2를 비교시 더 크면 4를 빈공간으로 오른쪽으로 시프트.. 더보기 자료구조_정렬 ② 버블정렬 [1] 버블정렬 (1) 버블정렬 개념 bubble 정렬 인접한 두 값의 대소 관계를 비교하여 오름차순이나 내림차순 형태로 값을 교환하여 정렬한다 각 인덱스 값을 비교하여 패스쓰루를 반복하기 때문에 시간복잡도가 크다 - 정렬되지 않은 배열이 주어졌을때 오름차순으로 정렬하기 - 정렬되지 않은 배열이 주어졌을때 중복 값을 찾기 - 정렬되지 않은 배열이 주어졌을때 최대값 찾기 - 단순 정렬 (2) 버블정렬 과정 1. 인덱스 1과 인덱스 2를 비교하여 인덱스1 > 인덱스 2 의 값이면 두 항목을 교환한다 인덱스1 < 인덱스 2 의 값이면 아무것도 하지 않는다 2. 인덱스 포인터를 +1 옮긴다 3. 인덱스 2 와 인덱스 3을 비교하여 .... 똑같은 작업을 반복한다 4. 인덱스 0부터 인덱스 마지막까지 비교 후 다.. 더보기 자료구조_정렬 ① 선택정렬 [1] 선택정렬 (1) 선택정렬 개념 selection 정렬 처음 데이터를 기준으로 하여 나머지 모든 데이터와 비교 후 가장 작은 값을 처음 기준이 되는 데이터 위치로 이동하는 과정을 반복하여 정렬함 1회전이 끝나면 두번째 데이터를 기준으로 모두 비교하여 최소값을 두번째 위치로 이동하는 과정을 반복함 (2) 선택정렬 과정 1번째 패스쓰루에서 최소값 찾기 + 그 최소값을 인덱스 0 위치에 넣기 2번째 패스쓰루에서 0인덱스를 제외한 나머지에서 최소값찾기 + 그 최소값을 인덱스 1 위치에 넣기 3번째 패스쓰루에서 0, 1 인덱스를 제외한 나머지에서 최소값찾기 + 그 최소값을 인덱스 2위치에 넣기 ... 마지막 패스쓰루에서 마지막 인덱스와 최소값이 동일할때 종료 (3) 시간복잡도 O(N⌒2) public cla.. 더보기 자료구조_비선형구조 ②그래프 [1] 그래프 개념 (1) 그래프 개념 객체를 나타내는 정점vertex과 객체를 연결하는 간선 edge로 구성된 집합이다 G = (V,E) [2] 그래프 종류 (1) 무방향 그래프 두 정점의 쌍에 순서가 없는 그래프 (v0,v1) 와 (v1,v0)이 동일하다 최대 간선의 수 = n(n-1) / 2 개이다 (n : 정점의 수) (2) 방향 그래프 간선을 표현하는 두 정점의 쌍에 순서가 있는 그래프 (vj,vk) 와 (vk,vj)가 다른 그래프 최대 간선의 수 = n(n-1) 개이다 (n : 정점의 수) (3) 신장트리 spanning tree n개의 정점으로 이루어진 무방향 그래프 에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리 최소비용 신장트리 알고리즘 kruskal 알고리즘 : 가중치가 높은.. 더보기 자료구조_비선형구조 ① 트리 - 트리셋 TreeSet [1] TreeSet (1) Tree Set 특징 중복 허용 안됨 정렬된 순서에 의해 반복 TreeMap을 이용하여 구현된 형태이다 인덱스 위치를 통해 저장과 접근을 하는것이 아닌 key를 이용하고 싶을 경우 사용한다 저장되는 데이터의 갯수가 몇개인지 예상되지 않는 경우 사용한다 정렬된 값이 필요할때 사용한다 삽입 삭제가 빈번하지 않을때 사용한다 객체의 정렬에 사용하는 클래스 Set 인터페이스를 구현하여 중복을 허용하지 않고, 오름차순이나 내림차순으로 객체를 정렬할 수 있음 내부적으로 이진검색트리(binary search tree)로 구현됨 이진검색트리에 저장하기 위해 각 객체를 비교해야 함 비교 대상이 되는 객체에 Comparable이나 Comparator 인터페이스를 구현 해야 TreeSet에 추가 .. 더보기 자료구조_비선형구조 ① 트리 - 트리맵 TreeMap Map 인터페이스를 구현한 클래스이고 key에 대한 정렬을 구현할 수 있음 key가 되는 클래스에 Comparable이나 Comparator인터페이스를 구현함으로써 key-value 쌍의 자료를 key값 기준으로 정렬하여 관리 할 수 있음 더보기 자료구조_비선형구조 ① 트리 - 힙트리 HeapTree (1)힙트리 Heap tree 정렬에 사용되느 이진트리 항상 전이진 트리를 구성 중복된 값을 허용 힙은 최대값,최소값 검색을 위한 구조 Max heap 최대 힙 : 부모 노드 키 > 자식 노드 키 Min heap 최소 힙 : 부모 노드 키 < 자식 노드 키 우선순위 큐를 위하여 만들어진 자료구조 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 ※ 완전이진트리 : 노드 삽입 할 때부터 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 부모 노드의 값은 자식 노드의 값보다 큰 상태를 유지한다 추가하기 왼쪽 하단부부터 노드가 채워지는 형태 노드가 채워진다면 숫자 순서대로 채워진다 추가한다면 마지막 노드를 생성하고 부모 노드가 자신보다 클때까지 부모로 올라간다. 삭제하기 상단 데이터 삭제시 하단.. 더보기 자료구조_비선형구조 ① 트리 - 이진 탐색 트리 [1] 이진검색트리 (1) 이진트리 binary tree 부모노드에 자식노드가 두 개 이하인 트리 컴퓨터 응용에서 가장 많이 사용한다 모든 노드가 최대 2개의 서브 트리를 가진다 왼쪽 서브 트리와 오른쪽 서브 트리로 구분한다 편향 이진트리 , 포화 이진트리 , 완전 이진트리가 있다 (2) 이진 검색 트리 binary search tree [23,10,48,15,7,22,56] 순으로 자료를 넣은 트리 임의의 키를 가진 원소를 삽입, 삭제, 검색하는데 효율적인 자료구조 모든 연산은 키값을 기준으로 수행 검색을 중심으로 만들어진 트리 자료(key)의 중복을 허용하지 않음 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가짐 자료를 검색에 걸리는 시간이 평균 log(n) .. 더보기 이전 1 2 3 4 다음 목록 더보기
