공부기록

교집합 배열 생성 전에 (오름차순) 정렬 필요 !!! a 🔽 -> 🔽 2 3 5 7 10 b 🔽 3 5 10 12 17 => a 배열 포인터 증가 (b배열에는 3보다 작은 값이 없으니까) => 포인터 값 증가 후 값 비교 후 같으면 c 배열에 삽입 c 🔽 3 a 🔽 2 3 5 7 10 b 🔽 3 5 10 12 17 => 동시에 포인터 값 증가 => 포인터 값 증가 후 값 비교 후 같으면 c 배열에 삽입 c 🔽 3 5 a 🔽 -> 🔽 2 3 5 7 10 b 🔽 3 5 10 12 17 => 동시에 포인터 값 증가 => a 배열 값이 더 작으므로 a 포인터 증가 => 포인터 값 증가 후 값 비교 후 같으면 c 배열에 삽입 c 🔽 3 5 10 => (더 짧은) 배열 하나가 끝나면 break; #include #..

a 🔽 1 3 5 b 🔽 2 3 6 7 9 c 🔽 1 a 🔽 1 3 5 b 🔽 2 3 6 7 9 c 🔽 1 2 a 🔽 1 3 5 b 🔽 2 3 6 7 9 c 🔽 1 2 3 a 🔽 1 3 5 b 🔽 2 3 6 7 9 c 🔽 1 2 3 3 a 🔽 1 3 5 b 🔽 2 3 6 7 9 c 🔽 1 2 3 3 5 한쪽 배열이 끝나면 break + 더 긴 배열의 나머지 값 삽입 #include #include #include using namespace std; int a[101], b[101], c[300]; int main(){ //freopen("input.txt", "rt", stdin); int n, m, i, p1=1, p2=1, p3=1; scanf("%d", &n); for(i=1; i

is: 5 3 4 0 2 1 1 0 n~1까지 큰 수부터 처리해야 한다!! (삽입정렬 응용) #include #include #include using namespace std; int main(){ //freopen("input.txt", "rt", stdin); int n, i, j, pos; scanf("%d", &n); vector a(n+1); vector b(n+1); for(i=1; i=1; i--){ pos=i; for(j=1; j

삽입정렬 이용하기!! input : 5 9 1 2 3 2 6 2 3 5 7 cache : 0 0 0 0 0 pos=-1; for(j=0; j=1; j--) c[j]=c[j-1]; } else{ //hit for(j=pos; j>=1; j--) c[j]=c[j-1] } c[0]=a; } miss 1 0 0 0 0 miss 2 1 0 0 0 miss 3 2 1 0 0 hit 2 3 1 0 0 miss 6 2 3 1 0 hit 2 6 3 1 0 hit 3 2 6 1 0 miss 5 3 2 6 1 miss 7 5 3 2 6

: 앞에서부터 정렬된 배열 부분과 비교 + 자신의 위치를 찾아서 삽입 💥 i=1 11 7 5 6 10 9 tmp=a[i] 7 for(j=i-1; j>0; j--) { if(a[j] > tmp) a[j+1]=a[j] else break; } 11 11 5 6 10 9 (j=-1인 상태) a[j+1] =tmp 7 11 5 6 10 9 💥i=2 7 11 5 6 10 9 tmp=a[i] 5 for(j=i-1; j>0; j--) { if(a[j] > tmp) a[j+1]=a[j] else break; } 7 11 11 6 10 9 7 7 11 6 10 9 (j=-1인 상태) a[j+1] =tmp 5 7 11 6 10 9 💥 i=3 5 7 11 6 10 9 tmp=a[i] 6 for(j=i-1; j>0; j--) ..

#include #include #include using namespace std; //int main(){ ////freopen("input.txt", "rt", stdin); //int a[101], n, tmp, i, j, b[101], c[101]; //scanf("%d", &n); //for(i=0; i

: 이웃한 두 수끼리 계속 비교하면서 정렬 💥 j=0 ~ 5 💥 13 23 11 7 5 15 a[j] > a[j+1] 뒤의 숫자가 작다면? swap => 발견될 때마다 교환이 필요하기 때문에 시간복잡도가 높다! 13 11 23 7 5 15 13 11 7 23 5 15 13 11 7 5 23 15 13 11 7 5 15 23 💥 j=0 ~ 4 💥 13 11 7 5 15 23 11 13 7 5 15 23 11 7 13 5 15 23 11 7 5 13 15 23 💥 j=0 ~ 3 💥 11 7 5 13 15 23 ... 똑같이 반복 for(i=0; i ... 이렇게 for문이 돌려면 //n-1에서 i를 빼준 범위만 돌면 된다! **참고자료 https://gmlwjd9405.github.io/2018/05/06/..

for (i=0 ... for(j=i+1 .. : 최소 값을 찾아서 i 지점과 swap 💥i=0💥 13 5 11 7 23 15 5 13 11 7 23 15 💥i=1💥 idx = i; for(j=i+1; j a[idx]=11 a[idx] = 11 a[j] = 7 -> idx=j -> a[idx]=7 ==> idx 값이 계속 바뀌면서 idx=3 가장 작은 값의 인덱스를 저장하게 됨! 5 7 11 13 23 15 💥i=2💥 5 7 11 13 23 15 💥i=3💥 5 7 11 13 23 15 💥i=4💥 5 7 11 13 15 23 **참고 https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html [알고리즘] 선택 정렬(selection sort..

#include #include #include using namespace std; int main(){ //freopen("input.txt", "rt", stdin); int n, cnt=0, lt, rt, current, k=1; scanf("%d", &n); while(lt!=0){ lt=n/(k*10); current = (n/k)%10; rt = n%k; //printf("lt: %d\tcurr: %d\trt: %d\n", lt, current, rt); if(current>3) cnt+=(lt+1)*k; else if(current 이런 식으로 경우의 수를 계산! 5 3 6 7 십의자리를 계산한다? 3가지 방법이 있음!! -> 십의자리 숫자가 3보다 크냐/같냐/작냐? 5 3 6 7 ====..

#include #include #include using namespace std; //int main(){ ////freopen("input.txt", "rt", stdin); //int n, i, res=1, cnt=0, max=-2147000000; //scanf("%d", &n); //for(i=2; i0){ //if(res%10==0) { //cnt++; //if(cnt>max) max=cnt; //} //else cnt=0; //res = res/10; //} //printf("%d", max); // //return 0; //} //오버플러우 발생.. -> 소인수 분해 활용. 2와 5의 갯수를 세면 된다 int main(){ //freopen("input.txt", "rt", stdin);..