728x90 Algorithm/알고리즘 기본27 [Algorithm] 병합정렬(merger sort) 병합정렬? 병합 정렬의 특징은 빠르다. 구현이 어렵다. 병합 정렬의 flow 1. 분할: 문제를 반으로 나눈다. 2. 정복: 반으로 나눈 문제를 해결한다. 3. 병합: 해결된 문제들을 합친다. 예시 12345678 이 있으면 다음 단계로 나눈다. 1단: 1234 | 5678 2단: 12 | 34 | 56 | 78 3단: 1|2|3|4|5|6|7|8 다시 문제들을 정복해 나가면서 병합한다. 구현 public class MergeSort { MergeSort(){}; public void merge(int []data, int start, int center, int end) { int i = start; // 배열 앞부분 인덱스 int j = center+1; // 배열 중간 인덱스 int k = star.. 2021. 4. 13. [Algorithm] 조합 구현 구현1 nCr #include using namespace std; void combination(int arr[], int n, int r, int index, int target, int comb[]) { cout j & 1) { cout 2021. 4. 11. [Algorithm] 순열과 조합 수학적 개념 경우의 수를 세우는 방법 중 가장 기본이 되는 것은 순열과 조합이다. 가장 기본이 되는 것은 순열이다. 순열 수학에서, 순열 또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 개념 1, 2, 3 로 4자리의 수를 만들수 있는 자연수는 몇개 일까? 3! 이다 3! = 3*2*1 = 6 설명 어떻게 6개가 나오는지 아래와 같이 분석해 보았다. 1. 첫번째로 1을 선택하는 경우. 1 2 3 1 3 2 2. 첫번째로 2를 선택하는 경우 2 1 3 2 3 1 3. 세번째로 3을 선택하는 경우 3 1 2 3 2 1 아래 Tree로 표현을 해보았다. 순열공식 만일 3개중 2개를 선택해서 만드는 경우의 수는 3!/2! 이다. 이를 일반화 하면 해당 공식이 나온다. nPr = n!/(n.. 2021. 4. 11. 이전 1 ··· 4 5 6 7 다음 728x90 반응형
