CPP Module 09 self check list

서론

Ford-Johnson(포드 존슨) 알고리즘으로 유명한 이 과제는 제대로 구현한 사람을 찾기가 힘들다.

짐작하건대 통과자 중 75%는 완전히 잘못 짰고 15%는 그럴 듯 하게 보이게 짰으며 나머지 10%만이 제대로 짰다.

본래 포드 존슨 알고리즘을 주제로 쓰려고 하였으나 귀찮기도 하고 1시간 뒤에 출근할 계획이라 주제를 조금 바꿨다.

제출하기 전에 이 정도는 스스로 확인해보자.

 

Exercise 00: Bitcoin Exchange

• 어떤 컨테이너를 사용하였는가? key-value 쌍을 효율적으로 저장할 수 있는 컨테이너인가?
• (std::map을 선택하지 않았다면) 선택한 컨테이너는 std::map에 비하여 어떠한 장단점이 있는가?
• key의 타입은 무엇인가? 정답은 없지만 약간의 성능 차이는 있을 것이다.
• find()가 정말로 필요한가? upper_bound()로 대체할 수는 없는가?
• 파싱을 제대로 하였는가? 미숙한 코딩 실력을 '이 과제는 파싱 과제가 아니다' 등의 변명으로 넘어가려 하고 있지는 않은가?

 

Exercise 01: Reverse Polish Notation

• 어떤 컨테이너를 사용하였는가? LIFO를 지원하는 컨테이너인가?
• (std::stack을 선택하지 않았다면) 선택한 컨테이너는 std::stack에 비하여 어떠한 장단점이 있는가?
• std::stack은 컨테이너가 확실한가? 컨테이너와 컨테이너 어댑터의 차이를 알고 있는가?
• (ex02에서 std::deque을 사용하였다면) 서로 다른 exercise에서 동일한 컨테이너를 사용할 수 없다는 제한을 지키고 있는가?
• division by zero를 처리하였는가? 정수 자료형을 사용하였다면 필수적으로 처리해야 한다.
• overflow를 처리하였는가? 처리하였다면 어떻게 처리하였는가? 처리하지 않았다면 어떤 이유로 처리하지 않았는가?

 

Exercise 02: PmergeMe

• 어떤 컨테이너를 사용하였는가? 선형 자료 구조 기반의 컨테이너인가?
• 선택한 두 컨테이너는 포드 존슨 알고리즘에서 뚜렷한 장단점을 가지고 있는가?
• (std::vector와 std::deque을 동시에 선택하였다면) 구현을 편하게 하기 위하여 std::deque을 선택하지는 않았는가?
• (std::list를 사용하였다면) iterator가 항상 valid하다는 특성을 이용하고 있는가?
• (generic function을 사용하였다면) 두 컨테이너의 성능을 최대한으로 이끌어낼 수 있는 구현이 확실한가?
• (핵심 로직이 50 라인을 넘어간다면) 표준 라이브러리를 효율적으로 사용하고 있는가?

• 신뢰할 수 있는 자료를 참고하였는가? 블로그는 신뢰할 수 있는 자료가 아니다.
• 포드 존슨 알고리즘의 원본 논문을 찾아보았는가? 또는 TAOCP Volume 3의 5.3.1절을 찾아보았는가?
• 알고리즘의 핵심 원리를 파악하였는가? 비교 횟수가 줄어드는 원리를 간략한 예제를 통해 설명할 수 있는가?
• main chain을 포드 존슨 알고리즘을 이용하여 재귀적으로 정렬하고 있는가? 그렇지 않다면 잘못된 구현이다.
• 이분 탐색을 전체 범위에서 수행하고 있지는 않은가? 만약 그렇다면 잘못된 구현이다.
• 야콥스탈 수가 정말로 필요한가? 알고리즘의 핵심 원리를 파악하였다면 반드시 필요하지는 않다.
• OEIS A001768 수열의 의미를 알고 있는가? 당신의 구현은 이 수열을 만족하는가?

 

끝

빨리 클러스터 가서 할로우 나이트 해야 됩니다

푸하하

낄낄

끝