대학일기

재작년 쯤 Flowgorithm이란 프로그램을 접하고 간단한 알고리듬을 몇 개 만들어 보면서 위키독스와 유튜브에 올렸다. https://wikidocs.net/book/8077 이번 학기에 알고리즘 과목을 수강하며 한두 가지 더 만들었더니 누가 유튜브 댓글로 배낭(knapsack) 문제를 풀 수 있냐고 물어본다. 배낭 문제는 작년에 교정한 책에 실렸고 이번 학기에도 배웠는데도 잘 이해하지 못해서, 강의를 다시 보고 나서 한참 끙끙대며 풀었다. 하고 나니 그리 어렵지 않다. 0-1 Knapsack(0-1 배낭) with Flowgorithm https://youtu.be/YsTETO3pBn4

플로이드-워셜 알고리듬이 이해하기는 어려워도 의사코드가 단순해서 Flowgorthm으로 만들 수 있을 것 같아 보였다. 직접 실습해 보니 설명만 들었을 때보다는 조금 더 알 것 같다. https://wikidocs.net/238497 2. 플로이드-워셜 알고리듬플로이드-워셜(Floyd-Warshall) 알고리듬은 동적계획법으로 모든 정점 간의 최단 경로를 찾습니다. 주어진 그래프의 인접 행렬을 이용하여 각 단계에서 정점을 거치는 경우와…wikidocs.net

작년에 입학하고 열심히 공부하다가 점점 게을러져서, 요즘은 작년 이맘때에 비해 공부를 반의 반도 안 하는 것 같다. 20년 전이긴 하지만 알고리즘 과목을 이미 수강했고 근래에 알고리즘 책을 교정한 적도 있으니, 이번 학기 수업을 안 들었더라도 어느 정도 문제를 풀 수 있어야 한다. 하지만 첫 문제를 보자마자 헛웃음이 나왔다. 각 문제에서 묻는 알고리즘이 어떻게 작동하는지 대략 이해하면 풀 수 있는 것들이었지만, 그것도 몰라서 부랴부랴 교안을 보면서 예제의 풀이 방법에 문제를 끼워맞추려 애썼다. 점수가 얼마나 나올지 궁금하다. 답을 틀린 문제는 다시 풀어보려고 화면을 캡처해 뒀다.

집합 커버(set cover) 문제를 설명하면서, 신도시를 지을 때 학교를 어디에 배치하는지 정하는 문제를 예로 들었다. 집합 커버는 집합에 관한 문제이고 신도시 학교 배치는 그래프 문제인데, 왜 그래프 문제를 집합 문제로 바꿔서 푸는지 의아했다. 챗GPT에 보여주니 이것은 dominating set problem이고, set cover 문제와 본질적으로 같은 문제는 아니지만 상호 변환 가능하다고 한다. 위키백과에는 이렇게 나와 있다. 최소 지배 집합(minimum dominating set) 문제와 집합 커버 문제는 L-환원(L-reduction)하에서 동등하다. 한 문제의 인스턴스가 주어지면 다른 문제의 동등한 인스턴스를 구성할 수 있다. https://en.wikipedia.org/wiki/Domi..

토론 게시판에 올린 글: 송○○ 학우께서 무인기의 자율비행에 관해 말씀하신 것을 보고, 제 전공과 관련이 있어서 그에 관해 조사했습니다. 자율비행에 사용되는 알고리즘으로는 여러 가지가 있습니다. 예를 들어, MIT 연구진은 기동성과 다양성을 갖춘 고정익 항공기인 '테일시터'의 경로 계획과 제어에 새로운 알고리즘을 개발하였습니다. 이 알고리즘은 복잡한 궤적을 실시간으로 계획하고 실행할 수 있는 능력을 갖추고 있으며, 이는 동적 환경에서 복잡한 움직임을 자율적으로 수행할 수 있게 합니다. https://news.mit.edu/2023/planning-algorithm-tailsitter-aircraft-0823 또한, 강화 학습을 기반으로 한 모듈러 학습 방식도 자율비행에 사용됩니다. 이 방식은 복잡한 작업..

3주차에 퀵 정렬이 나왔다. 위키독스에 쓴 Flowgorithm 책에 정렬 알고리듬을 몇 개 올려뒀었는데 퀵 정렬은 없어서 이번에 풀었다. https://wikidocs.net/235167