Algorithm

[알고리즘] mergeSort 병합(합병)정렬 (pseudo-code, 파이썬, Java)

병합정렬(mergeSort) 주어진 크기가 n인 리스트 A를 크기가 n/2인 두 부분으로 나눈다. 크기가 n/2인 두 부분을 재귀적으로(recursively) 정렬한다. 정렬된 두 부분을 하나로 병합한다 Merge(병합) 알고리즘 : 나뉜 두부분의 첫부분을 비교하여 작은 원소를 새로운 배열에 넣어주고, 작은 원소가 있던 부분배열의 인덱스를 늘려준다. 이렇게 부분배열이 다 넣어질 때까지 반복한다. 다른 한쪽부분은 남은 부분이 있을 수 있으므로 남은 부분배열의 전체를 배열에 넣어준다. Pseudo-code mergeSort 함수 : 정렬되지 않은 리스트(배열)을 재귀적으로 분할하는 역할을 한다 Algorithm mergeSort(arr, left, right) if (left < right) mid = (f..

[알고리즘] binarySearch 이진탐색, 재귀이진탐색_분할과 정복 (pseudo-code 파이썬, Java)

이진탐색 오름차순으로 정렬되어 있는 리스트(배열)에서 찾고자 하는 원소 item 의 위치를 찾을 때, 리스트(배열)에서 중간지점을 구한 후, item 값과 비교하여, item 값이 중간지점보다 작으면, 왼쪽부분에서 다시 중간지점을 찾아서 비교하여, 탐색하고, 크면 오른쪽부분에서 탐색한다. 중간지점과 item 과 값이 같으면 인덱스를 반환한다. Pseudo-code Algorithm binarySearch(A, item, n) left = 0 right = n-1 while (left right return -1 : item이 없을 경우 -1 반환 else mid = (left + right) / 2 : 2로 나눈 몫을 구하는 연산 if (item == A[mid]) return mid else if (i..

[알고리즘]분할과 정복 개념 및 예시

분할과 정복 큰 입력의 문제를 작은 입력의 문제들로 나눈다. 나눈 작은 문제들의 해를 재귀적으로 구현한다. 재귀적으로 나눈 문제들의 해를 이용하여 원래 문제의 해를 구한다. 리스트(배열)에서 최대값 찾기 분할과 정복 Algorithm maximum(a, first, last) if(first == last) then return a[first] else mid = (first + last) // 2 lmax = maximum(a, first, mid) rmax = maximum(a, mid + 1, last) if lmax > rmax then return lmax else return rmax mid 를 기준으로 나눈 왼쪽 반의 최대값 lmax 와 오른쪽 반의 최대값 rmax 를 비교하여 더 큰값이 전..

[알고리즘] bubble_sort 버블정렬(pseudo-code, 파이썬, Java)

버블정렬 매 단계마다 처음부터 마지막까지 차례대로 인접한 두 원소를 비교하여 뒤에 있는 원소가 앞의 원소보다 작은 경우 두 원소를 교환 각 단계 수행 후 최대값이 마지막으로 이동하므로, 마지막 원소는 정렬대상에서 제외 Pseudo-code Algorithm bubbleSort(a, n) for i = n – 1 downto 1 for j = 0 to i-1 if(a[j] > a[j+1]) then int temp = a[index] a[index] = a[i] a[i] = temp Python def bubble_sort(arr): for i in range(len(arr)-1,0,-1): for j in range(i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[..

[알고리즘] selectionSort 선택정렬(pseudo-code, Java, 파이썬)

선택정렬 각 루프마다 최대(최소) 원소를 찾는다 최대(최소) 원소와 마지막(가장 앞에 있는) 원소를 교환한다 마지막(가장 앞에 있는) 원소를 제외한다 – 하나의 원소만 남을 때까지 위의 루프를 반복 pseudo 코드 배열 끝에서부터 나머지 원소들 중 최대값과 교환하는 방식 Algorithm selectionSort(a,n) for i = n-1 down to 1 //a[0]부터 a[i]까지 중 가장 큰 원소의 위치 index를 찾는다. index = 0 for j = 1 to i if(a[index] < a[j]) then index = j //a[index]와 a[i]를 교환한다. int temp = a[index] a[index] = a[i] a[i] = temp python 코드 배열 처음부터 나머..

[알고리즘] Stable & In-place

Stable 알고리즘 정렬할 자료들 중 동일한 두 자료의 상대적인 위치가 **정렬 후에도 유지**되는 알고리즘 정렬을 했을 때 중복된 값들의 순서가 변하지 않으면 **안정(Stable) 정렬**, 변하면 **불안정(Unstable) 정렬** Stable 알고리즘 Insertion Sort Merge Sort Bubble Sort Counting Sort Unstable 알고리즘: Selection sort Heap Sort Shell Sort Quick Sort In-place 알고리즘 **입력을 저장하는 메모리 공간** 이외에 추가로 사용하는 메모리공간이 O(1)인 알고리즘 추가적인 메모리가 거의 들지 않는 알고리즘 In-place 알고리즘 Insertion Sort Selection Sort Bubb..

알고리즘에 대하여 (pseudo-code)

알고리즘 문제 해결 과정을 체계적으로 기술한 것 문제의 요구 조건 입력과 출력으로 명시할 수 있다. 유래 알 콰리즈미(al-Khwarizmi) ; 페르시아 과학자, 근대 수학의 아버지 ↓ Algoritmi : 알 콰리즈미를 라틴화한 단어 ↓ Algoritm Pseudo-language (의사코드) 알고리즘 기술을 위한 표준 언어 pseudo-code : pseudo-language 로 작성한 코드 프로그래밍 언어보다 융통성이 있음 모호함이 적고, 명령어를 정의하면 됨 엄격한 문법에 따르지 않아도 무방 if 문 if 조건 then else while 문 while 조건 for 문 for i = 1 to n for i = n downto 1 1 ~ n 까지 반복 알고리즘의 평가 기준 정확성 수행시간 사용 메..