반응형 🌈 백엔드/자료구조31 자료구조_검색 ② 이진검색 [1] 이진검색 (1) 이진검색 개요 제어검색의 종류 이진검색 = 이분검색 자료들 중 중간에 위치한 항목을 키 값과 비교하여 다음 검색 위치를 결정하여 검색을 계속하는 방법 데이터의 반에 해당 위치를 찾아간다 성능 : 이진검색 < 피보나치검색 2023. 4. 16. 자료구조_검색 ① 순차검색 [1] 순차검색 (1) 순차검색 개요 일렬로 나열된 정렬되지 않은 자료를 처음부터 마지막까지 순서대로 검색하는 방법 검색기간이 길지만 정렬되어 있지 않아도됨 (2) 시간복잡도 O(N) 2023. 4. 15. 자료구조_정렬 ⑦기수 정렬 [1] 기수 정렬 (1) 기수정렬 개념 Radix 정렬 버킷 정렬 자릿수의 값을 기준으로 정렬 사용되는 데이터 진법에 따라 버킷의 갯수가 달라짐 10진수는 10+1 =11개 버킷 8진수는 8+1 = 9개 버킷 (2) 삽입정렬 과정 세자리 정수로 구성된 데이터가 있으면 먼저 100의 자리의 값을 기준으로 버킷을 이용하여 정렬하고 결과를 10의 자리값을 기준으로 정렬하고 1의 자리값을 기준으로 정렬하여 정렬을 완료한다 (3) 시간복잡도 O(n) 2023. 4. 7. 자료구조_정렬 ⑥ 병합 정렬 [1] 병합 정렬 (1) 병합정렬 개념 merge 정렬 두개의 그룹을 하나의 그룹으로 병합하여 그룹 내를 정렬하는 방식 외부정렬 수행능력은 좋으나 데이터 크기보다 2배의 기억공간이 필요하다 (2) 시간복잡도 O(nlog2n) 2023. 4. 6. 자료구조_정렬 ⑤힙 정렬 [1] 힙 정렬 (1) 힙 정렬 개념 heap 정렬 정렬을 위한 목적으로 만든 힙 트리를 이용한 정렬 (2) 시간복잡도 O(nlog2n) 2023. 4. 6. 자료구조_정렬 ④ 퀵 정렬 [1] 퀵 정렬 (1) 퀵 정렬 개념 quick 정렬 가장 빠른 정렬 방법 분할 정복 정렬 방식 데이터 리스트 중 중간에 위치한 값을 피벗이라한다 피벗은 알고리즘에 따라 첫 값, 마지막 값, 중위수 값을 선택할수 있다 피벗 기준으로 왼쪽에서는 피벗보다 큰 값을 , 오른쪽에서는 피벗보다 작은 값을 찾아 교환하는 작업을 반복하여 정렬한다 (2) 퀵 정렬 과정 (3) 시간복잡도 O(nlogn) 최악이면 O(N⌒2) 가 나올수 있다 2023. 3. 10. 자료구조_정렬 ③ 삽입정렬 [1] 삽입정렬 (1) 삽입정렬 개념 카드정렬 insertion 정렬 기존의 정렬된 데이터에 새로운 데이터가 삽입될때 정렬된 데이터들과 삽입할 데이터를 비교하여 데이터가 삽입될 위치를 찾아서 정렬하는 방식 (2) 삽입정렬 과정 주어진 정렬을 오름차순으로 정렬한다 . 삽입정렬 방법을 사용한다 첫번째 쓰루패스에서 정렬에서 삭제하고 임시공간으로 이동한다 8과 임의공간 4 를 비교했을때 8이 더 크면 8을 빈공간으로 오른쪽으로 시프트 한다 임의공간에 있는 4를 빈공간을 삽입한다 두번째 쓰루패스에서 인덱스 2를 삭제하고 임의공간으로 이동한다 8과 임의공간에 있는 2를 비교했을때 8이 더 크면 8을 빈공간으로 오른쪽으로 시프트하고 빈공간의 옆인 4가 임의공간의 2를 비교시 더 크면 4를 빈공간으로 오른쪽으로 시프트.. 2023. 3. 9. 자료구조_정렬 ② 버블정렬 [1] 버블정렬 (1) 버블정렬 개념 bubble 정렬 인접한 두 값의 대소 관계를 비교하여 오름차순이나 내림차순 형태로 값을 교환하여 정렬한다 각 인덱스 값을 비교하여 패스쓰루를 반복하기 때문에 시간복잡도가 크다 - 정렬되지 않은 배열이 주어졌을때 오름차순으로 정렬하기 - 정렬되지 않은 배열이 주어졌을때 중복 값을 찾기 - 정렬되지 않은 배열이 주어졌을때 최대값 찾기 - 단순 정렬 (2) 버블정렬 과정 1. 인덱스 1과 인덱스 2를 비교하여 인덱스1 > 인덱스 2 의 값이면 두 항목을 교환한다 인덱스1 < 인덱스 2 의 값이면 아무것도 하지 않는다 2. 인덱스 포인터를 +1 옮긴다 3. 인덱스 2 와 인덱스 3을 비교하여 .... 똑같은 작업을 반복한다 4. 인덱스 0부터 인덱스 마지막까지 비교 후 다.. 2023. 3. 9. 자료구조_정렬 ① 선택정렬 [1] 선택정렬 (1) 선택정렬 개념 selection 정렬 처음 데이터를 기준으로 하여 나머지 모든 데이터와 비교 후 가장 작은 값을 처음 기준이 되는 데이터 위치로 이동하는 과정을 반복하여 정렬함 1회전이 끝나면 두번째 데이터를 기준으로 모두 비교하여 최소값을 두번째 위치로 이동하는 과정을 반복함 (2) 선택정렬 과정 1번째 패스쓰루에서 최소값 찾기 + 그 최소값을 인덱스 0 위치에 넣기 2번째 패스쓰루에서 0인덱스를 제외한 나머지에서 최소값찾기 + 그 최소값을 인덱스 1 위치에 넣기 3번째 패스쓰루에서 0, 1 인덱스를 제외한 나머지에서 최소값찾기 + 그 최소값을 인덱스 2위치에 넣기 ... 마지막 패스쓰루에서 마지막 인덱스와 최소값이 동일할때 종료 (3) 시간복잡도 O(N⌒2) public cla.. 2023. 3. 9. 자료구조_비선형구조 ②그래프 [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 알고리즘 : 가중치가 높은.. 2023. 3. 9. 이전 1 2 3 4 다음 반응형
