-
임의의 원소를 수정할 수 있는 우선순위 큐
서론 힙 (Heap)은 그 간단한 구조와 시간 / 공간 측면에서의 여러 장점들 때문에 문제 풀이뿐만 아니라 실무에서도 우선순위 큐로서 널리 애용되는 자료구조입니다. C++의 std::priority_queue, Java의 java.util.PriorityQueue, Python의 heapq1 등 고수준 언어의 자료구조 라이브러리에서 웬만하면 지원을 해주기도 합니다. 우선순위 큐를 라이브러리로만 접하면 기능이 매우 적은 것에 대해 실망할 수도 있습니다. 대체로 원소를 삽입하는 기능과, 최대 혹은 최솟값을 확인하고 제거하는 연산이 전부이기 때문입니다. 그런데 사실 힙에는 그 외에도 많은 가능성들이 숨어있습니다. 단순한 형태의 구현체에서는 수행하기 어려운 연산들을...
-
Dictionary 기반 압축 알고리즘
안녕하세요? 오늘은 저번 글에 이어, 압축 알고리즘에 대한 설명을 추가로 진행해보려 합니다. Dictionary Type Data Compression 저번 글에서 소개드린 데이터 압축 기술은 대부분 data entropy를 기반으로 되어 있습니다. 다시 말해, 전체 데이터의 빈도 수를 세고 빈도가 높은 것에 작은 길이의 bit를 할당하는 방식으로 작동하며 data entropy와 최종 압축률이 거의 유사한 값을 가지게 됩니다. 이번 글에서 살펴볼 방법들은 그와는 약간 다른, 출현하는 패턴들을 기억하는 dictionary를 사용하는 압축 방법들입니다. 다만, dictionary type data compression 또한 반복되는 패턴이...
-
RSA Puzzles
서론 RSA는 공개키 암호의 일종으로, 공개키를 통해 평문을 암호화할 수 있으며 비밀키를 통해 암호문을 복호화할 수 있습니다. 이 때 비밀키로부터 공개키를 구할 수는 있지만, 공개키로부터 비밀키를 구하기는 어렵다는 비대칭적 특징을 지닙니다. 일반적으로 RSA에 대한 공격이라고 한다면 공개키만을 갖고 있는 상황에서 비밀키를 구할 수 있는 방법을 의미하곤 합니다. 예를 들어 RSA는 공개키 $(e, N)$과 비밀키 $(d, N)$으로 구성되는데, $N$를 소인수분해해 $N$을 이루는 두 소수 $p, q\ (N = pq)$를 구하거나 암호문으로부터 비밀키의 값을 모르는 상태로 평문...
-
sentiment analysis
Sentiment Analysis Contents 감정 분석이란 자연어처리 구현 마치며 참고자료 감정 분석이란 감정 분석은 일종의 자연어처리에 속하는 인공지능 과제 중 하나입니다. 여기서 자연어처리는 간단하게 사람간의 발화, 또는 이로 이루어진 문장 그리고 지문의 감정을 분석하는 것을 의미합니다. 감정이란 사람이 생각하는 사고와 그에 따른 의견에 의해 느끼고, 나타나는 것을 말합니다. 따라서 감정분석이라는 것은, 텍스트 또는 실제 발화에서 나타나는 그 사람의 태도, 의견, 성향을 분석할 수 있어야 합니다. 자연어처리중에서도 감정 분석은 상당히 어려운 분야로 취급됩니다. 이는 같은 의견이라도 사람의...
-
Monad Transformer In Scala
안녕하세요~ 오늘은 Monad Transformer 에 대해서 포스팅해보려고 합니다 ㅎㅎ » 이 글을 좀 더 좋은 가독성으로 읽기 « Monad Transformer 란? 자, 다음과 같이 간단한 코드가 있습니다. case class User(id: String, bestFriendId: String) def getUser(userId: String): Future[Option[User]] = ??? def getBestFriendOfUser(userId: String): Future[Option[User]] = for { userOpt <- getUser(userId) bestFriendIdOpt = userOpt.map(_.bestFriendId) bestFriendOpt <- bestFriendIdOpt match { case Some(bestFriendId) => getUser(bestFriendId) case None => Future.successful(None) } } yield bestFriendOpt getBestFriendOfUser 함수를 보면 Future 와 Option...