Min'sLog

● 퀵 정렬(quick sort) 이란‘  찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘   퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.   분할 정복 알고리즘(Divide and Conquer)의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법● 퀵정렬 : 정렬 방법 정리  분할 정복(Divide Conquer)을 활용한 순환호출로 구현한다. ○  퀵정렬 과정    1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.    2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고      피벗보다 큰 요소들은 모두 피..

● 목표 계산기를 구현하기 위해 먼저 중위표현식(In-fix) 으로 입력받은 표현식을후위 표현식(Post-fix)으로 변환하여 해당 후위 표현식을 연산하여 결과값을 출력하는 프로그램을 작성한다.  ● 중위 표현식을 후위 표현식으로 변경하는 이유중위 표현식은 계산의 우선순위가 고려되지 않아, 우선 계산이 필요한 경우 소괄호를 이용하기 때문에, 해당 식을 후위 표현식으로 변경하여 연산되도록 한다.소괄호와 연산자의 우선순위를 인식하게 하여 중위 표기법의 수식을 직접 계산하게 프로그래밍하는 것 보다 후위 표기법의 수식을 계산하도록 프로그래밍 하는 것이 로직적으로 더 쉽다. 후위식으로 변경하기 위해선 두가지에 대한 고려가 필요하다.1. 소괄호를 파악하여 그 부분을 먼저 연산한다. 2. 연산자의 우선순위를 근거로 ..

● 버블 정렬(bubble sort) 이란? 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. ● 버블 정렬(bubble sort) 알고리즘 상세버블 정렬은 첫 번째 자료와 두 번째 자료를 비교 , 두 번째 자료와 세 번째 자료를 비교, 세 번째 자료와 네 번째 자료를 비교 하는 식으로 n-1 번째 인덱스까지 비교를 반복하여 정렬차순(오름,내림)에 따라 두 수의 위치를 교환(swap)하는 방식이다.(정렬 차순은 오름차순으로 포스팅 되었으니 참고!)1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제..

● 사전 지식 알고리즘의 성능 분석을 위해 사전에 알아야 할 수학적 지식이 있다면, 지수식과 로그식이다. y축을 연산횟수, x축을 데이터의 양이라고 하였을때, 아래와 같은 그래프를 보자. x축의 데이터가 증가함에 따라 연산회수가 기하급수적으로 증가하는 것이 y=2^x 그래프이며, 최초 수행 및 초기에는 연산회수가 어느정도 있지만 데이터의 증가에 따른 y축 연산회수의 증가가 더딘 것이 로그식이다. (지수식과 로그식은 역함수 관계 // y=x 에 대칭됨) ● 알고리즘을 평가하는 두가지 요소 알고리즘을 평가할때는 두가지 요소를 함께본다 1. 시간복잡도(Time Complexity) 먼저 시간 복잡도는 얼마나 빠른가를 판단하는 요소로 연산처리의 속도에 대한 것이다. 2. 공간복잡도(Space Complexity..

1. 개념 이진 탐색은 목표(Target)값 배열을 탐색할때, 탐색의 범위를 절반씩 줄여나가면서 목표값을 찾는다. 다만, 목표값 배열이 정렬되어 있어야 한다는 제약사항이 붙는다. 순차탐색의 경우, N 개의 배열중 Target 을 찾기위해 최대 N 번을 수행해야 하지만, 이진 탐색의 경우, 목표값을 탐색할때, 최대 log2N번을 수행하여 찾을수 있다. 따라서, 탐색을 해야하는 Data 범위가 늘어날수록 이진탐색이 목표값을 찾기위해 더 효율적이다. (Data가 정렬되어있다면!) 2. 이진탐색의 알고리즘 Ⅰ. 최초 탐색의 범위를 지정하기 위해 배열의 시작 위치[First]와 마지막 위치[Last] Index를 지정. Ⅱ. 시작위치와 마지막위치의 값을 더한 후, 2로 나눈값을 중앙 값[Mid]으로 지정한다. Ⅲ..