DailyBread

https://programmers.co.kr/learn/courses/30/lessons/64063

First trial code :

#include <string>
#include <vector>
using namespace std;

long long find(long long room, vector<long long>& selected) {
    if (room == selected[room]) return room;
    else {
    	// Update the last empty room resursively
        selected[room] = find(selected[room], selected);
        return selected[room];
    }
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer(room_number.size());
    vector<long long> selected(k+1LL);

    long long targetRoom = 0;
    long long nextRoom = 0;
    long long i = 0;

	//Initiate 'selected' array to indicate the assignment
    for (i = 0; i <= k; i++) selected[i]=i;

    for (i = 0; i < room_number.size(); i++) {
        targetRoom = find(room_number[i], selected);
        answer[i] = targetRoom;
        nextRoom = 0LL;
        
        if (targetRoom + 1LL <= k) {
            nextRoom = find(targetRoom + 1LL, selected);
        }
        selected[targetRoom] = nextRoom;
    }
    return answer;
}

But this code has been failed with 'memory excess'

Why it has failure with big memory usage ? 'find' function will have too many resursion ?

It's because 'selected' vector should be allocated for very big number.  (1 <= k <= 10^12)

So, only to allocate required rooms, 'map' will be good choice to use.

#include <string>
#include <vector>
#include <map>
using namespace std;

long long find(long long room, map<long long, long long>& selected) {
    map<long long, long long>::iterator it;
    long long lastRoom;
    
    it = selected.find(room);
    
    // If the room is no in the map, that's the last one
    if ( it == selected.end() ) return room;
    else {
        // If the room is in the map, check next room
        lastRoom = find(it->second , selected );
        // update every room's next to last one
        it->second = lastRoom;
        return lastRoom;
    }
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer(room_number.size());
    map<long long, long long > selected;

    long long targetRoom = 0;
    long long i = 0;

    for (i = 0; i < room_number.size(); i++) {
        targetRoom = find(room_number[i], selected);
        selected.insert(make_pair(targetRoom, targetRoom+1LL));
        answer[i] = targetRoom;        
    }
    return answer;
}

We can try this problem using 'union find' method also.

매우 간단한 DP 문제 부터 확인해보도록 하겠습니다.

https://leetcode.com/problems/climbing-stairs/

한번에 1개 혹은 2개의 계단만 오를 수 있다고 가정할때, 총 N개의 계단을 올라갈 수 있는 가지수를 구하는 문제입니다.

아무리 문제만 바라보고 있어도 뾰족한 수가 떠오르지 않으니 가능한 방법들을 노트에 직접 구해보았습니다. 머리가 스마트 하지 않으면 손과 발이 고생이라라던 옛 현인들의 말씀이 순간 떠오르는 군요. 언젠가는 조금이라도 스마트해진 브레인이 되길 바라는 마음에 맘 굳게 먹고~!

 규칙이 보이시나요? S1=1, S2=2, S3=3, S4=5, S5=8, S6=13 즉 Sn = Sn-1 + Sn-2 의 규칙을 갖는 fibonacci 수열임을 알 수 있습니다. 이를 우선 생각나는대로 아래와 같이 코딩해 보았습니다. 보기에도 깔끔하고 음 나름 괜찮게 작성한 것 같습니다. 별 문제 없겠죠 ? 일단 Submit을 눌러봅니다...

class Solution {
public:
    int climbStairs(int n) {
        if (n==0) return 0;
        if (n==1) return 1;
        if (n==2) return 2;
        return climbStairs(n-1) + climbStairs(n-2);
    }
};

 Time Limit Exceeded ?? 수행 시간이 너무 오래 걸리는 코드라서 바로 Fail되었습니다. Time Complexity를 따져 보아야 할 듯합니다. 어림잡아서 tree 맨 아래 쪽 까지 내려간다고 했을때 대략 O(2^n)의 시간이 걸리는 코드였군요. 머리가 스마트하지 않았더니 CPU core가 고생하는군요.

 어떻게 하면 수행 시간을 단축 시킬 수 있을까요? 위의 트리를 봐도 중복되는 연산 단계들이 매우 많음을 알 수 있습니다. 이전에 계산했던 값들을 어딘가에 적어두고, 또 계산을 해야 하는 경우 곧바로 읽어 올수 있다면 연산 속도가 줄어들것 같다는 생각이 듭니다. 굳이 영어로 Memoization 이라고 합니다. DP를 공부할때 매우 자주 나오는 용어이죠. DP 알고리즘을 적용하려면 문제에 아래와 같은 특성이 있어야 합니다.

• Overlapping Subproblem : 큰 문제를 풀때 작은 문제의 풀이 방법과 동일하게 풀 수 있음
• Optimal Substructure : 작은 문제의 결과 값이 항상 같아야 한다.

 이전 연산 값을 사용하도록 코드를 바꾸어 보았습니다. 뭔가 지저분해 보이지만 계단 N의 가짓수를 구하기 위해, 0번부터 위로 올라가며 계산하는 이런 방식을 Bottom-up 방식이라고 합니다.

class Solution {
public:
    int climbStairs(int n) {
        
        int i=0;
        int prevStep1, prevStep2, prevStep;
        
        if (n==0) return 0;
        if (n==1) return 1;
        if (n==2) return 2;
        prevStep1 = 1;
        prevStep2 = 2;
    
        for (i=3;i<=n;i++){
            prevStep = prevStep1+prevStep2;
            prevStep1 = prevStep2;
            prevStep2 = prevStep;
        }

        return prevStep;
    }
};

취향에 따라 아래와 같이 Top-down 형태로 구현도 가능합니다. 계단 N의 가짓수를 구하는 과정을 코드 부분으로 먼저 구현되며, 실행시 N부터 거꾸로 0까지 내려가면서 구한다는 의미로 해석이 가능할듯합니다. 개인적으로는 Top-down이 읽기에는 (readability) 좀더 쉬워 보이지만 항상 recursive function을 사용 할때는 반복을 끝내는 조건을 명확하게 확인해야 합니다. 

class Solution {
public:
    int *array;
    
public:
    int calStairs(int n){
        int steps=0;

        if (n<=2 || array[n]>=0) return array[n];

        steps=calStairs(n-1)+calStairs(n-2);
        array[n] = steps;        
        return steps;
    }
    
    int climbStairs(int n) {
        int result=0;
        array = new int[n+1];
        
        if (n>=0) array[0] = 0;
        if (n>=1) array[1] = 1;
        if (n>=2) array[2] = 2;
        
        result = calStairs(n);
        
        delete[] array;
        array=0;
        
        return result;
    }
};

 문제의 성격에 따라 다르겠지만 이 예제에서는 실행속도와 사용하는 메모리 공간이 Bottom-up과 Top-down방식이 유사한 결과가 나왔네요.  Bottom-up 코드에서는 변수 2개를 추가로 선언해서 이전 결과값을 저장하면서 반복하며 사용하였습니다. Top-down 코드에서는 recursive function을 내려갈때마다 이전 결과들이 저장되어 있어야 할 것 같아서 동적 array를 사용하였습니다. 메모리 사용 공간 차이가 많이 나겠지했는데, 비슷한 메모리가 사용되네요. 그 차이는 나중에 다시 확인해 봐야 할 듯합니다. (Leetcode에서 말하는 memory usage의 의미가 무엇인지)

 c++에서는 'array = new int[n+1];' 처럼 메모리 할당을 한다는 부분을 잠시 눈여겨 보도록 합니다. 동적으로 메모리를 할당했을 때는 꼭 다시 메모리를 회수해야 합니다. 이때 'delete array'가 아닌 'delete[] array'를 사용한 부분도 꼭 확인해 보시기 바랍니다.  코드를 좀더 깔끔하게 정리해야겠지만 조금 지저분한 점 양해를 부탁드립니다.

 이번 편도 끝까지 읽어 주셔서 감사합니다. 같이 조금씩 DP 문제들을 더 알아보면서 두뇌를 좀더 Smart하게 연습시켜 보도록 해요~

 오늘은 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 스터디그룹과 함께 알아가보도록 해요~

* Source Code

#include <iostream>
#include <cstring>
using namespace std;

class myClass{

        private:
                int a;
                char *name;

        public:
                myClass(){ }
                myClass(int _a, const char *_name){
                        a = _a;
                        name = new char[strlen(_name)+1];
                        strcpy(name, _name);
                }
#if 0
                myClass(const myClass &T){
                        a = T.a;
                        name = new char[strlen(T.name)+1];
                        strcpy(name, T.name);

                }
#endif
                ~myClass(){
                        delete []name;
                }

                void showData(){
                        cout << a <<endl;
                        cout << name << endl;
                }

};

int main(int argc, char *argv[]){
        myClass A(4,"spider man");
        myClass B(A);

        B.showData();
}

* Compilation

g++ -g classbasic.cpp

* Error

[root@localhost PracticeAlgorithm]# ./a.out
4
spider man
*** Error in `./a.out': double free or corruption (fasttop): 0x080dc008 ***
======= Backtrace: =========
/lib/libc.so.6[0x4c4e9b8a]
/lib/libstdc++.so.6(_ZdlPv+0x20)[0x4d2f2940]
/lib/libstdc++.so.6(_ZdaPv+0x1c)[0x4d2f299c]
./a.out[0x80489d6]
./a.out[0x80488ea]
/lib/libc.so.6(__libc_start_main+0xf3)[0x4c48d963]
./a.out[0x80487a1]
======= Memory map: ========
08048000-08049000 r-xp 00000000 fd:02 2762798    /home/broadcom/codes/PracticeAlgorithm/a.out
08049000-0804a000 r--p 00000000 fd:02 2762798    /home/broadcom/codes/PracticeAlgorithm/a.out
0804a000-0804b000 rw-p 00001000 fd:02 2762798    /home/broadcom/codes/PracticeAlgorithm/a.out
080dc000-080fd000 rw-p 00000000 00:00 0          [heap]
4c44c000-4c46b000 r-xp 00000000 fd:01 552980     /usr/lib/ld-2.17.so
4c46b000-4c46c000 r--p 0001e000 fd:01 552980     /usr/lib/ld-2.17.so
4c46c000-4c46d000 rw-p 0001f000 fd:01 552980     /usr/lib/ld-2.17.so
4c474000-4c62c000 r-xp 00000000 fd:01 552982     /usr/lib/libc-2.17.so
4c62c000-4c62e000 r--p 001b7000 fd:01 552982     /usr/lib/libc-2.17.so
4c62e000-4c62f000 rw-p 001b9000 fd:01 552982     /usr/lib/libc-2.17.so
4c62f000-4c632000 rw-p 00000000 00:00 0
4c670000-4c6b1000 r-xp 00000000 fd:01 552996     /usr/lib/libm-2.17.so
4c6b1000-4c6b2000 r--p 00040000 fd:01 552996     /usr/lib/libm-2.17.so
4c6b2000-4c6b3000 rw-p 00041000 fd:01 552996     /usr/lib/libm-2.17.so
4c899000-4c8b4000 r-xp 00000000 fd:01 552999     /usr/lib/libgcc_s-4.8.3-20140911.so.1
4c8b4000-4c8b5000 r--p 0001a000 fd:01 552999     /usr/lib/libgcc_s-4.8.3-20140911.so.1
4c8b5000-4c8b6000 rw-p 0001b000 fd:01 552999     /usr/lib/libgcc_s-4.8.3-20140911.so.1
4d2a7000-4d388000 r-xp 00000000 fd:01 543920     /usr/lib/libstdc++.so.6.0.19
4d388000-4d38c000 r--p 000e1000 fd:01 543920     /usr/lib/libstdc++.so.6.0.19
4d38c000-4d38d000 rw-p 000e5000 fd:01 543920     /usr/lib/libstdc++.so.6.0.19
4d38d000-4d394000 rw-p 00000000 00:00 0
b779f000-b77a2000 rw-p 00000000 00:00 0
b77b6000-b77b9000 rw-p 00000000 00:00 0
b77b9000-b77ba000 r-xp 00000000 00:00 0          [vdso]
bf7e1000-bf802000 rw-p 00000000 00:00 0          [stack]
Aborted (core dumped)

* Debugging

[root@localhost PracticeAlgorithm]# gdb a.out
GNU gdb (GDB) Fedora 7.6.1-46.fc19
Copyright (C) 2013 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "i686-redhat-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /home/broadcom/codes/PracticeAlgorithm/a.out...done.
(gdb) run
Starting program: /home/broadcom/codes/PracticeAlgorithm/a.out
4
spider man
*** Error in `/home/broadcom/codes/PracticeAlgorithm/a.out': double free or corruption (fasttop): 0x0804b008 ***
======= Backtrace: =========
/lib/libc.so.6[0x4c4e9b8a]
/lib/libstdc++.so.6(_ZdlPv+0x20)[0x4d2f2940]
/lib/libstdc++.so.6(_ZdaPv+0x1c)[0x4d2f299c]
/home/broadcom/codes/PracticeAlgorithm/a.out[0x80489d6]
/home/broadcom/codes/PracticeAlgorithm/a.out[0x80488ea]
/lib/libc.so.6(__libc_start_main+0xf3)[0x4c48d963]
/home/broadcom/codes/PracticeAlgorithm/a.out[0x80487a1]
======= Memory map: ========
08048000-08049000 r-xp 00000000 fd:02 2762798    /home/broadcom/codes/PracticeAlgorithm/a.out
08049000-0804a000 r--p 00000000 fd:02 2762798    /home/broadcom/codes/PracticeAlgorithm/a.out
0804a000-0804b000 rw-p 00001000 fd:02 2762798    /home/broadcom/codes/PracticeAlgorithm/a.out
0804b000-0806c000 rw-p 00000000 00:00 0          [heap]
4c44c000-4c46b000 r-xp 00000000 fd:01 552980     /usr/lib/ld-2.17.so
4c46b000-4c46c000 r--p 0001e000 fd:01 552980     /usr/lib/ld-2.17.so
4c46c000-4c46d000 rw-p 0001f000 fd:01 552980     /usr/lib/ld-2.17.so
4c474000-4c62c000 r-xp 00000000 fd:01 552982     /usr/lib/libc-2.17.so
4c62c000-4c62e000 r--p 001b7000 fd:01 552982     /usr/lib/libc-2.17.so
4c62e000-4c62f000 rw-p 001b9000 fd:01 552982     /usr/lib/libc-2.17.so
4c62f000-4c632000 rw-p 00000000 00:00 0
4c670000-4c6b1000 r-xp 00000000 fd:01 552996     /usr/lib/libm-2.17.so
4c6b1000-4c6b2000 r--p 00040000 fd:01 552996     /usr/lib/libm-2.17.so
4c6b2000-4c6b3000 rw-p 00041000 fd:01 552996     /usr/lib/libm-2.17.so
4c899000-4c8b4000 r-xp 00000000 fd:01 552999     /usr/lib/libgcc_s-4.8.3-20140911.so.1
4c8b4000-4c8b5000 r--p 0001a000 fd:01 552999     /usr/lib/libgcc_s-4.8.3-20140911.so.1
4c8b5000-4c8b6000 rw-p 0001b000 fd:01 552999     /usr/lib/libgcc_s-4.8.3-20140911.so.1
4d2a7000-4d388000 r-xp 00000000 fd:01 543920     /usr/lib/libstdc++.so.6.0.19
4d388000-4d38c000 r--p 000e1000 fd:01 543920     /usr/lib/libstdc++.so.6.0.19
4d38c000-4d38d000 rw-p 000e5000 fd:01 543920     /usr/lib/libstdc++.so.6.0.19
4d38d000-4d394000 rw-p 00000000 00:00 0
b7fe5000-b7fe8000 rw-p 00000000 00:00 0
b7ffc000-b7fff000 rw-p 00000000 00:00 0
b7fff000-b8000000 r-xp 00000000 00:00 0          [vdso]
bffdf000-c0000000 rw-p 00000000 00:00 0          [stack]

Program received signal SIGABRT, Aborted.
0xb7fff424 in __kernel_vsyscall ()
Missing separate debuginfos, use: debuginfo-install glibc-2.17-21.fc19.i686 libgcc-4.8.3-7.fc19.i686 libstdc++-4.8.3-7.fc19.i686

// Backtrace

(gdb) bt full
#0  0xb7fff424 in __kernel_vsyscall ()
No symbol table info available.
#1  0x4c4a2687 in raise () from /lib/libc.so.6
No symbol table info available.
#2  0x4c4a3ec3 in abort () from /lib/libc.so.6
No symbol table info available.
#3  0x4c4e1f45 in __libc_message () from /lib/libc.so.6
No symbol table info available.
#4  0x4c4e9b8a in _int_free () from /lib/libc.so.6
No symbol table info available.
#5  0x4d2f2940 in operator delete(void*) () from /lib/libstdc++.so.6
No symbol table info available.
#6  0x4d2f299c in operator delete[](void*) () from /lib/libstdc++.so.6
No symbol table info available.
#7  0x080489d6 in myClass::~myClass (this=0xbffff198, __in_chrg=<optimized out>) at classbasic.cpp:27
No locals.
#8  0x080488ea in main (argc=1, argv=0xbffff244) at classbasic.cpp:41
        A = {a = 4, name = 0x804b008 ""}
        B = {a = 4, name = 0x804b008 ""}

(gdb) list
29   
30            void showData(){
31                cout << a <<endl;
32                cout << name << endl;
33            }
34   
35    };
36   
37    int main(int argc, char *argv[]){
38        myClass A(4,"spider man");
(gdb) list 28
23   
24            }
25    #endif
26            ~myClass(){
27                delete []name;
28            }
29   
30            void showData(){
31                cout << a <<endl;
32                cout << name << endl;
(gdb)

(gdb) print name
$1 = 0

(gdb) info locals
A = {a = 4, name = 0x804b008 ""}
B = {a = 4, name = 0x804b008 ""}

(gdb) info args
argc = 1
argv = 0xbffff244

(gdb) info stack
#0  0xb7fff424 in __kernel_vsyscall ()
#1  0x4c4a2687 in raise () from /lib/libc.so.6
#2  0x4c4a3ec3 in abort () from /lib/libc.so.6
#3  0x4c4e1f45 in __libc_message () from /lib/libc.so.6
#4  0x4c4e9b8a in _int_free () from /lib/libc.so.6
#5  0x4d2f2940 in operator delete(void*) () from /lib/libstdc++.so.6
#6  0x4d2f299c in operator delete[](void*) () from /lib/libstdc++.so.6
#7  0x080489d6 in myClass::~myClass (this=0xbffff198, __in_chrg=<optimized out>) at classbasic.cpp:27
#8  0x080488ea in main (argc=1, argv=0xbffff244) at classbasic.cpp:41


(gdb) info registers
eax            0x0    0
ecx            0x14da    5338
edx            0x6    6
ebx            0x4c62e000    1281548288
esp            0xbffff180    0xbffff180
ebp            0xbffff1a8    0xbffff1a8
esi            0x0    0
edi            0x0    0
eip            0x80488ea    0x80488ea <main(int, char**)+90>
eflags         0x246    [ PF ZF IF ]
cs             0x73    115
ss             0x7b    123
ds             0x7b    123
es             0x7b    123
fs             0x0    0
gs             0x33    51


(gdb) info frame
Stack level 8, frame at 0xbffff1b0:
 eip = 0x80488ea in main (classbasic.cpp:41); saved eip 0x4c48d963
 caller of frame at 0xbffff180
 source language c++.
 Arglist at 0xbffff1a8, args: argc=1, argv=0xbffff244
 Locals at 0xbffff1a8, Previous frame's sp is 0xbffff1b0
 Saved registers:
  ebx at 0xbffff1a4, ebp at 0xbffff1a8, eip at 0xbffff1ac

* Symbol table

[root@localhost PracticeAlgorithm]# nm a.out
0804a04c B __bss_start
0804a0ec b completed.5953
         U __cxa_atexit@@GLIBC_2.1.3
0804a048 D __data_start
0804a048 W data_start
080487c0 t deregister_tm_clones
08048830 t __do_global_dtors_aux
08049ef4 t __do_global_dtors_aux_fini_array_entry
08048ac0 R __dso_handle
08049efc d _DYNAMIC
0804a04c D _edata
0804a0f4 B _end
08048aa4 T _fini
08048ab8 R _fp_hw
08048860 t frame_dummy
08049eec t __frame_dummy_init_array_entry
08048c98 r __FRAME_END__
0804a000 d _GLOBAL_OFFSET_TABLE_
08048959 t _GLOBAL__sub_I_main
         w __gmon_start__
         U __gxx_personality_v0@@CXXABI_1.3
08048658 T _init
08049ef4 t __init_array_end
08049eec t __init_array_start
08048abc R _IO_stdin_used
         w _ITM_deregisterTMCloneTable
         w _ITM_registerTMCloneTable
08049ef8 d __JCR_END__
08049ef8 d __JCR_LIST__
         w _Jv_RegisterClasses
08048aa0 T __libc_csu_fini
08048a30 T __libc_csu_init
         U __libc_start_main@@GLIBC_2.0
08048890 T main
080487f0 t register_tm_clones
08048780 T _start
         U strcpy@@GLIBC_2.0
         U strlen@@GLIBC_2.0
0804a04c D __TMC_END__
         U _Unwind_Resume@@GCC_3.0
080487b0 T __x86.get_pc_thunk.bx
0804891a t _Z41__static_initialization_and_destruction_0ii
         U _ZdaPv@@GLIBCXX_3.4
080489d8 W _ZN7myClass8showDataEv
08048976 W _ZN7myClassC1EiPKc
08048976 W _ZN7myClassC2EiPKc
080489b8 W _ZN7myClassD1Ev
080489b8 W _ZN7myClassD2Ev
         U _Znaj@@GLIBCXX_3.4
         U _ZNSolsEi@@GLIBCXX_3.4
         U _ZNSolsEPFRSoS_E@@GLIBCXX_3.4
         U _ZNSt8ios_base4InitC1Ev@@GLIBCXX_3.4
         U _ZNSt8ios_base4InitD1Ev@@GLIBCXX_3.4
0804a060 B _ZSt4cout@@GLIBCXX_3.4
         U _ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@@GLIBCXX_3.4
0804a0f0 b _ZStL8__ioinit
         U _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@@GLIBCXX_3.4

* References :

thrillfighter.tistory.com/146

http://scottmcpeak.com/memory-errors