E D R , A S I H C RSS

Eight Queen Problem Second Try Discussion

이번에 해결할때는 각 테스트 부분에 대해 시간측정을 하고 했습니다. (한 5분간격정도 기준) 중간에 테스트를 작은 테스트로 나눌때 빼고는 보통 한 테스트 당 5분정도 걸리더군요.

우.. 그리고 여전히 테스트 코드를 생각하기 어려웠던 부분이 실제 Queen 을 놓는 부분인데요. 다음과 같이 코드를 나열하고 재귀호출 부분에 대해서 유도를 하는 방법을 시도해봤습니다. 일종의 수열 찾는 방법이 되더군요. 음.. 이 부분에 대해서는 EightQueenProblem 에 대한 하나의 해를 알아놓고 시작한다면 TDD를 시도할 수 있을것 같다는 생각이 들긴 하는데. (문제는, 답을 구해놓고 나서야 이 생각이 났더라는. --;)

  • 하고 나니 아쉬웠던점 - 여유가 있었는데, 만들고 나니 기존에 생각했었던 방법과 비슷하게 되어버렸다는 점. 좀 더 여유를 가지고, 현재 생각한 방법 자체가 복잡한 방법이 아닐까 생각하면서 더 쉬운방법을 생각해낼 수 있었을텐데.. 다른 사람들의 소스를 보니 Queen에 대한 대각선 처리 알고리즘 부분이 훨씬 더 단순하게 할 수 있겠더라는.
    알고리즘에도 OAOO를 적용할 수 있습니다. 정보의 중복(duplication)이 있다면 제거하는 식으로 리팩토링을 하는 겁니다. 이 때 정보의 중복은 신택스 혹은 세만틱스의 중복일 수 있습니다.

유도 과정 부분

~cpp 
def MakeEightQueen (self, Level):
    UnAttackableList0 = self.GetUnAttackableOthersPositionList (0)

    for UnAttackablePosition0 in UnAttackableList0:
        self.SetQueen (UnAttackablePosition0)

	UnAttackableList1 = self.GetUnAttackableOthersPositionList (1)
	if not len (UnAttackableList1):
		self.EraseQueen (UnAttackablePosition0)
		continue

	for UnAttackablePosition1 in UnAttackableList1:
		self.SetQueen (UnAttackablePosition1)

		UnAttackableList2 = self.GetUnAttackableOthersPositionList (2)
		if not len (UnAttackableList2):
			self.EraseQueen (UnAttackablePosition1)
			continue

		for UnAttackablePosition2 in UnAttackableList2:
		self.SetQueen (UnAttackablePosition2)

		.
		.

		## if level == 8:
		## make clone and append the 
			eq = QueenBoard ()
			self.Clone (eq)

			self.EightQueenList.append (eq)
			return 0

최종부분

~cpp 
    def MakeEightQueen (self, Level):
        if Level == self.size:
            eq = QueenBoard ()
            self.Clone (eq)

            self.EightQueenList.append (eq)
            return 0

        UnAttackableList = self.GetUnAttackableOthersPositionList (Level)
        if not len (UnAttackableList):
            return 0
            ## return before level. ( if level == 0: have no solution)

        for UnAttackablePosition in UnAttackableList:
            self.SetQueen (UnAttackablePosition[0], UnAttackablePosition[1])
            if not self.MakeEightQueen (Level + 1):
                self.EraseQueen (UnAttackablePosition)
-- 석천


EightQueenProblemDiscussion 에서 지적해주신 것처럼, OOP를 써보자라는 목표로 다시 작성해보았더니, 디자인상의 고려 때문인지, 저녁시간이라 뇌력의 소모 때문인지는 몰라도 오히려 시간이 더 늘어버렸습니다. 이번 디자인은 과연 OOP를 제대로 쓴건지 의견을 구합니다.

디자인하면서, 가장 의문이 들었던 부분이 출력과 관계된 부분이었습니다. EightQueenProblem 자체가 출력이 필요한 문제인지, 아닌지로 시작된 고민에.. 결국 '출력이 필요하다' 라고 결론을 내리게 되어, 출력을 원할경우, 인자로 출력 소스를 넘겨주면 지시한 곳으로 출력하고, 부가적으로 output format을 지원하는 방식을 채택하였습니다.


--이선우

제가 보기에 현재의 디자인은 class 키워드만 빼면 절차적 프로그래밍(procedural programming)이 되는 것 같습니다. 오브젝트 속성은 전역 변수가 되고 말이죠. 이런 구성을 일러 God Class Problem이라고도 합니다. AOP(Action-Oriented Programming -- 소위 Procedural Programming이라고 하는 것) 쪽에서 온 프로그래머들이 자주 만드는 실수이기도 합니다. 객체지향 분해라기보다는 한 거대 클래스 내에서의 기능적 분해(functional decomposition)가 되는 것이죠. Wirfs-Brock은 지능(Intelligence)의 고른 분포를 OOD의 중요요소로 뽑습니다. NQueen 오브젝트는 그 이름을 "Manager"나 "MainController"로 바꿔도 될 정도로 모든 책임(responsibility)을 도맡아 하고 있습니다 -- Meyer는 하나의 클래스는 한가지 책임만을 제대로 해야한다(A class has a single responsibility: it does it all, does it well, and does it only )고 말하는데, 이것은 클래스 이름이 잘 지어졌는지, 얼마나 구체성을 주는지 등에서 알 수 있습니다. (Coad는 "In OO, a class's statement of responsibility (a 25-word or less statement) is the key to the class. It shouldn't have many 'and's and almost no 'or's."라고 합니다. 만약 이게 자연스럽게 되지않는다면 클래스를 하나 이상 만들어야 한다는 얘기가 되겠죠.) 한가지 가능한 지능 분산으로, 여러개의 Queen 오브젝트와 Board 오브젝트 하나를 만드는 경우를 생각해 볼 수 있겠습니다. Queen 오브젝트 갑이 Queen 오브젝트 을에게 물어봅니다. "내가 너를 귀찮게 하고 있니?" --김창준
말씀해주셔서 감사합니다. 이해가 안되는 부분 몇가지 여쭤보겠습니다. 종합해보면, NQueen 자체는 어떠한 보드 형태가 n-Queens problem을 만족하는것인지를 알아봐야 하고, n * n 크기의 보드를 만들어거나 만들어진 보드를 출력하는건 다른 누군가의 몫이다. 라는 이야기가 되는건가요?(이 내용이 위에서 쓰신 한가지 가능한 ... 볼 수 있겠습니다의 내용인지도 궁금합니다.) 그리고, 마지막에 쓰신 Queen 오브젝트 갑이 Queen 오브젝트 을에게 물어봅니다. "내가 너를 귀찮게 하고 있니?" 의 내용이 어떤 뜻인지 궁금합니다. --이선우
예를 들어, Board 객체는 Queen 객체들을 만들고 배치, 자신의 상태를 출력하는 서비스를 지원하고, Queen 객체는 내가 다른 Queen 객체를 공격할 수 있는지 없는지 알려주는 서비스를 지원합니다 -- 더 나아가서 스스로 자기 앉을 자리를 찾아갈 정도로 똑똑하게 만들 수도 있겠죠. Queen 오브젝트 갑이 Queen 오브젝트 을에게 물어봅니다. "내가 너를 귀찮게 하고 있니(attackable에 대한 메타포임)?", 라는 부분은 OOP로 어떻게 표현될 수 있을까 직접 생각해 보는 것이 더 좋을 것 같습니다. OOP에서 객체끼리의 의사소통은 보통 메쏘드 호출로 이루어지고, 목적어는 인자의 형태로 전달된다는 점을 고려한다면 여러가지 방법이 떠오를 수 있겠죠.

계속해서 문제점을 발견하니 재밌습니다. 또다시 OOP에 도전해봤습니다. 기본 컨셉은, 체스 말과 보드 그리고 체스 플레이어가 등장합니다. 체스 말은 자신이 놓임으로써 다른 말을 "귀찮게 하는지"를 판단하고, 보드는 이러한 체스 말들이 놓이고 출력하는 일을 담당합니다. 마지막으로 체스 플레이어는 자신의 알고리즘에 따라 보드에 퀸을 배열하게 됩니다. 이번에 대각선 방향의 퀸을 체크하는 방법으로 기울기에 의한 방법이 떠올랐습니다. 덕분에 대각선 체크가 깔끔해진듯 합니다. 위에서 이야기해주신 방법 가운데 '스스로 자기 앉을 자리를 찾아간다'라는 부분은, 그렇게 되면 체스 말과 보드가 서로 tightly하게 연결될 공산이 커서 고민하다가 체스 플레이어를 탄생시킨 배경이 되었습니다.


--이선우

음.. 아직 구현은 안해보고 그냥 생각해본거지만, 체스 말과 보드가 타이트하게 연결되어도 큰 문제는 아닐 것 같은데요. 보드를 Singleton 으로 모든 Queen들이 공유하는 객체로 생각해도 좋을 것 같고요. (Queen에 눈이 달렸던지, 그렇지 않으면 체스 플레이어같이 Queen이 존재하고 있는 세계에 대한 답을 내려줄 신 (?) 이 존재하던지 둘중 하나가 될듯 하다는. ^^;) 아직 OO 관점으로는 그냥 생각만 해보는중. --석천

커플링에는 음과 양이 있습니다.

OO 패러다임은 사물(사건 + 물건)들이 제 할 일을 스스로 알아 하는 신기하고 편리한 세상을 상정합니다. 친구가 집에 찾아왔다가 방을 어지럽히고 갔습니다. 자신이 갖고있는 "깨끗한 방 배치도"를 이용하거나 혹은 각 물건 당 붙어있는 "원래 위치" 꼬리표를 보고 갖다 놓을 위치와 거기로 이르는 경로를 판단, 직접 재배치를 해야하는 세상과, 벽에 지도 한장을 붙여놓고 마치 마술(automagically)처럼 "모든 물건은 제 위치로!"라고 외치면 말끔히 정리가 되는 세상, 어느 것이 OOP적일까요.

Wiki:TellDontAsk라고 합니다. (see also Wiki:LawOfDemeter)
~cpp 
route=superman.getEverydayPath()
for each city in the route:
   superman.visit(each city)

~cpp 
superman.travelEverydayPath()
의 차이입니다.

--김창준

다시 머리가 아파오기 시작합니다. 이번에 자를 수 있는데로 잘라보자라고 결심을 하게 된 배경중 하나가, NQueen2 에서 자신의 영역을 뛰어넘는 Manager가 되버리는 경우에 대한 이야기가 있어서 였습니다. 그렇다면 역으로, 위에서 superman과 object의 개념이나 경계는 모호해지는게 아닌가요? 그렇다면, Player가 따로 있는 개념보다는 Board에서 처리하는게 더 OO적인가요?

--이선우

제 말을 ~cpp mainProgram.runEverything()을 실행하면 모든 게 마술처럼 알아서 실행되게 하라는 뜻으로 오해하지는 않았으면 합니다. 위 superman의 예에서는, 전자의 경우 superman을 제대로 이용해 먹으려면 superman의 내부적 구조를 알아야 합니다. superman의 구현에 종속적이 되는 셈이죠. 하지만 후자는 그게 디커플링이 됩니다. 자기가 매일 가는 길에 있는 도시를 방문하는 것은 superman이 스스로 수행할 수 있어야 할 책임이 있다 이거죠. Queen이라는 객체가 여덟개가 있다고 칩시다. 얘네들한테 "너는 저 여왕을 공격할 수 있니?"하고 묻고 그 결과를 가지고 여왕을 배치하고 하는 것을 하나의 추상(abstraction)으로 묶는 것이 어떨까요? 묻지말고 "시키자"는 것이죠 -- 여덟개의 똑똑한 Queen 객체를 만들고 하나씩 "판 위로 올라가라"고 시킵니다. 이렇게 하면 Board와 Queen에 커플링이 생겨서 문제가 되는 건 아니냐고 했는데, 어차피 Queen은 Board 없이는 별 의미가 없고, 또, 그렇게 하지 않더라도 어떻게든 비슷하거나 혹은 더 큰 정도의 커플링이 존재합니다. 어쨌건, 지금 단계에서는, 더 나은 방법이라기보다 그냥 다른 방법이라고 편안하게 생각하면 좋을 듯 합니다. --김창준
DeleteMeLater) 네, 무슨 말씀이신지 알겠습니다. 며칠 동안 Queen 생각하느라 시간가는줄 몰랐습니다. 잠깐이 아니라 꾸준히 배움이 즐거울 수 있은 묘책이 있으면 좋겠습니다. :)
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:11
Processing time 0.0318 sec