지난 목요일 강의를 끝으로 '알고리즘 설계와 분석' 과목이 종강되었습니다.
간만에 돌아온 학교, 이번 학기 최초의 종강이네요.

이 과목에서는 분할 정복법, 동적 프로그래밍, 탐욕적 기법, 되추적, 분기한정법 순으로 알고리즘 풀이 기법을 배웠는데요. 평소에 관심이 많던 분야였던지라 흥미진진 하였습니다.
물론, 베스트 티쳐상을 수상하셨었다는 손교수님의 강의도 좋았구요. 짝짝짝.

학기 중에는 2~3주에 한번씩 과제가 나왔는데요.
ACM 문제를 풀어 MFC로 래핑한 프로그램을 제출하는 식이었습니다.
(제 기억 속의) 2학년 때에 비해 갑자기 난이도가 상승한 기분이라 같이 수업받는 후배들이 불쌍했지만 당황스러웠지만 이건 이것대로 재밌었습니다.

총 5번의 과제가 나왔었는데 그중에서도 가장 어려웠던 Ouroboros Number의 주요 코드를 여기 공개해봅니다.
일종의 되추적 기법을 이용했는데요. 첨엔 자료구조를 잘못 잡아서 캐삽질하고... 전체적으로 4~5시간쯤 걸린 것 같습니다. 쩝.

#pragma once //! 특정 n에 대한 가장 작은 Ouroboros Number를 계산해서 가지고 있는 클래스 class COuroborosNumber { public:  COuroborosNumber(int iN);  ~COuroborosNumber();  //! 특정 k에 대한 o값을 얻어온다.  int GetO(int iK); private:  void Initialize();  bool* m_pbSet; //!< Ouroboros Number 계산중에 특정 o 값이 등장하였는지를 기록해두는 저장소  char* m_pcBit; //!< 2진수로 표현된 Ouroboros Number  int  m_iN;  //!< Ouroboros Number를 생성할 n };
#include "StdAfx.h" #include "OuroborosNumber.h" COuroborosNumber::COuroborosNumber(int iN) : m_iN(iN) {  m_pbSet = new bool[(1 << m_iN)];  m_pcBit = new char[(1 << m_iN)];  memset(m_pbSet, false, sizeof(bool) * (1 << m_iN));  memset(m_pcBit, 0, sizeof(char) * (1 << m_iN));  Initialize(); } COuroborosNumber::~COuroborosNumber() {  delete [] m_pcBit;  delete [] m_pbSet; } int COuroborosNumber::GetO(int iK) {  int iResult = 0;  for (int i = 1; i <= m_iN; ++i)  {   // k 값이 커서 overflow가 발생하는 경우 뒤는 계산하지 않는다. 즉, 0을 붙여준다.   // (가장 작은 Ouroboros Number는 앞에 n개만큼의 0이 등장한다는 사실을 이용한다.)   if ((iK + m_iN - i) < (1 << m_iN))   {    iResult += m_pcBit[iK + m_iN - i] * (1 << (i - 1));   }  }  return iResult; } void COuroborosNumber::Initialize() {  // 가장 작은 Ouroboros Number를 구하는 것이므로, 최초에는 n개의 0이 등장하고...  int iPos = m_iN + 1;    // 그 다음에는 1이 온다.  m_pcBit[m_iN] = 1;  // 위의 과정을 통해 o(n, 0), o(n, 1)은 각각 0과 1로 확정된다.  m_pbSet[0] = true;  m_pbSet[1] = true;  bool bPrunning = false;  // 이후의 과정을 prunning 할 것인가?  bool bLeafBound = false; // 바운딩되는 노드가 리프 노드인가?  // 전체적인 루프는 백트레킹을 이용한다.  while (true)  {   // Ouroboros Number가 완성된 경우   if (iPos >= (1 << m_iN))   {    // 마지막까지 Promising 한가를 검토한다.    // (Promising 조건은 o(n, k)와 같은 o(n, l) - 이 때 l은 k보다 작은 모든 수 - 가 존재하지 않는 것, 즉 m_pbSet를 검사한다.)    int i = 1;    for (; i < m_iN; ++i)    {     int iSetData = GetO(iPos - m_iN + i);     if (false == m_pbSet[iSetData])     {      m_pbSet[iSetData] = true;     }     else     {      break;     }    }    if (i == m_iN)    {     // 마지막까지 Promising 하다면 the smallest Ouroboros Number로 확정.     return;    }    else    {     // 아닌 경우, 바운딩     for (int j = iPos - m_iN; j < iPos - m_iN + i; ++j)     {      m_pbSet[GetO(j)] = false;     }     --iPos;     bPrunning = true;     bLeafBound = true;    }   }   if (false == bPrunning)   {    // 기본적으로 0을 하나씩 붙여가며 Promising 여부를 판별한다.    m_pcBit[iPos] = 0;   }   else   {    // Promising 하지 않아 바운딩된 경우, 최초로 바운딩된 노드가 아니라면 기존에 체크해둔 o 값도 함께 제거한다.    if (true == bLeafBound)    {     bLeafBound = false;    }    else    {     m_pbSet[GetO(iPos - m_iN + 1)] = false;    }    if (0 == m_pcBit[iPos])    {     // 0을 먼저 붙여봤는데 Promising 하지 않았다면 1을 붙여본다.     m_pcBit[iPos] = 1;     bPrunning = false;    }    else    {     // 1도 Promising 하지 않아 바운딩되는 경우     --iPos;     continue;    }   }   int iSetData = GetO(iPos - m_iN + 1);   if (false == m_pbSet[iSetData])   {    // 아직 등장하지 않은 o(n, k). 즉, Promising 하다.    m_pbSet[iSetData] = true;    ++iPos;   }   else   {    bPrunning = true;    bLeafBound = true;   }  } }
문제는 요녀석입니다. ^-^
http://acm.uva.es/p/v100/10040.html

(0) (0)