본문 바로가기

Data Structure/Algorithm

Recursive Algorithm - Binomial theorem Binomial theorem(이항계수) - 이항계수(binomial theorem) 알고리즘 : 조합론에서 사용되며, n개의 서로 다른 원소에서 r개의 원소를 선택하는 경우의 수를 계산 - 이항계수 : 조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수 / 2를 상징하는 ‘이항’이라는 말이 붙은 이유는 하나의 아이템에 대해서는 ‘뽑거나, 안 뽑거나’ 두 가지의 선택만 존재 (ex)4개의 집합 중에서 2개를 순서없이 고르는 조합의 수는 ‘4! / 2! / 2!’, 즉 6 nCk = n! / k!(n-1)! = (4*3*2*1) / (2*1)(2*1) = 3*2*1 = 6 1. r이 0이거나 n과 같으면 함수는 1을 반환 2. 그렇지 않으면 k-1과 n-1인자로하.. 더보기
Recursive Algorithm - GCD(최대공약수) GCD - 유클리드 호제법/알고리즘(Euclidean Algorithm) : 두 수의 “최대공약수(GCD)”를 찾기 위한 알고리즘 - 큰 수를 작은 수로 나누어 떨어지게 하여 수를 반복적으로 취하여 나머지 0이 될 때까지 작동하는 방법 / 작은 수가 최대공약수 Java예시 - m = 작은 수, n = 큰 수를 입력으로 받고, n=0이 될 때까지 recursive 실행 - 큰 수와 작은수를 큰 수로 나눈 나머지를 구하는 연산을 계속 하면서, m의 값을 갱신 - main함수에서 실행한 결과 C예시 - 추가 예정 더보기
Recursive Algorithm - Fibonacci Fibonacci - 피보나치 수열 : 이전 두 항의 합이 다음 항이 되는 수열 - 첫째 항과 둘째 항이 1이고 이후 모든 항은 모든 항은 바로 앞 두항의 합으로 이루어지는 수열을 의미 - 피보나치 수열의 예시 - [1, 1, 2, 3, 5, 8, 13, 21, 34,...] Java예시 - parameter로 들어온 값이 0 이거나 1이면 0, 1 return - 첫 번째와 두 번째 값은 1, 세 번째부터는 현재 위치 기준 앞에 있는 2개의 합으로 구성(세 번째 값 = 두 번째 값 + 첫 번째 값, 네 번째 값 = 세 번쩨 값 + 두 번째 값, ...) - main함수에서 실행한 결과 C예시 - 추가예정 더보기
Recursive Algorithm - Recursive Function Recursive Function - Recursive(재귀) : 어떤 문제를 해결하기 위해 알고리즘을 설계할 때 동일한 문제의 조금 더 작은 경우를 해결함으로써 그 문제를 해결하는 것 - 팩토리얼, 거듭제곱, 문자열 반대로 출력 등의 문제에 적용 가능 Java 예시1 - Factorial - Factorial : 자연수 n에 대해서 1부터 n까지의 모든 자연수를 곱한 값 - factorial() 함수에 파라미터로 값을 넘길 경우 재귀함수로 반복하여 결괏값을 반환해 주는 함수 - factorial(5) = 5 * factorial(4) / factorial(4) = 4 * factorial(3) / factorial(3) = 3 * factorial(2) / factorial(2) = 2 * factor.. 더보기
Sort Algorithm - Heap Heap - Heap = 최솟값과 최대값을 빠르게 찾아내기 위해 완전2진트리 형태로 만들어진 data structure Heap이 가지는 기본 특성 left child node = index * 2 + 1 right child node = index * 2 + 2 parent node = (index-1) / 2 - 오름차순 정렬 : 최대 Heap, 내림차순 정렬 : 최소 Heap 사용 최대 Heap : Parent node의 value(key value) = Child node의 value Java예시 HeapSort() : Heap Sort Algo. 실행 sort1() : heapify()를 이용해 Max Heap을 얻는 함수 if(size=0; i--){heapify(a, i, size-1);} .. 더보기
Sort Algorithm - Quick Quick - Divide & Conquer Algorithm 중 하나 - pivot을 이용 - 위치에 따라 간격의 불균형이 발생할 수도 있다. - Merge Sort와 속도가 비슷하고, Heap Sort보다 속도가 빠르다. Java예시 *left = 부분 Array의 1st index *pivot = 부분 Array의 중간값 *right = 부분 Array의 last index partition() : - left 더보기
Sort Algorithm - Merge Merge - Divide & Conquer Algorithm 중 1개 / 보통 재귀함수로 구현 - Array의 길이가 1이 될 때까지, 2개의 부분 Array로 계속 divide -> divide가 끝나면, 다시 merge 후 sort Java예시 - merge() : 2개의 부분 Array의 index를 비교하면서 정렬 후 합치기 *left : 왼쪽 부분 Array의 index *right : 오른쪽 부분 Array의 index *tmpArr[] : 매개변수로 들어온 arr의 값을 비교하고 sort하기 위해 만든 Array for(int i = left; i 정렬과정을 거친 결과물들을 tmpArr[]에 저장 int part1 = left; : part1에 left를 저장int part2 = mid +.. 더보기
Sort Algorithm - Shell Shell - Insertion Sort의 장점을 살리고, 단점을 보완한 Algorithm - 전체 배열을 정해진 간격으로 부분적으로 나눠서 sort한 뒤, 다시 정해진 간격을 줄여서 또 부분으로 나눠서 sort하는 과정 반복 Java예시 - for(int h = array.length/2; h>0; h/=2){} : h = sort에 사용할 일정 간격 / 초기에 간격은 주어진 array 의 반으로 설정( int h = array.length/2; )하고 h>0일 때까지 한 cycle을 반복할 때마다 간격을 반씩 줄인다.(h/=2) - for(int i = h; i=0 && array[j] > tmp){array[j+h] = array[j]; j-=h;} array[j+h] = tmp;} : 정해진 간격.. 더보기

티스토리툴바