여섯번째 사요코, 초콜릿 코스모스, 삼월은 붉은 구렁을 을 읽고 빠져버린 온다 리쿠.
마침 요새 50% 세일을 하길래 장바구니에 담아놓고 월급날만 기다리며 부들부들 떨다가, 한방에 질러버렸습니다!!!
9권이나 질렀는데 4만원대로 끊어주니 행복해요~>ㅁ<)//


PS.
친구 과제를 도와주고 나니 갑자기 할일이 없어졌어요ㅠㅠ
아 심심해라... 뭔가 마음을 줄 만한 것이 없을까나~

작년 내한공연 했다는 이야길 듣고 땅을 치고 후회했는데 이번에 다시한번 와주었군요ㅠㅠ
근데 5월 10일 당장 내일이네요-_-; (뭔상관이랍니까 어짜피 갈껀데) 6년을 바래마지않은 공연이니 흑흑ㅠㅠ
ENVY의 라이브를 눈앞에서 직접 들을 수 있다니 꿈만같아요=ㅁ=)//

음악 감상 ㄱㄱ

=================================

보고 왔습니다. 2시간동안 시간개념이 사라졌습니다. 여한이 업스빈다.
라이브의 포스를 모르고 팬이라고 했다니 창피합니다.
a dead sinking story 재킷에다가 멤버분 모두에게 사인 받았어요>ㅁ<)//

문제는 이곳에 있습니다 : 사이냅 소프트 2009년도 신입 및 경력사원 모집을 위한 퀴즈

이 문제의 해결은 간단합니다.
정수 리스트를 모두 돌면서 2개를 선택하여 더하고 더한 값이 정수 리스트에 존재하는가?를 확인하면 됩니다.
3중 for문을 돌면 심플하게 해결되겠죠.

하지만 문제의 제시조건중에 신경써 주어야 할 것이 있습니다. 바로


정수 리스트가 5000개까지 입력 가능합니다. 차라리 없었으면 속편했을 것을... O(n³) 이라는 수행시간이 발목을 잡습니다. (대략 5000*5000*5000번 도는거져.)
5000개를 넣고 무작정 3중 for문을 돌렸더니 수십초가 걸립니다. 출제자가 설마 이런걸 원한 건 아니겠지요.
그래서 생각해 본것이 아래입니다.

#include <algorithm>

size_t GetTripleCount( int *pIntArray, int nArraySize )
{
    std::sort(pIntArray, &pIntArray[nArraySize]);

    int iSum = 0;
    size_t nTripleCount = 0;
    std::pair<int *, int *> range;
    for ( int i = 0; i < nArraySize-1; ++i )
    {
        for ( int j = i+1; j < nArraySize; ++j )
        {
            iSum = (pIntArray[i]+pIntArray[j]);
            if ( iSum <= pIntArray[nArraySize-1] )
            {
                // 갯수만큼 더해줘야 한다.
                range = std::equal_range( &pIntArray[j+1], 
                                          &pIntArray[nArraySize], iSum );
                nTripleCount += (size_t)(range.second - range.first);
            }
        }
    }

    return nTripleCount;
}

어짜피 N개의 정수 중 2개를 순서없이 골라잡아 더해야 하니 _NC₂ 번은 기본적으로 돌아줘야 할 것이고,
두 정수의 합이 리스트에 존재하는가를 확인하기 위해 binary search 가 적용된 알고리즘을 사용하였습니다.
std::equal_range가 내부적으로 그렇게 돌아간다고 책에 써있네요=ㅅ= 끝입니다!
이것으로 수십초 걸리던 함수가 1초 내외로 빨라졌습니다~

문제는 이곳에 있습니다 : 사이냅 소프트 2009년도 신입 및 경력사원 모집을 위한 퀴즈

이 문제는 코드의 양이 조금 깁니다.
이진수의 곱셈을 손으로 풀어나가듯이 예쁘장하게 출력해야 하는 문제입니다.

자 조건부터 알아보도록 하죠.


위의 조건을 만족시키기 위해서 뒤따르는 추가조건들이 생기게 됩니다.

먼저 출력에 대한 helper 함수를 생각해보기로 합시다. 오른쪽 정렬 출력이라는 문제를 해결해 줄 녀석 말이죠.
기본적으로 printf함수의 format string ( 예를들어 printf("%25s", "rightalignedstring"); ) 을 사용하면 오른쪽 정렬 출력이 가능하긴 합니다만, 이것은 컴파일 타임에 정적인 선택만이 가능하므로 여러개의 문제, 계속 달라지는 동적인 오른정렬 너비값을 출력하려면 직접 구현해 주는 방법밖에 없습니다. 그래서 구현해본 코드가 아래에 있습니다.

void _AppendRepeatString( std::string & buffer, 
                         const std::string & str, size_t count )
{
    for ( size_t i = 0; i < count; ++i )
        buffer += str;
}

void PrintLnRightAlignedString( std::string & str, size_t iTotalSize )
{
    size_t nLength = str.length();
    if ( nLength <= iTotalSize )
    {
        std::string buffer;
        _AppendRepeatString( buffer, " ", iTotalSize - nLength );
        buffer += str;
        printf( "%s\n", buffer.c_str() );
    }
}

PrintLnRightAlignedString 함수는 문자열과 오른쪽정렬 될 너비를 입력하면 문자열의 왼쪽에 공백을 삽입하여 출력해 주는 함수입니다. (귀찮아서 너비가 문자열보다 작 경우는 작성하지 않았어요=ㅅ=;)

이것으로 추가조건 2에 대한 조건이 만족되었군요. 이제 추가조건1 과 3을 만족시켜 계산을 하면 위 함수를 사용해 예쁘장한 출력이 가능하게 되었습니다.

자, 본격적으로 계산에 들어가보겠습니다. 이 계산을 위해 CMultiplyBinary라는 클래스를 작성하기로 했습니다.

class CMultiplyBinary
{
public:
    CMultiplyBinary( char *bin01, char *bin02 )
        : m_strBin01(bin01) , m_strBin02(bin02)
    {
        _MakeProcessList();
        _CalcResult();
    }

    //...생략...
private:
    std::string m_strBin01;
    std::string m_strBin02;
    std::string m_strResult;
    std::list<std::string> m_strProcessList;
};

생성자에서는 문제에서 입력될 2진수를 받게 되며, 멤버변수로 2개의 2진수, 결과값, 그리고 계산과정을 가지고 있을 리스트가 모두 string 타입으로 있습니다. 바로 이 생성자에서 _MakeProcessList() 함수를 통해 계산과정이 process list에 누적되게 되며, CalcResult() 함수에서는 이 누적된 리스트를 가지고 결과 string을 만들어내게 됩니다. 모든 계산을 string을 통해 진행될 예정이므로 10진수 <-> 2진수 변환 할 일은 없습니다.

이제 위에서 제시된 함수들을 볼 차례입니다.
드디어 좀 볼만한 코드가 나오네요.=ㅅ=)/

우선 _MakeProcessList() 부터 보도록 하죠.

private:
    void _MakeProcessList()
    {
        size_t nBin02Length = m_strBin02.length();
        for ( size_t i = 0; i < nBin02Length; ++i )
        {
            std::string buffer;
            if ( '1' == m_strBin02[nBin02Length - i - 1] )
                buffer = m_strBin01;//strBin01을 출력하고
            else//bin01길이만큼 0을 출력한다.
                _AppendRepeatString( buffer, "0", m_strBin01.length() );

            // 몇번째인지 뒤에 공백을 붙인다.
            _AppendRepeatString( buffer, " ", i );
            m_strProcessList.push_back(buffer);
        }

    }

이 함수는 손으로 과정을 작성하듯이 process list를 입력하는 부분입니다. 입력된 2번째 binary의 길이 갯수만큼 for문을 돌면서 2번째 binary가 1이면 첫번째 바이너리, 0이면 첫번째 바이너리 길이만큼 '0'을 넣어줍니다.
특이사항이라면 몇번째 줄인지에 따라 뒤에 공백을 넣어주는 것인데요.
후에 결과를 계산할 때도 편하고, 출력할 때도 그냥 오른쪽정렬만 해서 출력하면 되니 편리하겠죠?
물론 앞부분에도 공백을 넣어서 더더욱 편리하게 (그냥 왼쪽정렬로 출력해도 되도록) 진행할 수도 있지만, 지금으로써는 결과의 길이를 알 수 없으니 얼마큼의 공백이 앞에 붙어야 되는지 알 수 없습니다.

두번째로 볼 _CalcResult() 멤버함수 입니다. 이는 위에서 입력된 process list를 기반으로 결과 string을 만들어내는 함수입니다. 코드부터 보시죠~

    void _CalcResult()
    {
        // string을 뒤집어서 계산하고, 결과도 뒤집어서 만든 뒤 다시 뒤집는다.
        std::list<std::string> ReversedProcessList;
        ReversedProcessList.resize( m_strProcessList.size() );
        std::copy( m_strProcessList.begin(), m_strProcessList.end(), 
                    ReversedProcessList.begin() );

        std::list<std::string>::iterator iter = ReversedProcessList.begin();
         for ( ; iter != ReversedProcessList.end(); ++iter )
         {
            std::reverse((*iter).begin(), (*iter).end());
         }

        // 더해봅시다.
        int iSum;
        int iNextAdd = 0;
        size_t nMaxLendth = ReversedProcessList.back().length();
        for ( size_t i = 0; i < nMaxLendth; ++i )// 가장 긴 녀석만큼 돈다.
         {
            iSum = _AddColumn( ReversedProcessList, i ) + iNextAdd;
            m_strResult.append( (iSum%2)?"1":"0" );// 2진수 끝자리
            iNextAdd = iSum/2;
         }

        while ( 0 != iNextAdd )
        {
            m_strResult.append( (iNextAdd%2)?"1":"0" );// 2진수 끝자리
            iNextAdd = iNextAdd/2;
        }

        std::reverse(m_strResult.begin(), m_strResult.end());
    }

이 함수는 3단계로 이루어져 있습니다.
1. m_strProcessList에 입력된 모든 문자열을 뒤집는다.
2. 뒤집혀진 리스트의 열을 모두 더해준다. 2진수이므로 2보다 크거나 같으면 다음 열을 더할 때 더해주게 된다.
3. 계산된 결과 문자열을 다시 뒤집는다.

1번 단계에서 문자열을 뒤집는 이유는 열을 더해줄 때 왼쪽부터 더해주기 위해서지요. 실제 손으로 계산할 때는 오른쪽-> 왼쪽 열(column) 순서로 더해주지만, 코드상으로는 그게 귀찮잖아요. for문을 거꾸로 돌아줘야 하니 실수할 여지도 있고. 2번에서 결과값도 오른쪽으로 계속 추가되기 때문에, 3번에서 최종적으로 결과값을 뒤집어주어야 우리가 읽을 수 있는 2진수가 나타나게 됩니다.

설명이 거의 끝났지만 한가지 빠뜨린 함수가 있죠. 바로 _AddColumn()입니다. 열을 더하는 함수죠.

    int _AddColumn( std::list<std::string> & SwappedProcessList,
                    size_t index )
    {
        int iSum = 0;
        std::list<std::string>::iterator iter = SwappedProcessList.begin();
        for ( ; iter != SwappedProcessList.end(); ++iter )
        {
            if ( (*iter).length() > index && 
                (*iter)[index] == '1' )
            {
                iSum += 1;
            }
        }

        return iSum;
    }

네 보시는 그대롭니다. process list를 모두 돌면서 해당 컬럼의 문자가 '1'이면 합계에 1을 더해주는 방식이죠.
드디어 모든 계산을 마치고 결과 binary(m_strResult)를 만들어 내었습니다. 후후후

이제 예쁘장하게 출력하는 일만 남았네요. 이 포스팅의 가장 처음에 오른쪽 정렬 출력을 도와주는 함수를 보셨죠? 이제 결과도 알고 있고 계산과정도 들고 있으니 있는 그대로 출력하는 일만 남았습니다~

    void PrettyPrint()
    {
        size_t nResultLength = m_strResult.length();
        PrintLnRightAlignedString( m_strBin01, nResultLength );
        PrintLnRightAlignedString( m_strBin02, nResultLength );

        std::string delimiter01;
        _AppendRepeatString(delimiter01, "-", max(m_strBin01.length(), 
                            m_strBin02.length()) );
        PrintLnRightAlignedString( delimiter01, nResultLength );

        std::list<std::string>::iterator iter = m_strProcessList.begin();
        for ( ; iter != m_strProcessList.end(); ++iter )
        {
            PrintLnRightAlignedString( (*iter), nResultLength );
        }

        std::string delimiter02;
        _AppendRepeatString(delimiter02, "-", nResultLength );
        PrintLnRightAlignedString( delimiter02, nResultLength );

        PrintLnRightAlignedString( m_strResult, nResultLength );
        printf("\n");
    }

이 코드는 별로 설명할 것이 없네요. 끝입니다~

추가: 구지 process list를 누적시키지 않아도 결과를 계산하고 출력하는데 문제없는 방법이 있을 것 같은데, 조금 더 생가해 보아야 겠습니다.