Algorithm/Algorithm13 정렬-삽입 정렬(insertion sort) *정렬-삽입 정렬(insertion sort) -수열의 왼쪽부터 순서대로 정렬하는 방식 -우측의 미탐색 영역 숫자를 하나 꺼내 정렬이 끝난 영역의 적절한 위치에 삽입하는 방식 -각 라운드의 첫 숫자를 그 왼쪽에 있는 숫자와 비교, 만약 왼쪽 숫자가 작다면 라운드 종료 -꺼낸 숫자가 정렬 완료 영역의 숫자보다 작을 때 그 숫자가 가장 왼쪽에 도착할 때까지 비교 및 교체작업 -최악의 입력 데이터는 역순(큰 순)으로 나열된 경우 *삽입 정렬의 예 -1부터 9까지의 숫자 정렬(5-3-4-7-2-8-6-9-1) -첫 라운드는 왼쪽 끝의 숫자(5)를 정렬이 끝났다고 간주 -5만 정렬된 상태(5-3-4-7-2-8-6-9-1) -미탐색 영역 숫자 중 왼쪽 끝 숫자(3)를 꺼내 작업이 끝난 왼쪽 숫자(5)와 비교 -왼쪽.. 2023. 2. 8. 정렬-선택 정렬(selection sort) *정렬-선택 정렬(selection sort) -수열 중에서 최솟값을 검색해 왼쪽 끝 숫자와 교체하는 작업 반복하여 정렬 -수열 중 최솟값을 찾을 때는 선형 탐색 사용 -1라운드에서 n-1회, 2라운드에서 n-2회가되며 비교횟수는 버블정렬과 같은 n²/2 가 됨 -숫자 교체는 각 라운드에서 최대 1회 -입력 데이터가 작은 순으로 나열되어 있다면 교체는 한 번도 발생하지 않음 *선택 정렬의 예 -1부터 9까지의 숫자 정렬(6-1-7-8-9-3-5-4-2) -수열을 선형 탐색하여 최솟값(1) 찾고 왼쪽 끝 숫자와 교체(1-6-7-8-9-3-5-4-2) -정렬 반복 -(1-2-7-8-9-3-5-4-6) -(1-2-3-8-9-7-5-4-6) -(1-2-3-4-9-7-5-8-6) -(1-2-3-4-5-7-9-8-.. 2023. 2. 7. 정렬-버블 정렬(bubble sort) *정렬-버블 정렬(Bubble Sort) -오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교하여 교환작업 반복 -오른쪽에서 왼쪽으로 숫자가 옮겨가는 모습이 물속에서 거품이 올라오는 모양과 비슷하다고 하여 버블이라 불림 -버블소트는 1라운드에서 n-1회, 2라운드에서 n-2회가되며 비교 횟수는 n²/2 가 됨 -비교횟수는 입력 데이터의 순서와 상관없이 일정함 *버블 정렬의 예 -수열의 오른쪽 끝의 숫자와 그 옆의 숫자를 비교함(5 9 3 1 2 8 4 7 6)(비교) -만약 오른쪽 끝의 숫자가 더 작다면 좌우의 숫자 교체(5 9 3 1 2 8 4 6 7)(이동) -비교완료 후 한칸 왼쪽으로 옮겨 같은 방법으로 숫자 비교(5 9 3 1 2 8 4 6 7)(비교) -(5 9 3 1 2 8 4 6 7)(이동.. 2023. 2. 3. 정렬-정렬(sort)의 이해, 종류 *정렬-정렬의 이해 -정렬(sort) : 주어진 숫자를 순서대로 나열하는 것 -숫자를 작은 순 또는 큰 순으로 정렬할 때 정렬 알고리즘이 활용됨 -버블정렬(bubble sort) : 오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교해서 교환 -선택정렬(selection sort) : 수열 중에서 최솟값을 검색해 왼쪽 끝에 있는 숫자와 교체하는 작업 반복 -삽입정렬(insert sort) : 수열의 왼쪽부터 두 숫자를 비교하여 순서대로 정렬 -힙정렬(heap sort) : 데이터구조 힙을 사용하여 정렬 -병합정렬(merge sort) : 정렬하고 싶은 수열을 두 개의 수열로 분할하여 비교하고 각 그룹 병합 -퀵정렬(quick sort) : 기준이되는 수(피봇, pivot)를 수열 안에서 임의 선택 후 .. 2023. 1. 29. 데이터구조-이진 탐색 트리(binary search tree) *데이터구조-이진 탐색 트리(binary search tree) -그래프의 트리구조 사용 -각 노드에 데이터가 저장됨 -이진 탐색 트리를 확장한 데이터 구조는 여러 개 존재(자가 균형 이진 탐색 트리, B 트리 등) --자가 균형(self-balancing) 이진 탐색 트리 : 트리가 한쪽으로 치우친 경우 모양을 바로잡기 위해 항상 균형을 유지하도록 하는 구조, 탐색 효율을 유지할 수 있음 --B 트리 : 가질 수 있는 자식 노드의 수에 제한을 두지 않고 트리의 균형을 도모한 트리 *이진 탐색 트리의 예 -각 노드에 적혀있는 숫자는 데이터, 같은 숫자는 존재하지 않는다고 가정 *이진 탐색 트리의 두 가지 성질 -모든 노드는 왼쪽 가지에 포함되는 어떤 숫자보다 큰 숫자가 됨(최솟값 확인 가능, 왼쪽은 최솟.. 2023. 1. 18. 데이터구조-힙(Heap) *데이터구조-힙(Heap) -그래프의 트리 구조 중 하나 -그래프 : 몇 개의 정점(node)이 간선(edge)으로 연결된 것 -힙은 우선순위 큐(priority queue)를 구현할 때 사용 -우선순위 큐 : 데이터 구조의 하나로서 데이터를 자유롭게 추가할 수 있지만, 데이터를 추출할 때 최솟값부터 순서대로 선택하여 추출함 -각 노드에 데이터가 저장됨 *힙(Heap)의 예(최솟값 구하기) -힙의 각 노드에 적혀있는 숫자는 저장되어 있는 데이터이며 이 노드들은 최대 두 개의 자식 노드를 가질 수 있음 -노드는 위에서부터 채워지고 같은 층 에서는 왼쪽부터 채워짐 -힙에서 자식 노드의 숫자는 반드시 부모의 숫자보다 커야함 *힙에 데이터 추가하기 -데이터 추가 시 가장 아래층에 있는 왼쪽 노드부터 값을 채우고.. 2023. 1. 15. 데이터구조-해시 테이블(Hash Table) *데이터구조-해시 테이블(Hash Table) -데이터 검색을 효율적으로 하기위해 사용되는 구조 -키(Key)와 값(Value)이 한 쌍을 이루는 데이터를 저장함 -일반적으로 키는 데이터 식별자이며, 값은 데이터의 내용으로 생각할 수 있음 -해시테이블은 해시 함수를 이용해 배열 내의 특정 데이터에 빠르게 접근할 수 있음 -해시함수 : 주어진 데이터를 고정 길이의 불규칙한 숫자로 변환하는 함수 -해시 함수로 얻은 해시 값은 충돌 시 리스트 사용하여 기존 데이터의 뒤에 연결(연쇄법, 체이닝) *해시테이블 저장 -키(Key)와 값(Value)이 한 쌍을 이루는 데이터 저장 -해시함수(주어진 데이터를 고정 길이의 불규칙한 숫자로 변환하는 함수)와 함께 데이터 검색을 함 -해시테이블 사용하기(ex. 키 값 : 이.. 2023. 1. 14. 데이터구조-큐(Queue) *데이터구조-큐(Queue) -데이터를 1열로 나열 -먼저 넣은 것을 먼저 꺼내는 선입선출 구조(First In First Out, FIFO) -데이터 추가 및 삭제는 단방향으로만 가능하며 추가하는 쪽과 삭제하는 쪽이 반대 -대기행렬 이라고 불림 -인큐(enqueue) : 데이터를 추가할 때 가장 위에 추가 -디큐(dequeue) : 데이터를 꺼낼 때 가장 오래된(가장 아래) 데이터부터 꺼냄 *큐의 사용 -너비 우선 탐색에서 탐색 후보중 가장 오래된 것을 선택 할 때 사용 이 포스팅에 작성한 내용은 이시다 모리테루, 미야자키 쇼이치, ⌜알고리즘 도감⌟, 김완섭 옮김, (주)제이펍, 2020 에서 발췌하였습니다. 2023. 1. 13. 데이터구조-스택(Stack) *데이터구조-스택(Stack) -데이터를 1열로 나열 -나중에 넣은 것을 먼저 꺼내는 후입선출 구조(Last In First Out, LIFO) -데이터 추가 및 삭제는 단방향으로만 가능하며 가장 위에 있는 데이터만 접근 가능 -푸쉬(push) : 데이터를 추가할 때 가장 위에 추가 -팝(pop) : 데이터를 꺼낼 때 가장 최근에 추가된(가장 위에 있는)데이터부터 꺼냄 *스택의 사용 -깊이 우선 탐색에서 탐색 후보를 선택 할 때 사용 -항상 최신 데이터만 접근할 수 있도록 하는 구조에서 편리하게 사용할 수 있음 -예) (AB (C (DE) F) (G ((H) IJ) K)) 문자열의 괄호 대응관계 결정 --왼쪽부터 문자열을 읽어서 왼쪽 괄호가 나올 때마다 그 위치를 스택에 푸시, --오른쪽 괄호가 나오면 .. 2023. 1. 13. 데이터구조-배열(Array) *데이터구조-배열(Array) -데이터를 1열로 나열한 것 -(장)리스트와 대조적으로 데이터에 접근하기 쉬움 -(단)데이터 추가, 삭제 시 시간이 걸림 *배열의 구조 -배열의 예 -a라는 이름의 배열 안에 세 개의 문자열(파랑, 노랑, 빨강)의 데이터가 저장되어 있을 때 -데이터는 연속된 메모리 영역에 순서대로 저장됨 -파랑(a[0]), 노랑(a[1]), 빨강(a[2]) -배열의 데이터 위치 -배열의 이름 뒤 [] 대괄호 안에 배열 데이터의 순서를 가리키는 첨자가 있음 -첨자는 처음에 1이아닌 0부터 시작함 -파랑은 a배열의 첫 번째 요소이며 a[0] 의 첨자를 가지고 있음 -노랑은 a배열의 두 번째 요소, a[1] -빨강은 a배열의 세 번째 요소, a[2] -배열의 데이터 접근 -배열은 연속된 영역에 .. 2022. 12. 24. 이전 1 2 다음