나름 개발자의 IT블로그

Splay Tree 를 사용하면 백준 태그에 Splay Tree가 붙은 문제 외에도 많은 문제를 해결할 수 있다. 여기에서 해결할 수 있는 문제들을 유형별로 정리하고 풀이를 간단하게 소개한다. 문제의 순서는 난이도 순이 아닐 수 있다. 기본 연산 유형Splay Tree는 값의 insert, delete, find연산을 지원한다. 이를 사용하여 해결할 수 있는 문제들이다.11723. 집합원래는 비트마스킹 연습하라고 메모리가 적게 세팅된 문제이지만 Splay Tree를 잘 구현하면 제한 안에 통과할 수 있다. Splay Tree를 연습하기 좋다. insert와 delete, find같은 기본 연산만으로 해결할 수 있다.1269. 대칭 차집합11723을 해결하며 toggle을 잘 구현했다면 toggle만으로 ..

Splay Tree는 Balanced Binary Search Tree의 한 종류로 데이터의 삽입, 삭제, 탐색을 $O(\log N)$에 준하는 속도로 처리할 수 있도록 하는 자료구조이다. 보통 학부과정에선 저런 기본 연산들을 배우게 되는데 Splay Tree를 사용해야만 해결할 수 있는 알고리즘 문제에서는 극한의 테크닉을 사용하여 많은 쿼리를 처리할 수 있다. 이 글에서는 Splay Tree가 어떤 자료구조인지 소개하기보다는 해결할 수 있는 application을 중점으로 소개한다. Splay Tree는 1985년에 Self-Adjusting Binary Search Tree라는 논문으로 소개가 되었고 여기에도 Tarjan이 저자로 들어가있다. 정말 많은 공헌을 하신 분이다. BasicSplay Tre..

소인수분해를 하는 가장 쉬운 방법은 약수를 구하듯이 $\sqrt N$까지 검사하며 나누어질 경우 인수로 가져가는 방식이 있을 것이다. 이러한 방법도 괜찮지만 $N \le 10^{18}$정도 된다면 TLE가 나는 느린 방법이다. 위 방법의 시간복잡도는 $\sqrt N$이지만 입력이 숫자이기 때문에 복잡도상으로 보면 지수시간을 가지는 느린 알고리즘이다. 소인수분해는 그만큼 어려운 문제이기 때문에 암호에도 많이 쓴다. 위 방법보다 빠르고 $10^{18}$범위까지 해결할 수 있는 Pollard rho 알고리즘에 대해 알아보자. Pollard rho를 이해하기 위해 몰라도 되지만 알면 좋은 사전지식이 있다.Birthday Paradox사람들이 얼마나 모여야 생일이 같은 사람이 존재할 수 있을까?비둘기집의 원리에 ..

우리는 암호를 왜 사용할까? 어떠한 정보에 도달하기 위해 내가 그 정보에 도달할 수 있는 유효한 사람임을 증명하기 위해 사용할 것이다. 예를 들어 웹사이트에서 나의 정보를 얻기 위해 나라는 것을 증명하기 위해 로그인을 하는 행위가 있을 것이다. 굉장히 심플한 방법이지만 보통 로그인을 할 때 패스워드를 서버에 보내서 서버에 있는 패스워드와 일치하는지 확인하는 방법을 사용하기 때문에 서버에 패스워드를 보내는 행위 자체가 찝찝할 수 있다. Zero Knowledge Proof어떤 문제를 해결하려는 사람 $P$(Prover)와 $P$가 제출한 데이터가 유효한지 검증하는 $V$(Verifier)가 있다고 하자. $P$는 $V$에게 어떤 데이터 $X$를 알고있다는 사실을 알려주고 싶다. 여기에서 $X$에 대한 정보..

가장 쉬운 문자열 자료구조나 알고리즘은 무엇일까? 아마 트라이정도가 있을 것이다. 이런 트라이도 상당히 고난이도의 자료구조에 속하기 때문에 문자열을 사용하는 자료구조나 알고리즘은 많이 어렵다. 문자열의 꽃이라고 볼 수 있는 Suffix 자료구조도 굉장히 고난이도에 속한다. 우리나라에서는 Suffix Array나 Suffix Tree (Suffix Trie) 등이 알려져있지만 Suffix Automaton은 잘 알려져있지 않다. 여기에서는 엄밀한 증명은 제외하고 Suffix Automaton이 무엇인지 알아보도록 한다. Automaton이름에서 볼 수 있듯이 Suffix Automaton은 어떤 문자열의 Suffix로 Automaton을 그린 것이다. Automaton가 뭔지 모른다면 여기를 참고하자. S..

CLRS 한글판을 보면 목차에 푸시-재명명, 재명명후-앞보내기 알고리즘이라고 있다. 뭔가 힙하고 새로워보이는 알고리즘같아 살펴보니 Push-Relabel을 한국어로 번역하다가 나온 이름이었다. (...) 그런 의미에서 이번 포스트에서는 Push-Relabel에 대해 알아본다. Push-Relabel도 1984년에 나온 비교적 최신 논문에 들어있다. SCC로 유명한 Tarjan이 저자로 있다! 해당 논문에 명시적으로 Push-Relabel이라는 알고리즘 이름은 없지만 전해 내려오면서 지어진 이름인 것 같다. 소개네트워크에서 전송 가능한 데이터를 계산하는 등 유량을 계산하는 것은 중요하다. Push-Relabel도 이러한 최대 유량을 구하는 알고리즘이며 $O(NM^2)$을 가지는 에드먼드 카프나 $O(N^2..

Berlekamp-Massey 알고리즘은 내가 가장 좋아하는 알고리즘 중 하나이다. 지금까지 이 알고리즘을 블랙박스 형태로 내부 동작을 모르는 채 사용했지만 이번 기회에 한 번 알아보는 것도 좋을 것 같아서 찾아보게 되었다. (몰라도 쓰는데 문제는 없다.) Shift-Register Synthesis and BCH Decoding 이라는 1969년에 나온 오래되고 클래식한 논문에 있는 알고리즘이었다. 정말 정말 좋은 리소스가 있어서 쉽게 접할 수 있었다. 엄밀한 증명은 하지 않고 어떻게 동작하는지만 남긴다. 선형 점화식DP에도 많이 나오는 선형 점화식은 1차원 수열상에서 이전 몇 개의 항들의 선형 결합을 통해 다음 항을 만드는 수열이 된다.$a_{i} = \displaystyle\sum_{j=1}^n c..

SQL과 NoSQL의 차이가 무엇인가요? 누군가가 위와 같은 질문을 한다면 무엇이라고 답하나요? 질문한 사람은 면접관, 친구 또는 동료가 될 수 있습니다.관계형 DB vs 비관계형 DB스키마가 정적임 vs 동적임MySQL, PostgreSQL이 있음 vs MongoDB, DynamoDB가 있음등등.. 각자 자신만의 방식으로 답변을 할 것 같습니다.  최근에 저는 이러한 질문을 받으면 그 히스토리에서 답을 찾는 방법에 감동을 받아서 해당 내용으로 답변해보고자 합니다.SQL데이터베이스는 언제부터 필요했을까요? 아마 컴퓨터가 사용되기 시작하고 데이터가 많아짐에 따라 관리되기 시작했을겁니다. 더 이상 파일만으로 관리하기 힘들고 복잡한 join연산과 집계를 위해 데이터베이스에 대한 수요가 나타나기 시작했습니다. ..

작년에 이어 올해도 여전히 현대모비스 알고리즘 대회가 열린다! 일반인이 참여할 수 있는 몇 안되는 대회이기 때문에 보자마자 참가할 수밖에 없었다. 여느 때와 마찬가지로 1등은 자동차를 주고 20등까지 아이패드를 준다. 하지만 올해는 21등부터 명시적인 상품이 없었다. 아무튼 대회를 참가했다. 예선예선은 3시간동안 프로그래머스에서 진행됐고 4문제가 출제됐다. 예선은 적당히 어려운 난이도로 편성되며(작년 기준 프로그래머스 3~5레벨) 상위 50명이 본선에 출전하게 된다! 아무래도 학생부에 현역으로 잘하는 사람이 많고 일반부에는 PS 은퇴(?)한 사람이 많을테니 일반부가 커트라인이 낮다. 다행히 나는 졸업하고 직장다니고 있기에 상대적으로 클린한(?) 일반부로 신청했다. 문제가 공개되지 않아 최소한의 후기만 남..

https://www.acmicpc.net/board/view/143175https://scpc.p-e.kr/ 서울대학교에서 외부인도 참가할 수 있는 오프라인 대회를 개최했다! 당연히 참을 수 없어서 보자마자 참가신청을 넣었고 대회에 참여했다. Before Contest서울대는 중학생때 숙제하러 한 번 오고 처음오는데 이제 와서 보니 정말 컸다. 학교 안에서 호기롭게 혼자 버스 안타고 걸어가다가 땀 흘리면서 강행군을 했다;; 서울대에서 연강걸리면 버스타고 다녀야되는 것 같다. 산으로 뒤덮여있어 정기를 받기 좋았던 것 같다.처음 신청할 때 생각없이 Div 1로 신청했는데 대회 3일 전쯤에 Div 1은 정말 어려우니 Div 2로 바꿀 수 있는 마지막 기회를 준다는 문자를 받았다. ㅋㅋ 이 문자를 받고 겁쟁이..