20230525목-무난한 하루

 

목차

 

오전

어제 술을 다 마신 후 노래방까지 제대로 즐기고 왔다. 술을 꽤 많이 마셨는데, 정신이 말짱한 상태로 잠자리에 들었고, 아침에 일어나서도 상태는 나쁘지는 않았다. 그래도 균형 감각이 조금 부족한 것 같아서 오전은 쉬면서 보냈다. 운동을 할 수는 있을 것 같았지만, 이전에 술 마신 상태에서 운동을 하면 간이 망가진다는 조언을 극렬하게 들은 바, 술 마신 후에 운동을 할 생각이 싹 사라졌다.

프밍 기초

오늘 수업부터는 과제의 형식이 조금 바뀌었다. 원래는 책에 있는 예제 코드를 그대로 제출하는 것이 과제였다. 문제를 10개 이상 내다보니 수업 시간 내에 다 끝내기 위해서는 그냥 코드를 베껴서 그대로 제출하는 것이 베스트였다. 근데 이제부터는 과제는 교수님이 직접 만든 문제 4개를 직접 코드를 짜서 제출하는 방식으로. 문제가 조금 두루뭉술해서 푸는 게 쉽지는 않았는데, 그렇다고 해서 그렇게 어렵지도 않았다.
어려운 것은 문자열을 다루는 것. 이게 좀 어렵더라. c언어는 입력을 받는 것부터가 참 쉽지 않다. 문자 하나를 받고 싶은데 내 입럭이 끝났다는 것을 나타내기 위해 줄바꿈을 넣어줘야 하고, 이게 또 문자로 인식이되는 경우가 생기다보니까..이를 위해 또 다양한 입력 함수가 생기는데 종류가 퍽 많아서 또 매우 귀찮다. 버퍼에 담아서 입력을 받는 놈이 있는가 하면, 그냥 바로바로 받는 케이스도 있고, 또 conio 헤더에 담긴 함수도 있고.. 이것을 잘 적응하는 게 관건이라고 생각이 든다.

조교님 과제는 기본 헤더에 있는 함수를 구현하는 것이었는데, 42서울에서 보냈던 시간들이 좀 스쳐지나갔다. 정말 처음 코딩이라는 것을 익혀보던 시절. 이 쉬운 것들조차 그 시절에는 쉽지가 않았다. 뭐.. 심지어 vim으로 하기도 했으니까.

알림 스터디

동적계획법. 

해를 테이블에 저장하면서 풀어나가는 데에서 유래.  큰 문제의 해답이 작은 문제를 풀어나가면서얻을 수 있다면 이를 최적 부분 구조라고 부른다. 이러한 성질을 가질 때 동적 계획법을 적용하는 것이 가능하다. 
최적 부분 구조를 통해 완전탐색을 효율적으로 하는 방법이라 이해하면 좋다. 
최적 부분 구조인지를 따지는 것이 가장 핵심이다. 내가 답을 내기 위해 필요한 요소를 찾고, 이를 상태공간으로 정의한다. 그리고 이 상태 공간간의 관계를 밝힌다. 이것이 곧 점화식을 찾는 과정이라고 할 수 있다. 
큰 문제를 작은 문제로쪼개니까 재귀호출이 일어나는 것이 보통이다. 이를 메모이제이션 기법을 이용해 최적화한다. 작은 문제들의 답을 메모리로 남기고 이를 계속 활용하는 방식이다.

완전탐색으로 풀어야 할 것 같은 문제인데 시간 이슈가 있을 것 같다면. 이럴 때 쓸 생각을 해봐야한다. 상태공간을 생각하는 것이 쉽지 않지만 이를 찾는 훈련이 필요하다. 이것을 잡아야만 점화식을 세울 수도 있게 된다.

dp는 특정 알고리즘이 아니라 기법. 구현 방법도 정해져 있는 것은 없다. 
그래도 접근 방식을 두가지 정도로 나눌 수 있긴 하다. 탑다운과 바텀업. 정답을 구하기 위해 그 정답을 위한 하위 문제들을 호출하는 것이 탑다운. 필요한 것들만 찾아 들어가는 것이다. 그리고 가장 작은 하위 문제들을 통해 가능한 답들을 찾아나가서 정답에 도달하는 것이 바텀업.
모든 dp는 그 두 가지로 접근할 수 있는 것이 아니다. 후자로만 풀 수 있는 케이스도 존재. 어떤 문제에 따라서는 바텀업은 불필요한 해도 찾는 케이스가 나올 것이다. 그래서 탐색 속도로만 따지면 탑다운이 대체로 유리하다.
전자는 재귀로, 후자는 반복으로. 그러나 재귀는 아무래도 조금 시간이 더 소요된다. 파이썬으로 재귀를 하면 많이 좋지 않다..
탑다운은 점화식과 초기조건만 아는 경우에 유용하다. 바텀업은 테이블이 채워지는 구조를 알 때 좋다.

dp의 종류. 트리dp. 비트마스킹 dp.

dp풀이 단계. 상태공간 정의. 중복되는 부분을 먼저 찾아야한다.  이후 상태 공간 사이의 관계식, 점화식을 찾는다.

알고리즘 설계기법은 크게 3가지. 완탐, 그리디, 동계. 그리고 동계는 완탐의 최적화 케이스.

회고 및 다짐

세미나가 끝난 후, 어쩌다가 다른 사람들과 이야기를 하게 됐는데 그 이야기가 엄청 길어졌다. 알고리즘 이야기도 했다가 끝내는 철학 이야기까지 가게 됐는데 왜냐, 나는 철학과에서 컴과로 넘어오는 케이스인데 마침 이 소모임 운영진 중 한 명이 컴과에서 철학과 복전을 하고 있더라는 것. 어째서 그런 결정을 내렸을까.. 싶은데 막상 이야기를 나눠보니 이 친구는 확실히 철학을 좋아할 만한 친구다, 싶었다. 이야기가 엄청 길어져서 거의 한 시간은 떠들었다. 이런 이야기들은 술을 마시면서 분위기 있게 하는 게 최고인데.. 아쉽구만.

dp는 내가 참 취약한 영역이었는데, 공부를 계속 하다보니 이제 슬슬 머릿속에서 정리가 되는 게 있는 것 같다. 하지만 결국 실전에서 어떻게 내가 적응하느냐가 관건이겠지.