20230526금-오산, 인형

 

목차

 

컴알

오늘은 그래프의 마지막.. 인 줄 알았으나 다익스트라 알고리즘은 다음 주로 넘어가게 됐고, 대신 오늘은 최소 신장 트리를 공부했다. 그래프와 관련된 문제는 다양하다. mst, spp, tsp. 오늘 이야기된 문제들인데, 순서대로 최소 신장 트리, 최단 경로 문제, 여행 순회자 문제. 보통 가장 잘 알려진 건 최단 경로일 텐데, mst를 먼저 본 이유는 만들어진 시기를 고려해서도 그렇고, 다익스트라가 mst 해법의 특수한 해이기 때문이기도 하다.

mst란? 최소 신장 트리. 뭐가 최소인 걸까? 가중치가 있는 간선의 총합이 최소이다. 신장 트리는 뭐지? spanning이 뭔지 몰라 처음에는 어려웠는데, 모든 노드를 가지는 부분 그래프를 말한다고 한다. 선형대수학의 span인 걸까? 아직 그 개념도 잘 모르기에 잘 판단은 안 선다. 내가 이해하는 정도의 span은 스칼라배를 통해 다르게 표현될 수 있는, 즉 가능한 범주에서 쫙쫙 늘어나는 그런 속성이나 대상을 말하는 것인데, 이게 어떤 연관이 되는지는 모르겠다. 트리, 즉 acyclic connected graph에 spanning 요소를 가진 부분 그래프를 찾고 싶은데 이때 간선 가중치의 합이 최소가 되기를 바라는 것이다. 
더 쉽게 말하자면, 주어진 그래프에서 임의의 그래프를 꺼내고 싶은데, 이 그래프는 모든 노드를 연결한 상태이면서 사이클은 없고, 그러면서 비용이 최소라는 것.

두 가지 알고리즘이 존재한다. 크루스칼과 프림. 둘 다 비슷하다. 시간복잡도 역시 비스무리하다. 직관적이기는 크루스칼이 조금 더 직관적인 듯하다. 크루스칼은 모든 간선의 가중치를 올림차순으로 정렬하고 작은 놈들부터 하나씩 골라나가는 것이다. 그리고 고를 때마다 사이클이 발생하는지 체크한다. 발생하는 놈은 건너 뛴다. 이것의 특징은 매번 만들 때마다 트리인 부분 그래프가 생긴다는 것이다. 종국에는 이 트리들이 이어져 하나의 거대한 트리가 된다. 트리들이 많이 나오는 구조를 띄기에 포레스트를 활용한다고 말할 수 있다. 
프림 알고리즘은 무작위 노드에서 출발해서 트리를 계속 쌓아나간다. 사이클마다 그래프 내의 노드를 3가지로 나눈다. 트리에 이미 속하게 된 intree 노드, 트리에 속한 노드와 하나의 간선으로 이어진 fringe 노드, 그리고 그 이외에 아직 탐지되지 않은 unseen 노드. 목표는 모든 노드가 intree 노드에 속하게 되는 것. 그러기 위해서 매 사이클마다 fringe 노드에 속하는 노드를 하나씩 선택한다. 그런데 이때 선택의 기준이 간선의 가중치가 가장 작은 것. 결국 이것도 작은 가중치를 선택하게 된다. 둘은 크게 다르지는 않다. 프림의 특징. 프림에서 발전해서 다익스트라가 나온다!

회고 및 다짐

내가 술만 안 마시면 이미 몇 키로는 더 뺐을 것 같은데.. 술 안 마시는 게 참 어렵다. 어제 오랜만에 담배를 다시 물어봤는데 필 수는 있지만 영 다시 피고 싶다는 생각이 안 들어서 관뒀다. 술은.. 그러기 어려운 것 같다. 적당하게 술을 즐기는 기준을 어떻게 잡는 게 좋을런지. 
사실 그것보다는 이대로 운동하면 두 달 후쯤에는 내가 택배하던 시절의 몸무게로까지 갈 것 같은데, 그때부터 내가 어떻게 운동 방향을 잡는 게 좋을지 고민이 된다. 그때 사람들에게 왜소해졌다는 평을 들었는데, 사실 그럼에도 어릴 때부터 있던 살은 줄지 않은 상태이기는 했다. 아마 지금 몸무게가 그때로 간다면 왜소한 인상이지는 않을 것 같기는 하다. 그때는 온몸의 지방이고 근육이고 수분이고 쫄쫄 빠졌고, 지금은 최대한 살만 빼면서 가고 있으니까. 달리 보자면 지금의 내가 그정도로 살이 빠진다면 그것은 정말 거의 지방만 빠지는 그림이 될 것 같다. 물론 그리 된다고 내가 정상 체중이라던가 그런 건 아마 아닐 것으로 생각된다만, 그 이후로 살을 빼는 것이 정말 힘들었던 것을 생각하면 이후부터가 난관일 것 같다는 게 포인트다. 나는 어느 정도 근성장을 통한 증량도 하고 싶은데, 이때를 기점으로 운동 방식을 바꾸면 남은 지방도 조금은 타면서 근육을 늘리는 게 가능할지, 그렇다면 운동 스타일을 바꾸는 게 좋을지 그런 고민이 계속 되는 것이다. 

알고리즘 교수님이 다음주 화요일에 면담을 갖자고 말씀하셨다. 나한테만 한 것은 아니고, 나, 물리학과, 수학과 이렇게 3명의 타과생에게 이야기를 하신 것. 원래 타과생에게 한번씩 상담을 해주신다고 한다. 나와 물리학과 친구는 특히나 열심히 수업에 참여하는 부류라 기특하게 생각해주시는 것도 있는 듯.

음. 잘못 하면 내 계획이 다 어그러지게 생겼다. 졸업을 위한 필요학점이 딱 3학점 남은 상황. 이번 학기 악착같이 18학점 듣고, 나머지 3학점은 계절 학기로 채울 생각을 하고 있었다. 기왕이면 내게 도움이 되는 강의를 듣고 싶어서 인공지능수학심화 강의를 신청했는데, 오늘 보니까 최소 인원 충족이 안 돼 폐강이 된다고 하네.. 정원이 빨리 안 찬다 싶어서 뭔가 불안했지만 그래도 폐강될 거란 생각은 안 하고 있었건만. 
계절을 못 들으면 나는 초과학기를 다녀야만 한다.. 이게 뭔..? 생각지도 않은 상황이 터져서 많이 당황스럽다. 폐강된 강의 신청한 인원에 한해서 재신청 권한을 준다는 이야기도 있어서 일단은 조금 더 상황을 지켜봐야할 것 같은데, 계절은 빌넣이나 증원이 잘 이뤄지지 않아서 정원이 안 찬 강의 아무거나 신청해야 한다고 하기도 하고..
최악은 정말로 초과학기를 다니는 것이겠지. 그러면 아싸리 재수강하고 싶던 강의들을 재수강까지 하면서 가는 것도 나쁘지 않..지 않다. 학점을 챙길 때가 아니잖나! 이럴 줄 알았으면 안전하게 인기 많을 것 같은 강의 신청할 걸..
급 술이 땡겼는데 참았다. 술은 기분 좋을 때 마셔야지, 지금은 그냥 기분 나쁜 일을 핑계로 술을 마시고 싶은 것일 뿐이다.

프로도씨가 내 생일날 내게 선물해준 인형이 오늘 도착했다. 댕청하게 생긴 멍뭉이 인형인데 빼빼로 인형 대신 껴안고 자라고 하더라..ㅋㅋ 그걸 또 어떻게 기억하고 있었던 거지. 인형 선물을 받는 건.. 처음까지는 아니지만 거의 처음이기는 하다. 안 지 얼마나 됐다고 생일 선물을 챙겨주나, 막상 받으니까 많이 고맙더라😅
괜히 넘겨짚지 말자. 저 친구 마음은 아직 잘 모르겠지만, 이제 내 마음은 아니까.