MIT-6.006_with_Rust

소개

이 저장소는 MIT 6.006 Introduction to Algorithms 강의를 기반으로 알고리즘과 자료구조를 Rust로 구현한 프로젝트입니다.

참고자료

• 다음 자료를 주로 참고하였습니다.
  • MIT 6.006 Introduction to Algorithms, Fall 2011, 부스트코스에서 제공하는 한국어 자료
  • RobEdwards - Data Structures, 부스트코스에서 제공하는 한국어 자료 - 자료구조의 실제 코드 상의 구현을 참고하였습니다.
  • TODO: 진행하면서 주로 참고한 자료들 추가

프로젝트 진행 순서

• Rust를 사용해서 알고리즘, 자료구조를 구현합니다.
• 코드의 시간 복잡도를 계산해서, 동일한(최대한 유사한) 시간/공간 복잡도를 가진다는 것을 증명합니다.
  • 이를 위해서 사용하는 함수나 기능의 시간/공간 복잡도를 정리합니다. (TODO: 이건 좀 너무 간거 같기도 하고, 시간 복잡도는 사용하는 기능이 적으면 충분히 가능할지도? 공간 복잡도가 문제일듯.)
• 테스트를 통해서 시간/공간 복잡도를 검증합니다. (TODO: C로 자료구조 구현할때도 성능 측정에 문제가 있었어서, 고민해보고 추후 도입할 예정)

목적

비전공자로서 개발자로 성장하기 위해 전공자 수준의 이해를 목표로 다양한 노력을 기울이고 있습니다.
그 일환으로, 자료구조와 알고리즘을 깊이 이해하기 위한 프로젝트입니다.

특히 실습을 통해 보다 깊이 있는 학습을 할 수 있다고 생각하며, Rust 언어로 직접 구현하고 검증하는 과정을 통해 이를 체계적으로 다지고자 합니다.

추가 정보

TODO: 이 부분 보완하기

• Rust를 사용하는 이유?
  • 저수준 언어를 사용하는 것이 학습에 더 도움이 될거라고 판단함. 성능 측정에서도 GC 등의 문제가 없고...
  • 백엔드 개발자로서의 커리어에서 C/C++은 사용비율이 Rust에 비해서 적음.
  • C/C++을 능숙하게 다루기 어려움. C는 막말로, 함정이 너무 많은 언어이다. C++은 너무 많은 기능이 있다.
  • 회사에서 정말 일부지만, Rust를 사용하고 있음.
• 왜 이 6.006 강의인가?
  • Introduction to Algorithms 책을 쓴 MIT에서 제공하는 강의.
    • Introduction to Algorithms는 여러 대학/논문에서도 참고하는 신뢰성 높은 자료.
  • 한번 할때 제대로 진행하고 싶음. 나중에 복습하기도 편하고...
• C에서 자료구조를 구현하며 겪었던 문제는?
  • 이론/구현 상 시간복잡도가 다른 코드를 실행해도, 하드웨어 성능이 높은 편이라 시간이 거의 동일한 문제.
  • 시간/공간 복잡성 비교를 위해서, 적절한 라이브러리가 없어서 코드를 구현해야 하는데, 신뢰성이 떨어짐. (나의 C/C++의 구현 능력을 신뢰할 수 없음.)
  • 메모리 관리를 직접 해야하는데, 요소, 자료구조의 생명주기를 관리하는데 어려움을 겪음. (이런 어려움을 Rust를 사용했을 때는 덜 수 있을꺼라 판단함. e.g. Vec의 get과 remove의 차이를 통해서 용도를 구분하고, memory-safe함을 보장.)
  • TODO: 이러한 문제를 해결하기 위한 여러 해결 방법을 고민하고, 같은 문제를 겪지 않게 예방하기.

LICENSE

MIT