알고리즘

💡탐욕 알고리즘 - 최적해를 구하는 데에 사용되는 근사적인 방법 (여러 경우 중 하나를 결정해야 할 때 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식) - 그 순간의 선택은 지역적으론 최적이지만 전체적으로 봤을 땐 아닐 수 있음 ‼️ 탐욕 알고리즘을 적용할 수 있는 문제의 경우, 지역적으로 최적이면 전역적으로도 최적 💡 문제 해결 방법 1) 선택 절차: 현재 상태에서 최적의 해답 선택 2) 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사 3) 해답 검사: 원래의 문제가 해결되었는지 검사 후, 해결되지 않았으면 선택 절차로 돌아감 ✔️ 거스름돈 계산하기 문제 - 동전의 개수가 최소가 되도록 거스름 돈을 내는 방법 - 가치가 높은 동전부터 x가 초과되지 않도록 계속 냄 while(동전이 남..

💡 행렬 - m x n 개의 원소를 갖는 사각형 배열 (m: 행, n: 열) - 행,열의 수가 같으면 정방행렬 💡 행렬의 곱 - A 행렬과 B 행렬이 있을 때, A행렬의 가로와 B행렬의 세로의 원소를 하나씩 곱해 더함 A11 A12 B11 B12 C11 C12 A21 A22 B21 B22 C21 C22 C11 = A11xB11 +A12xB21 int* matrix( int N, int a[][], int b[][]) { for (int i = 0; i < N;i++) for (int j = 0; j < N; j++) { c[i][j] = 0; for (int k = 0; k < N; k++) { c[i][j] = c[i][j] + a[i][k] * b[k][j]; } } } ✔️시간 복잡도 - 덧셈의 관..

💡빠른정렬 - 기준점(pivot)을 기준으로 배열을 둘로 쪼갠다 - 기준점보다 작으면 왼쪽, 크면 오른쪽으로 분리 - 다시 왼쪽, 오른쪽 배열에서 기준점을 잡고 분리 - 배열에서 기준점을 제외하고 모든 원소와 비교하므로 점화식은 T(n) = n-1 그 외 정렬이나 합병 과정은 없음 - 일정 복잡도 계산 X quickwort(){} partition(){} ✔️ 최악의 시간복잡도 - 이미 오름차순으로 정렬되어 있어 왼쪽 배열은 아무것도 없고 오른쪽에는 정렬된 배열이 남아 무의미하게 계속 기준을 잡고 비교하는 과정을 거치기 때문 - T(n) = T(0) + T(n-1) + n -1 , if n>0 (* n개의 배열을 비교하면서 n-1 비교, 왼쪽은 0, 오른쪽은 다시 n-1개의 배열로 이뤄짐) = n(n-1..

💡합병 정렬(Mergesort) - n개의 정수를 가진 배열을 올림차순으로 정렬 - 배열의 원소의 개수가 1이 될때까지 반으로 분할하여 분리한 배열을 각각 따로 정렬한 후 취합 void mergesort(int n, int s[]){ // 배열을 쪼개는 함수 const int h = n/2, m = n-h; int U[1...h], V[1...m] // 배열의 인덱스를 표현(원소의 개수) if(n>1){ // U배열에 S배열의 1~h번째 원소를 복사 // V배열에 S배열의 h+1~n번째 원소를 복사 mergesort(h,U); mergesort(m,V); merge(h,m,U,V,S); } } void merge(int h, int m, const int U[], const int V[], const i..