yoongrammer
목차 시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity) 알고리즘을 평가할 때 시간 복잡도와 공간 복잡도를 사용합니다. 시간 복잡도: 알고리즘의 수행시간을 평가 공간 복잡도: 알고리즘 수행에 필요한 메모리 양을 평가 시간 복잡도와 공간 복잡도는 주로 점근적 표기법 중 빅오 표기법을 이용하여 나타냅니다. 이유는 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠해볼 수 있기 때문입니다. 시간 복잡도(Time Complexity) 알고리즘의 수행 시간을 분석할 때 시간 복잡도를 사용합니다. 수행 시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가합니다. 기본 연산은 다음과 같습니다. 데이터 입출력 - copy, move... 산..
목차 점근 표기법 (asymptotic notation) 알아보기 점근 표기법(asymptotic notation)을 이해하고 대표적인 세 가지 유형의 점근 표기법인 빅오 표기법(Big-O notation), 빅 오메가 표기법(Big-Omega notation) , 빅 세타 표기법(Big-Theta notation)에 대해 알아보도록 하겠습니다. 점근 표기법 (asymptotic notation) 컴퓨터 알고리즘의 실행시간은 실행환경에 따라 다르게 측정됩니다. ex) 하드웨어, 운영체제, 언어 등 실행환경을 동일하게 하는 것은 어렵기 때문에 기본 연산(산술 연산, 제어 연산 등)의 실행 횟수로 성능을 분석합니다. 연산의 실행 횟수는 입력 크기 n에 대한 함수로 표현합니다. ex) \(f(n) = n^2+..
목차 보간 탐색 (Interpolation Search) 개념 및 구현 보간 탐색 (Interpolation Search)은 정렬된 리스트에서 범위를 줄여가며 검색하는 알고리즘입니다. 보간 검색은 전화부에서 이름 (책의 항목이 정렬되는 키 값)을 검색하는 방법과 유사합니다. 동작 방식은 이진 탐색과 비슷하지만 탐색 위치를 정하는 방식이 다릅니다. 이진 탐색과 보간 탐색의 탐색 위치를 결정하는 공식은 다음과 같습니다. arr [] : 데이터가 들어있는 배열 low : arr [] 배열에 시작 index high : arr[] 배열에 마지막 index x : 검색 값 pos : 탐색 위치 index 이진 탐색 \( pos = (low + high) / 2 \) 보간 탐색 \( pos = low + (x - ..
목차 점프 탐색(Jump search) 개념 및 구현 Jump search는 순차적으로 탐색하는 선형 탐색과 달리 블록 단위로 이동(점프)하면서 탐색하는 알고리즘입니다. 정렬된 배열에서만 사용할 수 있고, 한 칸씩 이동하는 것이 아니기 때문에 선형 탐색보다 적은 요소를 탐색하게 됩니다. 이 알고리즘은 선형 탐색보다 빠르지만 이진 탐색보다는 느립니다. 동작 방식 배열을 블록단위로 나누기 위해 블록 사이즈 m을 구합니다. m의 최적 값은 다음과 같습니다. 여기서 n은 요소의 수입니다. m = √n 한 블록에서 값을 탐색하고 없으면 다음 블록으로 이동합니다. 값을 가진 블록을 찾으면 선형 탐색을 사용하여 정확한 인덱스를 찾습니다. 블록 최적 사이즈 구하는 과정 m에 최적 값을 구하는 공식은 다음과 같습니다. ..
목차 이진 탐색 (Binary search) 개념 및 구현 이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘입니다. 이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있습니다. 동작 방식 이진 탐색 알고리즘은 리스트의 중간 값과 비교하여 검색값을 찾습니다. 중간 값을 찾아야 하기 때문에 반드시 정렬된 배열에서만 사용할 수 있습니다. 이진 탐색의 동작 방식은 다음과 같습니다. 배열의 중간 값을 가져옵니다. 중간 값과 검색 값을 비교합니다. 중간 값이 검색 값과 같다면 종료합니다. (mid = key) 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색합니다..