32강~37강

원래벌레·2022년 4월 9일

32강

접근법 :

for(i=0;i<n-1;i++){
	idx=i;
	for(j=i+1; j<n ; j++){
    	if(a[j] < a[idx]) idx=j;
    }
    tmp=a[i];
    a[i]=a[idx];
    a[idx]=tmp;
 }

idx를 i라고 두고, j는 i+1로 두고, i를 기준으로 j를 돌면서 i~j까지의 최솟값을 구하고, 구한 최솟값의 idx 데이터 값과, i 데이터 값을 바꿔준다.

34강

접근법 :

버블정렬
버블정렬은 인접한 두수를 비교한다. for문은 n-1번까지만 돌면 된다. 왜냐하면 두수를 비교하기 때문에 마지막을 비교하면 마지막 앞자리수와 마지막 수를 비교하게 된다.
버블정렬은 맨 뒤부터 정렬이 된다. j for문이 돌 때, j의 값은 j < n-i-1 일 때 까지 돈다.

36강

접근법 :

for(i=1;i<n;i++){
	tmp=a[i];
	for(j=i-1;j>=0;j--){
    		if(a[j] > tmp) a[j+1]=a[j];
            else break;
    }
    a[j+1]=tmp;
 }

i 인덱스 데이터와 i 인덱스 앞쪽 데이터 간의 비교를 한다.
먼저 tmp 변수에 a[i]를 저장해둔다.
그리고 a[i] 의 값과 a[j]의 값을 비교해서, 만약에 a[j] 가 tmp 보다 값이 크면 a[j+1]=a[j] 즉 한칸을 뒤로 밀어준다. 그러면 같은 값을 가진 데이터가 두개가 있는 형태가 된다.
그리고 만약에 tmp가 더 값이 크다. 그러면 break을 통해서 for문을 나오고 j+1 인덱스의 값에다가 tmp 값을 넣어준다.

37강

접근법 :

캐시미스, 캐시히트 문제
먼저 캐시 미스인지, 캐시 히트인지를 알아야 한다. 이를 해결하는 코드는 for문을 캐시의 크기만큼 돌면서 현재 작업 하려는 것의 번호가 있는지를 확인 하면 된다.
먼저 position = -1 이라고 선언을 해주고, 위에서 말했던 작업을 하면서 만약에 내가 지금 작업 하려는 번호와 같은 번호가 캐시에 있다면 캐시의 해당 인덱스를 position에 저장을 해준다. 그렇지 않다면 -1을 유지해준다.
여기서 이제 position 값이 -1 이라면, 캐시 미스가 일어나고 -1이 아니라면 캐시히트가 일어난 것이다.
여기서 캐시 미스가 일어났다면, 현재 캐시 안에 내가 하려는 작업의 번호가 없는 것이다. 그렇기 때문에 맨 뒤의 값부터 인덱스 번호 1번까지 값을 뒤로 한칸씩 땡겨 준다. 그리고 0번 인덱스에 지금 작업하려는 것을 넣어준다.
만약에 position 값이 달라져서 캐시 히트가 일어 났다면, 해당 position 인덱스부터 1까지 한칸씩 뒤로 밀어준다. 그리고 작업 하려던 값을 0번째 인덱스에 넣어준다.

학습한 내용을 담은 블로그 입니다.

32강