DailyBread

 오늘은 LeetCode에서 가장 Easy한 문제를 선택해 보았습니다. Day-01 편에서 DP 문제 중 Longest Palindromic Substring을 확인해 보았으나, 아직은 DP를 이야기하기는 제 수준이 한참 미달이기에 [two sum] 문제를 살펴보겠습니다. 숫자열을 입력을 받아서 두 수를 더했을때 목표 target 값이 되는 인덱스를 구해야 하는 비교적 쉬운 문제입니다.

링크는 여기에 https://leetcode.com/problems/two-sum/

텅빈 머리로 열심히 고민해 보았지만 딱히 떠오르는 건 Brute force solution 입니다. 말 그대로 야만적이고 무차별적인 솔루션이죠. 고민따위는 없는 O(N^2) 성능의 코드입니다. 아래처럼 for 문 2번 돌면서 일일이 다 비교해 보기입니다.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i=0, j=0;
        vector<int> result;
        result.empty();
        
        for (i=0;i<nums.size()-1;i++) {
            for (j=i+1;j<nums.size()-1; j++){
                if ( nums[i] + nums[j] == target ) break;
            }            
            if ( nums[i] + nums[j] == target ) break;
        }
        
        result.push_back(i);
        result.push_back(j);
                
        return result;        
    }
};

 C++ STL 문법은 아직 익숙하지 않기에 열심히 구글링을 해서 Vector를 선언하고, push_back이라는 class member function도 사용해 봅니다. 실행 결과는 무려 148ms 나 시간이 걸리는 군요. 어떻게 하면 좀더 최적화를 할 수 있을까요? 고민해 봅시다. 잠시.. 딴생각말고.. Brain을 다시 insert.

일단 for 문을 빠져 나오기 위해 if 문을 2번이나 반복해서 쓴 부분이 지저분해 보입니다. 그리고 return 값으로 vector를 내보내기 위해 push_back 멤버함수를 각각 2번 호출한 것도 눈에 거슬리는 군요. 저희의 영원한 희망, LeetCode solution을 참조하여 조금 fancy하게 바꾸어 봅시다.

 아무래도 일일히 for 문을 도는 것보다는 STL library에서 제공되는 API들이 조금더 튜닝이 되었을 꺼라는 희망에, itererator로 find와 distance 함수를 사용했습니다. 그리고 굳이 break할 필요 없이 vector 타입으로 곧바로 return을 하도록 변경 하였습니다. iterator라는 개념이 아직은 생소하지만 조금 있어 보이기는 하네요. 자~ 과연 성능에 변화가 있을까요? 부푼 꿈을 안고,

class Solution {
public:
    vector<int> twoSum(vector<int>&nums, int target) {
        int i=0, j=0, sub=0;
        vector<int>::iterator start, iter;
        
        start = nums.begin();
        
        for (i=0;i<nums.size()-1;i++){
            sub = target - nums[i];
            start++;
            iter = find( start, nums.end(), sub);
            j = distance(nums.begin(), iter);
            
            if ( j!=0 && j < nums.size() ) {
                return vector<int> { i,j };
            }
        }
        return result;        
    }
};

 
148ms에서 96ms 만큼 개선이 되었으니 무려 50ms 정도 개선이 되었네요... 라고 말할 수도 있고 굳이 %로 계산을 하면35%이상~ 좀더 위로가 될까요? 하지만 여전히 Time complexity 는 O(n^2) 입니다. Brute force 알고리즘의 근본적인 해결책이 필요한 것이죠.

 이럴때는 생각의 전환이 필요합니다. index를 하나 정하고, 남은 값들 중에서 목표 값을 한번에 찾을 수 있는 방법이 필요합니다. 일일이 전체 배열을 다 뒤지지 않고서요. 우선 적으로 떠오르는 교과서 적인 생각은,

1. 현재 자료를 뭔가 다른  값으로 바꾸어 표현해 본다.

2. 현재 배열로 되어 있는 자료 구조를 변경해 본다.

3. 항상 시간과 공간은 trade off라는 말이 있으니, 빠르게 동작하기 위해 메모리를 더 쓰는 방법을 생각해본다.

이 정도가 떠오릅니다. 또 어떤 방법이 있을까요?

 예를 들어서 입력이 {1,4,7,3,5} 이 있고 target이 9라고 가정해 봅시다. 첫번째 인덱스 0의 값 1를 선택하면, 나머지 구성요소에서 9-1=8이 되는 값을 찾아야 합니다. 저희가 찾아야 하는 것은 8이라는 값이 있는 위치(index)입니다. 일단 눈으로 보면 8이 없으니 다음 인덱스 1에 해당하는 값인 4를 선택해 봅시다. 9-4=5 이니까 5의 위치를 어떻게 한번에 알 수 있을까요? 노트 등에 생각을 한번 그려보세요.

1번의 확장으로, 현재 값들에 뭔가를 더하거나 빼거나 나누거나 등의 방법으로 바꾸면 개선이 될 수 있을까요?

2번의 확장으로, 배열을 다른 자료 구조로 바꾼다면.. linked-list? tree? set? hash?

3번의 확장으로, 어떤 방법이 있을까요? 메모리를 더 써서 한번에 5가 되는 값을 찾을 수 있나요?

Hash Map을 이용하는 방법이 있습니다. 현재 입력값은 아래와 같은 속성들을 갖고 있다고 볼 수 있습니다.

 value 값을 hash key 값으로 생각하고, index (우리가 찾고자 하는 값)를 아래처럼 넣어 둘 수 있습니다.

위의 배열에서 5라는 값의 위치를 찾으려면, 0부터 하나씩 찾아서 맨 끝까지 가야겠지만, 아래 hash table에서는 table[5]로 곧바로 접근해서, 저장해둔 index 값을 알 수 있게 됩니다.

 이제 다시 코드로 옮겨 볼 시간입니다. 아직 C++ STL library에 익숙하지 않아서 또 한참 구글형의 힘을 빌어 봅니다. STL library에는 hash_map이 올라가 있지 않네요. hash를 써서 빨리 접근 가능한 자료구조는 unordered_map 이라는 것을 알게 되었습니다. 평소에 자주 써보지 못한 container라 혹시 잘못된 정보라면 언제든지 댓글로 알려주세요. 개선을 위한 태클은 언제든지 환영입니다. 

#include <unordered_map>

class Solution {
public:
    vector<int> twoSum(vector<int>&nums, int target) {
        int i=0, sub=0;
        unordered_map <int, int> map;
        unordered_map <int, int>::iterator iter;
        vector<int> result={0,0};
               
        for (i=0;i<nums.size();i++){
            sub = target - nums[i];
            
            iter = map.find(sub);
            if( iter != map.end() ){
                return vector<int>{ iter->second, i };
            }
            map[nums[i]] = i;
        }
    
        return result;        
    }
};

 
성능이 기존 96ms에서 8ms로 매우 비약적으로 빨라진 것을 알 수 있습니다. for문이 한번 사용되었고 unordered_map이 hash로 한번 접근이 있었다고 하면 time complexity는 O(n)이 되었습니다. 결과 리포트에서 또 특이한 점을 찾으셨나요? 사용된 메모리 공간 변화는 어떻나요? unordered_map을 사용해서인지 메모리 사용량이 늘어 난 것을 알 수 있습니다. 앞서 개선을 위해 3가지 정도 고민했던 사항들이 모두 연관되어 있다는 것을 느끼셨나요?

 2일차에는 예제들에서 볼 수 있듯이 C++과 조금 더 친해지기 위해 Vector, Unordered_map 그리고 iterator 등을 사용해 보았습니다. Vector와 map은 C++에서는 container라고 부릅니다. 다른 데이터 형을 포함할 수 있기에 class template 형태로 구현된 것을 알 수 있습니다. 이 container의 구성요소들에 접근하기 위해서는 직접 접근할 수도 있겠지만 무슨 이유에서인지 iterator라 불리우는 반복자(?)를 사용합니다. 녹슨 coder인 제가 볼때는 일종의 포인터로 보입니다. 아마 객체지향적인 언어를 지향하기 위해 특정 형태에 종속되어 사용되지 않기 위해 나온 개념이겠죠? 객체 지향으로 넘어가면서 많이 복잡한 용어들을 사용하는 군요. Container들을 상속받아서 더 복잡한 구조를 만드는 것들은 Container adapter 라고 부릅니다.

 이렇게 정리를 하고 skysign님과 간단히 WSTT 미팅을 하였습니다. WSTT가 뭔지 궁금하신 분은 https://skysign.github.io/WSTT를 클릭해 보세요. 어떤 언어로 알고리즘을 연습하는게 좋을지 매우 근복적이 질문이 있었습니다. 제가 숙제로 해본 언어가 주로 C라 C++로 계속 탐험을 할지, JAVA나 Phython으로 갈 지에 대한 문제가 있군요. 고민 끝에 전 욕심이 많은 편이라 당분간은 C++과 JAVA의 기본 문법 혼합하여 남은 여정을 이어가도록 하겠습니다.

 망각의 언덕 저편으로 사라졌던 녹슨 코딩의 기억을 어떻게 하면 틈틈히 되살릴 수 있을까요? 빡센 군대 스타일, 특별 과외 등 여러가지 방법이 있겠지만, 주 54시간 근무 규정 따위는 적용되지 않는 회사의 노예로 특별한 시간을 내기 힘든 회사원으로서 Skysign님이 추천해주신 아래 site를 저 또한 매우 강추합니다. 

https://www.hackerrank.com/

짧은 글이지만 읽어 주셔서 감사합니다. 다음 시간에는 Skysign님이 WSTT offline에서 간략히 설명해주신 coin change algorithm을 직접 구현해 보고 후기를 공유하도록 하겠습니다.