오봉이와 함께하는 개발 블로그

Algorithmday_4 정리 (2021.12.01 수요일) 탐색(Search) 데이터의 집단 내에서 특정 데이터를 찾는 구조 탐색 알고리즘의 효율성은 탐색 집단의 구조가 어떻게 구성되어 있느냐에 따라 영향을 받음 컴퓨터가 가장 많이 하는 작업 중 하나 탐색에 사용되는 자료 구조 배열, 연결 리스트, 트리, 그래프 등 탐색 방법 순차 탐색 이진 탐색 보간 탐색 이진 트리 탐색 순차 탐색(Sequential Search) 정렬되지 않은 데이터의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법 탐색 방법 중 가장 간단하고 직접적인 방법 크기가 적은 리스트에서는 효율적이지만 크기가 큰 리스트에서는 매우 비 효율적 장점 하나씩 비교하기 때문에 탐색 용이 탐색 알고리즘 간단 단점 탐색 ..

Algorithmday_4 정리 (2021.12.01 수요일) 힙 정렬 (Heap Sort) 정렬할 원소를 힙(heap)이라는 자료 구조를 이용하여 정렬하는 방법 힙 구조 완전 이진 트리로, 각 노드의 키 값이 자식 노드들의 키 값보다 작지 않은 트리 로서 힙 루트는 트리 중 가장 큰 값 을 나타냄 힙 정렬 방법 주어진 데이터로 이진 트리를 구성한 후 힙 구조 알고리즘과 힙 정렬 알고리즘을 수행 힙 구조 알고리즘 제일 늦게 구성된 트리 선택 부모 노드와 자식 노드 중 가장 큰 값 선택 부모 노드와 자식 노드 중 가장 큰 값을 비교하여 자식 노드가 크면 서로 위치 교환 (큰 값을 위로 보냄) 힙 정렬 알고리즘 근 노드의 값을 배열의 맨 마지막에 저장 (근 노드 삭제에 해당) 빈 근 노드의 자리에선 자식 노..

Algorithmday_4 정리 (2021.12.01 수요일) 기수 정렬(Radix Sort) 정렬할 원소의 키 값을 나타내는 숫자의 자리수(radix)를 기초로 정렬하는 기법(사전식 정렬 방법) 정렬하고자 하는 값을 버킷에 넣어 정렬 버킷으로 큐 사용 데이터가 입력되는 곳, 출력되는 곳 : 먼저 들어온 것이 먼저 출력 버킷의 개수는 키의 표현 방법과 밀접한 관계 이진법을 사용한다면 버킷은 2개 알파벳 문자를 사용한다면 버킷은 26개 십진법을 사용한다면 버킷은 10개 기수 정렬 방법 첫 번째 패스 (1라운드) 정렬할 키의 가장 작은 자리수를 기준으로 분배 정렬 두 번째 패스 두 번째 작은 자리수를 기준으로 분배 정렬 키 값이 같은 경우 이전 정렬에서의 순서를 그대로 유지 키의 가장 큰 자리수까지 반복 수..

Algorithmday_4 정리 (2021.12.01 수요일) 이원 합병 정렬(Two-way Merge Sort) 정렬된 2개의 리스트를 혼합하여 완전히 정렬된 하나의 리스트로 합하는 정렬 방식 6, 9, 2, 12, 8, 34, 23, 33, 56, 17, 56, 32 (6, 9), (2, 12), (8, 34), (23, 33), (17, 56), (32, 56) (2, 6, 9, 12), (8, 23, 33, 34), (17, 36, 56, 56) (2, 6, 9, 9, 12, 23, 33, 34), (17, 36, 56, 56) {2, 6, 8, 9, 12, 17, 23, 32, 33, 34, 56, 56}

Algorithmday_4 정리 (2021.12.01 수요일) 퀵 정렬(Quick Sort) 분할 정복 정렬 방법 중 하나 전체 리스트를 2개의 부분 리스트로 분할하고 각각의 서브 리스트를 다시 퀵 정렬로 정렬 기준 값보다 큰 값들은 오른쪽으로, 작은 값들은 왼쪽으로 재 배열 정렬 방법 전체 리스트에서 한 원소를 기준 값(pivot)으로 선정 피벗을 기준으로 두 개의 서브 리스트로 분할 왼쪽 : 피벗보다 작은 값의 원소들로 구성 오른쪽 : 피벗보다 크거나 같은 값의 원소들로 구성 각각의 파티션(서브 리스트)에 대해 다시 퀵 정렬을 순환 적용 피벗 선정 및 파티션 분할 퀵 정렬 수행 순서 피벗(pivot) : 가장 왼쪽 숫자를 피벗으로 선정 두 개의 변수 : low와 high(이동) low는 왼쪽에 위치 ..