알고리즘 정리

현재 공부하고 있는 알고리즘 정리해보기

1. 주차마다 배운 내용 정리

2. 개념은 해당 페이지에 이어서 정리

3. 코드 정리는 주차씩 블로그 만들어서 정리

4. 알고있는 개념이여도 다 적어둘 것

---

---

1. 재귀함수

• 큰 문제를 부분 문제로 나눠 풀 때 사용
• 반드시 기저사례를 사용할 것
• 사이클이 있다면 사용 금지
• 반복문이 될 수 있다면, 반복문으로 구현
• 이해가 가지 않는다면, 그림으로 그려보기

ex1. 팩토리얼

5! = 5 x 4 x 3 x 2 x 1
---> n x n-1 x n-2 x n-3 x n-4
f(n) = n(n-1)
f(n-1) = (n-1)(n-2)
f(n-2) = (n-2)(n-3)

//코드

int fac(int n){
	if(n==1) return 1;
	return n * f(n-1);
}

ex2. 피보나치

0 + 1 + 1 + 2 + 3 = 5

//코드

int fivo(int n){
	if(n==1 || n==0) return n;
    return f(n-1) + f(n-1);
}

ex3. 하노이탑 ⭐

1. 맨 마지막을 제외(n-1)을 제외하고 temp에 넣어주기
2. 맨 마지막을 to(옮길 위치)에 넣어주기
3. 맨 마지막을 to(옮길 위치)에 넣어주기

void hanoi(int n, char from, char temp, char to){
	if(n==1) printf("원판 1을 %c -> %c로 이동\n", from, to); // 마지막 넣는 것
    else{
    	hanoi(n-1, from, to, temp);
        printf("%d를 %c -> %c로 이동\n", n-1, from, to);
        hanoi(n-1, temp, from, to);
    }

}

int main(){
	hanoi(4, 'A', 'B','C');
    return 0;
}

2. 순열

• 순서와 상관 있게 뽑는 것 :: 순열

• 순서와 상관없이 뽑는 것 :: 조합

• 정렬이 되어 있어야함.

  next_permutation(시작, 끝); :: 오름차순
  prev_permutation(시작, 끝); :: 내림차순

  [공식]
  nPr : n! / (n-r)!
  n : 몇개중에
  r : 몇개 뽑을 건지

//코드

vector<int> v = {2,1,3};
int a[] = {1,2,3};

sort(v.begin(), v.end());
sort(&a[0], &a[0]+3);

next_permutation(v.begin(), v.end());
next_permutation(&a[0], &a[0]+3);
next_permutation(a, a+3);

2-1. 재귀함수로 만드는 순열

1. 기본순열

   //코드
   
   next_permutation(v.begin(), v.end());

2. 재귀함수로 만드는 순열

• 이해가 안된다면, 꼭 그림 그려서 파악해보기

  
  int make_permutation(int n, int r, int depth){
  	if(r==depth) return;
     
     for(int i=depth; i<n;i++){
     	swap(v[r], v[depth]);
         make_permutation(n, r, depth+1);
         swap(v[r], v[depth]);
     }
     return;
  }
  

  

---

2. 메모리

• 메모리는 16진수로 이뤄져 있으며, 1byte씩 사용됨
• 포인터 변수는 자료형에 상관 없이 항상 8byte(64bit기준)