-
Linear Suffix Array Construction
제가 최근에 작업을 하면서 큰 문자열에서 다른 작은 문자열을 많이 찾을 필요가 있었습니다. 정확히는, 이런 일을 해야 할 필요가 있었습니다. 문자열 $T$가 주어집니다. 문자열 $S_{1}$, $S_{2}$, $\cdots$, $S_{K}$가 $T$에서 등장하는 횟수를 구해야 합니다. 모든 정수 $1 \leq i < K$에 대해, $S_{1}$, $S_{2}$, $\cdots$, $S_{i}$에 대한 답을 구한 이후에야 $S_{i+1}$을 알 수 있습니다. 이 조건은 실제 문제 상황보다는 조금 빡빡한 제한이지만, 이렇게 가정해도 큰 무리는 없습니다. 이 상황이 다른 일반적인 상황과 크게 다른 점은 이렇습니다....
-
Cryptanalytic Extraction of Neural Network Models
1. Introduction 이번 글에서는 암호학 분야에서 탑 티어 컨퍼런스 중 하나인 CRYPTO 2020에 통과된 Cryptanalytic Extraction of Neural Network Models 논문에 대해 알아보고자 합니다. 보통 암호학에서 인공지능을 활용할 때나 반대로 인공지능에서 암호학을 활용할 때에는 해당 기술을 마치 블랙박스와 같이 두고 결과를 가져다 쓰는 방식으로 진행되기 마련인데 이 논문에서는 그게 아니고 Neural Network Model의 Extraction을 하는 상황이 곧 암호학에서 아주 유명한 공격인 차분 공격을 하는 상황과 유사하다는 것을 이용해 Neural Network Model에 대한 Extraction을 기존의 방법들보다...
-
알고리즘 문제 접근 과정 5
알고리즘 문제 접근 과정 5 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 두 배열의 합 - KOI 2001 고등부 1번 관찰 우리가 생각해볼 수 있는 가장 쉬운 방법은 무엇이 있을까요? 아마 문제에서 나온 방법을 그대로 사용하는 것이 가장 편한 방법일 것입니다. 우리가 만들 수 있는...
-
컴퓨터 과학의 미해결 문제들
개요 수학에는 많은 난제들이 있습니다. 전세계적으로 유명한 밀레니엄 문제가 대표적입니다. 인지도 있고 학술적 가치가 높은 난제는 하나를 해결하는 것이 평생의 업적이 되기도 합니다. 많은 난제들이 꾸준히 풀리고 있지만, 새로운 문제가 창조되는 것에도 역시 끝이 없습니다. 난제의 범위를 컴퓨터 과학으로 좁혀봅시다. 대표적인 것으로는 밀레니엄 문제의 일부이기도 한 P-NP 문제가 있습니다. P-NP 문제는 너무나 유명해서 이 글을 읽을 사람이라면 누구나 한 번쯤은 들어보았을 것입니다. 하지만 그 외에 다른 컴퓨터 과학 난제는 그다지 널리 알려진 것이 없는 것...
-
2021 ICPC Seoul Regional
2021 ICPC Seoul Regional 이 글에서는 2021 ICPC Seoul Regional의 문제 풀이를 다룬다. 올해 문제는 예년 비해서 상당히 어렵게 출제된 편이다. 거의 모든 해에서 우승 팀이 모든 문제를 풀었고, 그렇지 않은 해 (2015, 2018 등) 에도 웬만하면 한 문제 빼고 다 풀었다는 점을 감안하면 상당히 이례적이다. 다만 모든 문제를 푸는 난이도는 솔직히 2018년이 더 어렵지 않나 싶다. 솔직히 말해서 문제가 자꾸 봤던 유형에서 계속 재탕 삼탕하는 느낌이 너무 강하다. 어느 정도야 그럴 수 있겠지만 올해는...