22.04.07. 풀었던 문제들

1. 캐시

충격적이다... range for문은 값을 변경해도 변경되지 않는다고 한다. 예를 들어 아래와 같은 코드를 실행해도 arr에서 값이 1인 element의 값은 그대로 1이다. 왜냐하면 range loop에서 값은 복사된 값이기 때문이라고 한다.

for(int elem : arr){
    if(elem == 1) elem = 0;
}

이를 방지하기 위해 reference를 사용하면 된다.

for(int &elem : arr){
    if(elem == 1) elem = 0;
}

풀이는 간단하다. LRU를 구현하면 된다.

"city가 cache안에 있다면, 해당 city의 참조값을 0으로 둠. 없다면, 참조값이 제일 큰 것의 위치에 넣음. 이후 모든 lru 수치를 1 더함."으로 구현하면 된다.

​

​

2. 뉴스 클러스터링

multiset의 intersection, union을 다루는 문제. 이 알고리즘 알고리즘을 어디서 봤는데.. 아마 C++로 구현하는 자료구조와 알고리즘이었던 걸로 기억한다. 추억 생각난다.