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을 직접 구현해 보고 후기를 공유하도록 하겠습니다.

몇일 전 오랜 친구들과 휴가와 같은 시간을 보내다, skysign이 알고리즘 스터디를 한다는 것을 알았습니다.  작은 소모임 처럼 운영하고 있기에 저도 같이 참가를 하기로 약속 하였습니다. 벌써 웹사이트도 운영하고 있어서 관심 있는 분은 이쪽으로 ~ https://skysign.github.io/WSTT WSTT가 뭔가 봤더니 웹사이트 제목에 크게 써져 있네요. 기술인 답게 약자를 좋아하는 군요. 궁금하시다면 링크를 클릭~

지금은 DP를 공부하고 있다고 해서 기억을 더듬어 보니, 몇해 전 중동 보안 업체 면접 문제중 한 가지가 떠오릅니다. 당시 머리속에 아무 생각도 나지않아 부끄럼 가득한 솔루션을 끄적이고는 돌아서야 했던 아픔이 떠오르네요. 유명한 Palindrome substring 관련된 문제입니다. 그 당시는 입력된 string이 Palindrome인지 확인을 하는 간단한 알고리즘 구현이 면접 문제였습니다.

Skysign이 공부하고 있는 topcoder와 여러 싸이트를 보니 왠지 전문적인 분위기라, 조금 접근하기 쉬운 싸이트를 찾아보았습니다. LeetCode ! http://leetcode.com/ 사이트가 간결하고, 알고리즘 문제들에 대한 팁과 솔루션도 함께 쉽게 확인 가능하게 운영되는 싸이트 입니다. 도전해 보고 싶은 알고리즘으로 (예를 들면 Dynamic programming)으로 찾거나 아래와 같이 문제의 이름으로도 쉽게 검색이 가능합니다.

그동안 코딩을 손놓은지 10년차가 되다 보니, 기본적인 코딩 부분에서 헤매기 시작합니다. 

Visual C++에서 기본 standard string class 추가 조차 구글형의 힘을 빌려 찾아봐야 하는 상황이라니... 지금은 암담하지만 skysign의 노력하는 모습을 보며 저도 마음을 다잡아 봅니다. 한참을 고생하다 LeetCode site에서 바로 코딩하고 컴파일 결과 확인까지 할 수 있다는 것을 알고는 바로 visual c++을 닫!!

위처럼 문제에 대한 간단한 설명이 왼편에 나타나고, 오른편은 자신이 선호하는 언어로 곧바로 코딩을 시작할 수 있습니다. (회사에서 모바일로 접속하여도 충분히 코딩 가능한 화면 구성이였습니다. 블루투스 키보드로 직상 상사분들 몰래...)

 가능하면 Descrition 하단의 Hint만 보고 해결책을 연습장등에 고민해 보는 것을 추천드립니다. 하지만... 저는 한참을 고민해봐도 텅빈 머리속에 정적만 흐를 뿐이라 부끄럽게도 옆의 Solution 부분을 꼼꼼히 읽어 보았습니다. 일종의 컨닝이죠~

꼼꼼히 읽어보고서는 연습장에 solution에서 설명된 규칙을 바탕으로 예제를 손으로 따라가며 그려 보았습니다. 뭔가 열심히 한 것 같지만 그냥 지저분한 낙서 처럼 보이네요. 

이제는 정리해본 알고리즘을 코드로 옮기는 순서입니다. 다른 coding 웹서비스들도 유사하겠지만, Leetcode에서도 곧바로 compile 뿐 아니라 친절하게 error가 난 부분까지 표시를 해주는 기능이 있었습니다. 오랜만에 다시 코딩을 하는 저로서는 각 라인별 debugging (각 변수값을 실시간 표시) 까지 지원해주는 편안함에 세상이 정말 많이 변했음을 타이핑 하며 느끼게 되었습니다. 편함

어이없는 코딩 실수들을 부지런히 고치다보니 드디어 [Accepted] 의 순간을 맞이하게 되었습니다. ㅠ.ㅠ 그동안의 게으름 순간 부끄럽게 느껴지는 순간입니다. 매일 조금씩이라도 생활 코딩을 할 수 있는 환경이 있다는 점에 절로 감사가 나옵니다. 늘 그렇듯 습관처럼 코드 리뷰 없이 당당히 [Submit] 버튼을 눌러봅니다. 드디어~~~!!

기다렸다는 듯이 Runtime Error가 발생합니다. 제가 로켓사이언스나 생명을 다루는 것과 관련된 IT에 종사하고 있었다면 어찌되었을지 순간 섬뜩해집니다. 열심히 코드를 뒤져서 결국 '예외처리'를 하나도 하지 않았다는 것을 알게 되었습니다.  

다시한번 마음을 가다듬고 다시한번 [Submit]을 해봅니다. 생각보다 매우 친절하게 성적표가 나왔습니다. Solution을 커닝해서 작성해본 코드였지만 그래도 이 성적표를 보고 있으니 나름 뿌듯해지네요. 그래도 아직 코딩인구이 절반 정도 수준은.. ^^*** 

실행속도가 전체의 57% 수준이라는 것은 아직도 개선의 여지가 많이 있음을 의미할듯합니다. Dynamic programming 알고리즘을 참조하여 코드를 작성하여 현재 O(n^2)의 성능인데, Leetcode에서는 친절하게 O(n)의 알고리즘도 소개해 주고 있습니다. 이제부터 조금씩 이 알고리즘들을  WSTT https://skysign.github.io/WSTT 스터디그룹과 함께 알아가보도록 해요~