ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 카카오 1차 온라인 코딩테스트 3번 문제(17.09.16)
    💻 프로그래밍/알고리즘 2017. 10. 7. 02:23

    안녕하세요!! 코딩하는 JAY 입니다~:D 


    다들 추석연휴 잘 보내고 계신가요?!ㅎㅎ 저는 추석 동안 친구들 만나러 다니느라 정신 없었습니다 ㅎㅎ


    이제 연휴도 얼마 안남았는데요 ㅜㅜ 남은 연휴 잘 보내시길 바랍니다~


    자! 오늘은 '카카오 1차 온라인 코딩테스트 3번 문제'를 풀어보도록 하겠습니다.


    문제 및 풀이 링크 : http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/


    3. 캐시(난이도: 하)


    - 입력 형식

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

    - 출력 형식

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

    - 조건

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

    - 입출력 예제

    캐시크기(cacheSize)도시이름(cities)실행시간
    3[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”]50
    3[“Jeju”, “Pangyo”, “Seoul”, “Jeju”, “Pangyo”, “Seoul”, “Jeju”, “Pangyo”, “Seoul”]21
    2[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “SanFrancisco”, “Seoul”, “Rome”, “Paris”, “Jeju”, “NewYork”, “Rome”]60
    5[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “SanFrancisco”, “Seoul”, “Rome”, “Paris”, “Jeju”, “NewYork”, “Rome”]52
    2[“Jeju”, “Pangyo”, “NewYork”, “newyork”]16
    0[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”]25

    내용은 대략 이렇습니다.

    이문제의 경우에는 LRU(Least Recntly Used)라는 알고리즘을 알아야지 풀 수 있는 문제입니다.(뭐, 몰라도 검색이 가능했기 때문에 큰 문제는 없습니다.)


    간단히 요약하자면 캐시 메모리에서 가장 최근에 사용하지 않은 페이지를 교체하는 알고리즘입니다.

    쉽게 말하면 스택, 큐 같은 느낌인데 거기에 메모리 마다 사용시간을 부가하여 캐시메모리에 새로운 데이터가 들어올때마다 가장 사용시간이 낮은 데이터를 새로운 데이터와 교체하는 것 입니다.(?).. 뭔가 말이 어렵긴 했지만... 위 URL을 참고하시면 쉽게 이해가 갈 것입니다.
    카카오 이모티콘에 대한 이미지 검색결과
    (여러분은 이해하실 수 있을 겁니다.. 암... 죄송해요.. 설명을 잘 못해서ㅜㅜ)


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    #include <iostream>
    #include <string>
    #include <vector>
     
    #define    cacheHit    1
    #define cacheMiss    5
     
    using namespace std;
    int cacheCheck(int cacheSize, int* cacheFrequency, vector<string> &cache, string data);
    int solution(int cacheSize, vector<string> cities);
    int main(void)
    {
        int testCase;
        string arr[] = {"Jeju""Pangyo""Seoul""NewYork""LA""Jeju""Pangyo""Seoul""NewYork""LA"};
        string arr1[] = {"Jeju""Pangyo""Seoul""Jeju""Pangyo""Seoul""Jeju""Pangyo""Seoul"};
        string arr2[] = {"Jeju""Pangyo""Seoul""NewYork""LA""SanFrancisco""Seoul""Rome""Paris""Jeju""NewYork""Rome"};
        string arr3[] = {"Jeju""Pangyo""NewYork""newyork"};
        string arr4[] = {"Jeju""Pangyo""Seoul""NewYork""LA"};
        vector<string> citi(arr, arr + (sizeof(arr) / sizeof(arr[0])));
        vector<string> citi1(arr1, arr1 + (sizeof(arr1) / sizeof(arr1[0])));
        vector<string> citi2(arr2, arr2 + (sizeof(arr2) / sizeof(arr2[0])));
        vector<string> citi3(arr3, arr3 + (sizeof(arr3) / sizeof(arr3[0])));
        vector<string> citi4(arr4, arr4 + (sizeof(arr4) / sizeof(arr4[0])));
     
        testCase = solution(3, citi);
        testCase = solution(3, citi1);
        testCase = solution(2, citi2);
        testCase = solution(5, citi2);
        testCase = solution(2, citi3);
        testCase = solution(0, citi4);
     
        return 0;
    }
     
    int solution(int cacheSize, vector<string> cities) 
    {
        int answer = 0;            // 실행 시간
        int *cacheFrequency = new int[cacheSize + 1]; // cache 발생빈도(사용시간)
        
        vector<string> cache(cacheSize);
        memset(cacheFrequency, 0sizeof(cacheFrequency) * cacheSize);
        
        // string process
        int size = cities.size();
        for(int i = 0; i < size; i ++) {
            // cache안의 내용을 체크
            answer += cacheCheck(cacheSize, cacheFrequency, cache, cities[i]);
        }
     
        /************ 결과 확인하기 위한 코드 ************/
        cout << "citi size : " << size << endl;
        cout << "cache size : " << cache.size() << endl;
        cout << "runtime : " << answer << "\n" << endl;
        /*********************************************/
     
        delete cacheFrequency;
        
        return answer;
    }
     
    int cacheCheck(int cacheSize, int* cacheFrequency, vector<string> &cache, string data)
    {
        unsigned int lowFreCache = 0// 가장 빈도수가 낮은 캐시 순서
        int runTime = 0;               // cacheHit or Miss
        
        // 가장 사용 빈도수(시간)가 낮은 캐시 순서 체크
        for(int i = 0; i < cacheSize; i ++) {
            if(cache[i] == "") {
                lowFreCache = i;
                break;
            } else if(cacheFrequency[i] < cacheFrequency[lowFreCache]) {
                lowFreCache = i;
            }
        }
        
        //  Cache Hit
        for(int i = 0; i < cacheSize; i ++) {
            if(!stricmp(cache[i].c_str(), data.c_str())) { // 대소문자를 구분하지 않고 문자열 비교
                cacheFrequency[i] += 1// cache 사용(빈도)수 증가
                runTime = cacheHit;
                return runTime;
            } 
        }
        
        // Cache Miss 
        if(cacheSize) { // cache가 1개라도 있을 경우만 새롭게 캐시 넣음
            for(int i = 0; i < cacheSize; i ++) {
                if(i != lowFreCache) cacheFrequency[i] -= 1;
            }
            cache[lowFreCache] = data;
            cacheFrequency[lowFreCache] = 1// 빈도 증가
        }
     
        runTime = cacheMiss; // 캐시안에 문자열이 없으므로 cacheMiss
        
        return runTime;
    }


    코드를 보시면 아시겠지만, cacheCheck함수에서 캐시사이즈, cache hit, miss 등을 판단하여 그에 따라 runtime을 계산하도록 코드를 짰습니다.


    stricmp 이 함수는 문자열을 비교할 때 대소문자를 구분하지 않고 비교합니다!!(스..스고이)


    저는 이런 함수가 있는지는 몰.....랐지만 왠지 대소문자 구분하지 않는 것 ...쯤은 라이브러리가 있을 것이다라는.. 촉(?)으로 구글링 해보니...


    떡하니 저렇게 함수가 있었더라고요!!(역쉬 MS)


    튼 결론적으로 3번문제도 LRU알고리즘이라는 것만 안다면 크게 어렵지 않게 풀 수 있는 문제였습니다.


    이상으로 오늘의 알고리즘 포스팅을 마치겠습니다~~ 여러분 재밌는 코드 생산하세요!!


    (혹시 문제풀이가 잘못되었거나 소스코드 동작이 이상하다면 댓글로 조언해주시면 감사히 배우겠습니다!! 저도 배워가는 입장이라 많이 부족하지만 여러분 들과 함께 공부하면서 서로 윈윈하며 좋은 개발자가 되고싶습니다!!)



    댓글

운동하는 개발자 JAY-JI