Samsung Software Membership
    • BLOG
    • ABOUT US

    S/W 멤버십 기술 블로그

    • RBTree's profile image

      RBTree

      February 20, 2021

      Gröbner basis

      서론 최근 다변수 Coppersmith Method와 관련해 살펴보면서 Gröbner basis, 한국어로는 그뢰브너 기저에 대해서 접하게 되었습니다. 다변수 Coppersmith Method의 과정을 간략하게 설명하자면 다음과 같습니다. 변수 $x_1, x_2, \dots, x_k$에 대한 어떤 modular equation $f(x_1, x_2, \dots, x_k) \equiv 0 \pmod n$을 풀고 싶다. 단, $x_1, x_2, \dots, x_k$는 $n$에 비해서 매우 작다. Howgrave-Graham Theorem과 LLL algorithm을 적용해 $g_1(x_1, x_2, \dots, x_k) = 0, g_2(x_1, x_2, \dots, x_k) = 0, \cdots, g_l(x_1, x_2, \dots, x_k) = 0$...

      cryptography

    • blisstoner's profile image

      blisstoner

      February 20, 2021

      Multi-Party Computation 1

      1. Introduction 두 부자 Alice와 Bob이 있다. 두 명은 상대방에게 자신의 재산이 얼마인지 공개하지 않고 누구의 재산이 더 많은지 비교하고 싶다. 라는 문제를 생각해봅시다. 사실 이 문제를 해결하는 방법은 굉장히 간단합니다. Alice와 Bob이 모두 신뢰할 수 있는 Charlie가 있다면 Alice와 Bob이 Charlie에게 자신의 재산을 알려주고 Charlie가 비교를 한 후 누가 더 재산이 많은지를 두 사람에게 알려주면 됩니다. 하지만 두 사람이 모두 신뢰할 수 있는 제 3자가 없다면 상황이 많이 복잡해집니다. 결국 대소를 비교하려면 양쪽의 값을...

      Cryptography

    • jh05013's profile image

      jh05013

      February 20, 2021

      접미사 트리 (파트 1: 정의와 응용)

      이 글은 트라이(trie) 자료구조에 대한 배경지식을 전제로 합니다. 부분문자열에 대한 다양한 문제를 선형 시간에 해결할 수 있는 접미사 트리 자료구조를 소개합니다. 이론 및 구현은 쉽지 않지만, 여러 문자열 문제들을 자명하게 만들거나 더 어려운 문자열 문제들을 해결하는 데 유용하게 쓸 수 있습니다. 문자열 $S$의 길이를 $m$이라고 하고, $i$번째부터 $j$번째까지 글자로 이루어진 부분문자열을 $S[i..j]$로 표기하겠습니다. 접미사 트라이 먼저, $S$의 모든 접미사로 이루어진 트라이를 생각해 봅시다. 이를 접미사 트라이(suffix trie)라고 합니다. 예를 들어 아래는 문자열 banana에 대한 접미사...

      string data-structure

    • cheetose's profile image

      cheetose

      February 20, 2021

      압축 트라이 (Compressed Trie)

      서론 본 글에서는 트라이를 압축하여 트라이의 깊이를 $O(\sqrt (\sum \vert S \vert))$로 만드는 기법에 대해 설명하고자 합니다. 해당 방법은 트라이와 라빈-카프 알고리즘에 대한 선행 개념이 필요합니다. 해당 개념을 모르는 사람들을 위해 아래에 간략하게 설명하겠습니다. 트라이는 접두사 트리로, 어떤 문자열 집합의 prefix를 관리하는 자료구조입니다. 예를 들어 문자열 집합이 {“baby”, “bank”, “be”, “bed”, “box”, “dad”, “dance”}라면 이 집합을 표현한 트라이는 아래 그림과 같습니다. 이 때 붉은색 테두리는 여기서 끝나는 문자열이 존재한다는 것을 의미합니다. 이를 앞으로 valid한 노드라고...

      string data-structure

    • djm03178's profile image

      djm03178

      February 19, 2021

      '틀렸습니다'를 받지 않기 위한 팁

      개요 이전 글들에서 시간 복잡도를 고려한 코드 설계 전략과 PS에서의 런타임 에러와 디버깅에 대해 각각 다루어 보았습니다. ‘시간 초과’와 ‘런타임 에러’는 모두 오답 판정 중 특수한 경우에 해당하기 때문에 코드의 어떤 부분에 초점을 맞추어 디버깅을 해야 할지가 비교적 명확하고, 문제가 될 수 있는 유형도 어느 정도는 제한적이고 빈번히 발생하는 패턴들이 존재합니다. 특히 ‘런타임 에러’의 경우에는 백준 온라인 저지에서 얼마 전부터 런타임 에러의 종류를 공개하기 시작해서, 문제의 원인을 파악하기가 이전보다 훨씬 용이해졌습니다. 오답 판정 중 가장...

      wrong-answer

    • Previous Page
    • 74
    • 75
    • 76
    • 77
    • 78
    • Next Page
    • github
    • facebook
    • instagram
    • youtube
    • S/W Membership

    Copyright © SAMSUNG SOFTWARE MEMBERSHIP. All rights reserved.