yoongrammer

목차힙 (Heap) or 이진 힙(binary heap) 알아보기힙(heap)은 이진 힙(binary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조입니다. 힙은 다음과 같은 속성을 가지고 있습니다.완전 이진트리(Complete Binary Tree) 이다.부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다.키값 대소관계는 오로지 부모자식 간에만 성립되며 형제사이에는 대소관계가 정해지지 않음.힙의 종류힙에는 두가지 종류(최대 힙, 최소 힙)가 있습니다. 1. 최대 힙 (Max Heap)부모 키값이 자식노드 키값보다 큰 힙Key(parent) ≥ Key(child)가장 큰 값이 루트..

목차시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)알고리즘을 평가할 때 시간 복잡도와 공간 복잡도를 사용합니다.시간 복잡도: 알고리즘의 수행시간을 평가공간 복잡도: 알고리즘 수행에 필요한 메모리 양을 평가시간 복잡도와 공간 복잡도는 주로 점근적 표기법 중 빅오 표기법을 이용하여 나타냅니다.이유는 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠해볼 수 있기 때문입니다.시간 복잡도(Time Complexity)알고리즘의 수행 시간을 분석할 때 시간 복잡도를 사용합니다.수행 시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가합니다. 기본 연산은 다음과 같습니다.데이터 입출력 - copy, move...산술 연산 - add,..

목차점근 표기법 (asymptotic notation) 알아보기점근 표기법(asymptotic notation)을 이해하고 대표적인 세 가지 유형의 점근 표기법인 빅오 표기법(Big-O notation), 빅 오메가 표기법(Big-Omega notation) , 빅 세타 표기법(Big-Theta notation)에 대해 알아보도록 하겠습니다.점근 표기법 (asymptotic notation) 컴퓨터 알고리즘의 실행시간은 실행환경에 따라 다르게 측정됩니다. ex) 하드웨어, 운영체제, 언어 등 실행환경을 동일하게 하는 것은 어렵기 때문에 기본 연산(산술 연산, 제어 연산 등)의 실행 횟수로 성능을 분석합니다.연산의 실행 횟수는 입력 크기 n에 대한 함수로 표현합니다. ex) \(f(n) = n^2+3n+1..

목차보간 탐색 (Interpolation Search) 개념 및 구현보간 탐색 (Interpolation Search)은 정렬된 리스트에서 범위를 줄여가며 검색하는 알고리즘입니다. 보간 검색은 전화부에서 이름 (책의 항목이 정렬되는 키 값)을 검색하는 방법과 유사합니다.  동작 방식은 이진 탐색과 비슷하지만 탐색 위치를 정하는 방식이 다릅니다. 이진 탐색과 보간 탐색의 탐색 위치를 결정하는 공식은 다음과 같습니다.arr [] : 데이터가 들어있는 배열low : arr [] 배열에 시작 indexhigh : arr[] 배열에 마지막 indexx : 검색 값pos : 탐색 위치 index이진 탐색\( pos = (low + high) / 2 \) 보간 탐색\( pos = low + (x - arr [low]..

목차점프 탐색(Jump search) 개념 및 구현Jump search는 순차적으로 탐색하는 선형 탐색과 달리 블록 단위로 이동(점프)하면서 탐색하는 알고리즘입니다.정렬된 배열에서만 사용할 수 있고, 한 칸씩 이동하는 것이 아니기 때문에 선형 탐색보다 적은 요소를 탐색하게 됩니다. 이 알고리즘은 선형 탐색보다 빠르지만 이진 탐색보다는 느립니다.동작 방식배열을 블록단위로 나누기 위해 블록 사이즈 m을 구합니다.m의 최적 값은 다음과 같습니다. 여기서 n은 요소의 수입니다.m = √n한 블록에서 값을 탐색하고 없으면 다음 블록으로 이동합니다.값을 가진 블록을 찾으면 선형 탐색을 사용하여 정확한 인덱스를 찾습니다.블록 최적 사이즈 구하는 과정m에 최적 값을 구하는 공식은 다음과 같습니다.블록 크기가 m이고 n..