2018 카카오 코딩테스트 - 캐시

https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

카카오 신입 공채 1차 코딩 테스트 문제 해설

3번 문제 캐시를 풀어보겠습니다.

 

 

3. 캐시(난이도: 하)

---

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

입력 형식

---

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력 형식

---

• 입력된 도시이름 배열을 순서대로 처리할 때, “총 실행시간”을 출력한다.

조건

---

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

입출력 예제

---

 

생각해보기

---

LRU알고리즘을 사용하여 해당 문제를 해결하여야 합니다.

LRU알고리즘은 페이지 교체알고리즘중 한 방법입니다. 가장 최근에 사용한것이 다시 사용될 가능성이 높다고 판단하여, 가장 오래전에 사용한 페이지를 교체하는 방식입니다.

자세한내용은 아래 링크를 참조하세요.

https://j2wooooo.tistory.com/121

LRU 알고리즘 (Least Recently Used Algorithm)

가장 오래전에 사용한것을 교체하는 알고리즘이므로, 이 알고리즘을 구현하기 위해서 어떤 자료구조를 사용할지 고민했습니다. 

먼저, Queue입니다. FIFO 가장 먼저 들어온것이 가장 먼저 나가게 됩니다. 단순히 생각해보면 어떤 것이 가장 오래전에 hit 하였는지 따로 기록을 하지 않아도 됩니다. 가장 오래전에 입력한 페이지는 가장 먼저 pop되기 때문입니다. 하지만, 문제는 양끝에서만 입력과, 출력이 가능하다는점과, 탐색을 할수 없다는 것 입니다. hit되었는지 판단하기 위해서 캐시를 search해주어야하는데, Queue에서는 추가적인 구현이 없이는 탐색이 되지않습니다. 또한, 양끝이 아닌 큐의 가운데에 있는 메모리가 hit할경우, hit한 메모리만 따로 제거하여 다시 push해주는 것이 불가능합니다.

 

그렇다면 이를 구현하기위해서는 어떤 자료구조를 사용하여야 할까요?

1.  search가 가능해야합니다. hit인지 miss인지 판별하기위해 찾고자하는 data가 자료구조에 들어있는지 확인할수 있어야 합니다
2. 순서가 필요합니다. 가장 오래된것을 왼쪽에 두고 가장 최근에 사용한 data를 가장오른쪽에 두어, 페이지 교체가 일어났을때, 별도의 추가적인 조작없이 가장 왼쪽의 것을 삭제하고 가장오른쪽에 추가할 수 있어야합니다.
3. 구조의 양끝단 뿐만아니라 가운데 위치한 data를 가장 우측으로 이동할 수 있어야합니다. 

list와 vector가 이에 대한 조건을 만족하였습니다. 그렇다면 list와 vector는 어떤차이가 있고, 이 문제에서 어떤 자료구조가 더욱 효율적인지 고민해봐야합니다.

https://loadofprogrammer.tistory.com/76

★ 1. STL Vector와 List 설명 및 장단점

list의 장점은 어느 위치에서든 제거가 빠르다는 것입니다. 포인터를 통해 연결되어있기에, 제거시 포인터가 가리키는 곳만 변경해주면 되어서 제거가 빠릅니다. 하지만, 특정원소에 접근하려면 처음이나 끝부터 차례대로 탐색해야만합니다.

vector의 장점으로는 양끝에서의 제거와 삽입이 빠르고, 개별 data에 대한 접근속도가 빠르다는 것입니다.

해당 문제의 경우에는 캐시사이즈가 작고 miss가 많아 양끝단에 데이터를 추가하고 삭제하는 일이 많이 발생합니다. 따라서 이 문제의 경우에는 vector를 사용하는것이 좀더 적합하다고 판단했습니다.

 

구현

---

main에서 입력된 데이터를 paging 함수로 넘겨주어 경과시간을 return하도록 만들었습니다.

main에서 cities를 넘겨줄때 주의하여야 합니다.

http://studymake.blogspot.com/2015/05/blog-post_5.html

C/C++에서 배열을 함수의 인자로 넘기는 방법

배열을 넘겨주는것이 아니라 배열의 시작주소를 넘겨주기때문에, 배열의 크기가 필요한경우 꼭 배열의 크기또한 같이 넘겨 주어야합니다. 

 

이를 vector를 사용한 cache로 구현하여주면 됩니다.

vector에 대한 내용은 아래 링크를 참조하였습니다.

https://blockdmask.tistory.com/70

[C++] vector container 정리 및 사용법

 

코드

---

https://github.com/psg2021/KAKAOtest/blob/master/2018_1st/2018_1st/Cache.cpp

psg2021/KAKAOtest

 

후기

---

점점 내용이 짧아지는것 같기도 하다.

이문제의 경우 LRU를 어떻게 구현하여야 효율적일까에 대해 고민을 많이 했었다.

지금은 어떤 자료구조가 어떤곳에서 어떤효율을 내는지 한번에 알기 힘들지만, 열심히 하다보면 언젠가 한번에 알아보는 고수가 되지않을까.