나름 개발자의 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사람들이 얼마나 모여야 생일이 같은 사람이 존재할 수 있을까?비둘기집의 원리에 ..

가장 쉬운 문자열 자료구조나 알고리즘은 무엇일까? 아마 트라이정도가 있을 것이다. 이런 트라이도 상당히 고난이도의 자료구조에 속하기 때문에 문자열을 사용하는 자료구조나 알고리즘은 많이 어렵다. 문자열의 꽃이라고 볼 수 있는 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..

작년에 이어 올해도 여전히 현대모비스 알고리즘 대회가 열린다! 일반인이 참여할 수 있는 몇 안되는 대회이기 때문에 보자마자 참가할 수밖에 없었다. 여느 때와 마찬가지로 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로 바꿀 수 있는 마지막 기회를 준다는 문자를 받았다. ㅋㅋ 이 문자를 받고 겁쟁이..

나는 지금 백엔드(서버) 개발자로 일을 하고 있는데 PS하던 경험이 개발에 알게 모르게 도움이 될 때가 많다. 어떤 것들이 있고 어떤 도움이 되는지 내 생각을 말해보고자 한다. 구현능력 솔브드 8대 태그에도 있는 구현은 알고리즘문제를 풀기 위한 기본 소양이다. 실제로 브론즈의 대부분 문제는 구현이 들어있고 알고리즘 문제를 풀기 위한 과정도 구현이다. 이러한 경험을 실제 개발에도 적용하면 비즈니스 로직 구현하는데 도움이 된다고 느꼈다. 다만 아키텍처 설계는 별개이다. 그리고 1000문제를 해결했다면 문제당 코드 길이가 평균 50줄이라고 해도 5만 라인을 작성한 것이다. 이 정도라면 코드짜는 자신감과 타이핑속도 등을 얻을 수 있다. (자신감 의외로 중요하다.) 구현능력을 테스트하고 싶다면 유효기간이 있는 마..

2월 3일 최초로 솔브드에서 열리는 그랜드 아레나가 온사이트로 열리게 되었다. 이런 이벤트를 너무 좋아하는 나에겐 반드시 참여하고 싶은 이벤트였다. 성적이 좋거나 아레나를 많이 참여할수록 참가 확률이 높다고 하는데 Arena #10부터 모두 참가한 나는 어렵지 않게 참가할 수 있었다. (#10은 운영자로 카운팅되었다!) 그동안 SS~SS+퍼포먼스를 받아서 Div 1에 배정받았다. 알고리즘하는 지인들은 아레나에 참여하지 않아서 당첨되지 않아 혼자서 참석하게 되었다.. Grand Arena Onsite 지금까지 이런 온사이트 이벤트는 구데기카페, 보드게임카페와 더불어 3번째였다. 풍성한 기념품들을 받을 수 있었다. 역시 utilforever님이 후원을 해주셨고 현장에 계셨다. 지난 KUPC때 함께 모니터링을..

덱은 double-ended queue를 줄인것이다. 이름에서 알 수 있듯이 양쪽으로 넣고 뺄 수 있는 큐를 의미한다. 기초 자료구조이지만 여기에 숨어있는 신기한 사실이 있다. 시간복잡도 덱의 장점은 앞, 뒤 어디서든지 삽입삭제가 $O(1)$이라는 것이다. 보통 학부 과정에서 덱을 구현하라는 과제를 받으면 리스트로 구현하여 삽입삭제를 $O(1)$로 끝내고 random access를 $O(N)$에 동작하도록 구현하게 된다. 하지만 실제로 내장된 deque를 사용해보면 어떨까? # python from collections import deque import time N = 1000000 arr = [i for i in range(N)] s = 0 start = time.time() for i in rang..