8. 17

• 번사이드 정리...끙.. 오늘 꼭 이해하고 말리라. 링크! 바둑판에서의 경우의 수를 세는 문제를 풀고 있었는데, 개고생해서 하나하나 따져가며 AC를 받아냈는데(오답 7번이었나-_-), 딴사람 코드 보고 멍..해졌던 기억이 있다. 아마도 번사이드 정리를 써서 해결한 방법이었던 것 같은데.. 번사이드 정리는 군론과 관련이 있군!
• Burnside's lemma.docx
• For any problem, there is a certain challenge in trying to solve it elegantly using only lists, but there are nevertheless good reasons to avoid too much of a fixation on lists, particularly if a focus on seeking elegant list-based solutions induces a myopia for elegant solutions that use other well-known data structures. For example, some of the people with whom I discussed the ideas in this paper were not aware that a solution using a heap was possible in a purely functional language because they had never seen one used in a functional context. The vast majority of well-understood standard data structures can be as available in a functional environment as they are in an imperative one, and in my opinion, we should not be afraid to be seen to use them. (The Genuine Sieve of Eratosthenes에서) 머시땅..
• To be in emotional contact with others is important for my quality of life. I think that's why I feel better these days. Chances to communicate deeply are very thin, because I am the very bottom of the hierarchy around me and my superiors are at least 1.5 times older than me. They have very distinct interest from mine, which leads to have less subjects to communicate in common. However, I am finding some way to the equilibrium adding my interests. Moreover, I learned to value the experience to share with. However different interests, we can share experience together and communicate emotion.. Now I try to get 'involved in' the activities and share my own feelings. In that way, I could laugh more often and feel more delighted.
  
• MINASTIRITH 후기. 풀고나서 기뻐서 게시판에 글올림-_- 결국 환형 덮기 문제인데, 여기서 까다로운 것은 선형으로 전환할 때 시작점(이자 끝점)을 덮는 선분들을 특별히 처리해주어야 한다는 것이다. 중요한 아이디어는 이중에 단 하나의 선분만 넘김처리를 하고 나머지에 대해서 선형 덮기를 수행해 최적해를 찾아내면 된다는 것인데, 그 정당성은 책에 증명되어 있다. 간단히 설명하면, 최적해에 세 개 이상의 선분이 포함되어 있을리는 없고, 두개 혹은 하나인데.. 하나일 때는 선형덮기로 당연히 최적해가 나오게 된다. 두 개가 최적해에 포함될 경우 둘 다 넘김처리를 해야 되지 않냐?싶지만 그렇지 않다는 게 포인트! 중심점이 시작점을 사이에 두고 나뉘어 있다면, 어느 한 쪽을 선택했을 때 최적해를 구하면 다른 한쪽을 포함시킬 수 있다. 시작점을 기준으로 어느 한 편에 둘 다 존재한다면, 중심점이 시작점에 가까운 선분을 처음에 선택했을 때 최적해가 계산된다. 왜냐하면 두 점 모두 최적해에 포함되어야 하니까, 중심점이 더 먼 점이 더 가까운 점을 넘어서 갈 리는 없기 때문. 결국 환형이라는 모양은 첫 선분 계산할 때만 고려하면 된다.