-
Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals Introduction 어떠한 순열 $\pi = (\pi_1, \ldots, \pi_n)$ 에 대해서 순열의 몇 개 원소에 $-1$ 을 곱해서 만들 수 있는 수열들을 signed permutation (부호 있는 순열) 이라고 하자. 이 수열에 우리는 뒤집기 라는 연산을 할 수 있는데, 뒤집기 연산 $r(i, j)$ 는 구간 $[i, j]$ 에 대해서 구간의 원소에 $-1$ 을 곱하고 구간을 뒤집는 것을 뜻한다. 즉, $\pi$ 에 뒤집기 연산 $r(i, j)$ 를 수행하면,...
-
Wireless Digital Communication 6
서론 지난 글에서는 OFDM이란 무엇인지, 또 OFDM과 FFT/IFFT 와는 어떤 관계가 있는 지에 대해 알아보았습니다. 제가 처음 글에서 OFDM이라는 시스템은 ISI를 줄이기 위해 고안한 시스템이라는 설명을 했었습니다. 과연 어떤 방식으로 ISI를 줄이는 지 설명하고, OFDM의 전체적인 구조를 설명한 뒤에 글을 마치겠습니다. 이 글이 해당 시리즈의 마지막 글이 될 예정입니다. 마지막까지 잘 따라와주시면 감사하겠습니다. 본론 지난 글에서는 채널이 없다고 가정을 하였고, 따라서 ISI에 대한 생각은 하지 않아도 됐습니다. 하지만 실제로는 모든 신호는 어떤 특정한 채널을 거치게...
-
MRI imaging과 Parallel Imaging Algorithm, 그리고 PRUNO
Introduction MRI (Magnetic Resonance Imaging)은 X-Ray, CT와 함께 널리 쓰이는 의료 영상 기법으로 손꼽힙니다. 이미지 특성 상 가장 좋은 연부 조직 대비 (soft matter contrast)를 보여줍니다. 즉, 근육이나 뇌 등 수분을 많이 포함하는 조직에 대해 가장 월등한 이미지 품질을 낼 수 있습니다. 다만 MRI의 경우 짧게는 30분에서 1시간 정도 되는 긴 촬영 시간이 단점으로 꼽히는데, 때문에 시간 단축을 위한 다양한 기법이 제시되고 있습니다. MRI는 촬영한 raw data가 전자기파 신호이기 때문에, 특이하게도 이를 푸리에 변환을 비롯한...
-
프로그래밍 대회 출제 체크리스트
개요 PS가 보다 대중에게 친숙해지면서 여러 종류의 프로그래밍 대회도 점점 많아지고 있습니다. 특히 기관이나 기업이 아닌 일반인이 주최하는 대회가 부쩍 늘었는데, 대표적인 것이 대학교 대회라고 할 수 있습니다. 모두에게 친숙한 백준 온라인 저지에서도 BOJ Stack을 통해 손쉽게 대회를 준비할 수 있는 플랫폼을 만들어 어느 정도 PS에 경험이 있다면 누구나 쉽게 대회 개최에 참여할 수 있게 되었습니다. 반면에 아마추어가 쉽게 대회를 열 수 있다는 점은 반대로 준비가 덜 된, 낮은 퀄리티의 문제가 쉽게 양산될 수도 있다는...
-
랜덤한 교란 순열을 생성하는 card-based 프로토콜 (1)
1. Introduction Symmetric group $S_n$의 원소, 즉, $[n]$ 상의 순열 가운데 fixed point가 없는 것들을 Derangement(교란 순열)이라고 부른다. 이제, 한 가지 예를 들어, $n$ 명의 학생이 있는 학급에서 마니또 행사를 한다고 가정해보자. 학생 $i$의 마니또가 $p_i$라 할 때, $p_i \neq i$ 여야 하며, $i \neq j$ 이면, $p_i \neq p_j$ 여야 할 것이다. 즉, ${p_i}$ 가 derangement 여야 한다. 또한, 학생 $i$는 $p_i$의 값 외에 다른 정보를 알지 않아야 한다. 이렇듯, 현실에는 각자 자신에게 배정된 수...