-
jh05013's profile image
jh05013
September 18, 2022
도형의 합집합과 넓이
도형의 불리언 연산이란, 여러 도형의 영역에 대한 집합 연산을 말합니다. 두 원의 교집합의 넓이를 구하는 방법은 잘 알려져 있습니다. 부채꼴 2개의 넓이를 합친 다음, 이등변삼각형 2개의 넓이를 빼는 방식으로 구할 수 있습니다. 같은 방법으로 두 원의 합집합의 넓이도 구할 수 있습니다. 하지만 원이 3개만 되어도 이런 “포함 배제” 접근을 하기 어렵습니다. 이 글에서는 도형의 합집합 및 그 넓이를 구하는 일반적인 방법을 소개합니다. 테두리 따기 아래 그림에서 테두리가 갖고 있는 중요한 성질을 찾아봅시다. 테두리는 도형의 둘레로...
-
jh05013's profile image
jh05013
February 18, 2022
이동하기 4 (BOJ 18796)
이 글은 BOJ 18796 (이동하기 4)의 풀이를 다룹니다. 현재 이 문제의 solved.ac 티어는 루비 5입니다. 이 문제의 흥미로운 점은 지문이 거의 똑같은 문제가 무려 22티어나 낮은 브론즈 2라는 것입니다. 두 문제의 차이는 네 글자뿐이지만, 이는 x 방향으로 이동하는 비용이 x 좌표가 아니라 y 좌표에 의존하게 된다는 매우 치명적인 차이입니다. (물론 y 방향도 마찬가지입니다.) 60 +---+---+---+ +60-+60-+60-+ | | | | 10 90 80 70 20 +---+---+---+ +20-+20-+20-+ | | | | 10 90 80 70...
-
jh05013's profile image
jh05013
September 4, 2021
Persistent Data Structures
Persistent Introduction 과거의 상태를 보존하는 자료구조를 persistent data structure라고 합니다. 예를 들어, persistent array는 과거의 배열의 상태를 담고 있는 “버전”을 갖고 있습니다. 여기에 “버전 $x$에서 $i$번째 원소를 $d$로 바꿔서 버전 $y$를 만들어라”, 또는 “버전 $x$에서 $i$번째 원소의 값을 반환해라” 등의 연산을 적용할 수 있습니다. Persistent segment tree(PST)에 대한 자료는 인터넷에서 많이 찾아볼 수 있습니다. 하지만 persistence라는 개념은 segment tree에만 적용되는 것이 아닙니다. PST는 persistence를 지원하는 일반적인 방법을 segment tree에 적용한 것일 뿐, segment tree만을 위한...
-
jh05013's profile image
jh05013
June 20, 2021
스킵 리스트
서론 다음 연산을 모두 $O(logn)$에 지원하는 자료구조가 필요합니다. x를 추가한다. x를 삭제한다. x 이상의 원소 중 가장 작은 것을 출력한다. C++에서는 std::set가 바로 이 역할을 하지만, Python에는 이런 내장 라이브러리가 없습니다. 그래서 외부 라이브러리를 쓰지 않는 한 레드-블랙 트리나 AVL 트리 등을 직접 구현해야 하는데, 트리 자료구조는 보통 rebalancing 과정이 복잡합니다. 한편, 트리의 틀을 벗어나면 스킵 리스트 (Skip List)라는 자료구조가 있습니다. “평균”이라는 말에서 추측할 수 있듯이, 랜덤을 사용한다는 특징이 있습니다. AVL 트리 등에 비해 구현이...
-
jh05013's profile image
jh05013
April 11, 2021
접미사 트리 (파트 2: Ukkonen의 알고리즘)
이전 글에서 이어집니다. Ukkonen의 $O(m^3)$ 알고리즘 Ukkonen의 알고리즘은 접미사 트리를 $O(m)$에 만드는 알고리즘입니다. 하지만 이를 모두 설명하기에는 너무 복잡하니, 비효율적인 버전을 먼저 서술하고 시간 복잡도를 점차 줄여 나갑시다. (구현할 때도 파트 1을 먼저 구현하고, stress test 등으로 구현이 정확함을 확인하시는 것을 권합니다.) $S[1..i]$의 접미사 트리를 $I_i$라고 표기합시다. Ukkonen의 알고리즘의 큰 그림은 $I_1$에서 시작해서 이것을 $I_2$로 확장하고, $I_3$, $\cdots$, 마지막으로 $I_m$으로 확장하는 것입니다. $m$번째 글자가 끝 문자라고 가정하면 $I_m$의 모든 리프 노드와 접미사가 일대일 대응이 되지만,...
-
jh05013's profile image
jh05013
February 20, 2021
접미사 트리 (파트 1: 정의와 응용)
이 글은 트라이(trie) 자료구조에 대한 배경지식을 전제로 합니다. 부분문자열에 대한 다양한 문제를 선형 시간에 해결할 수 있는 접미사 트리 자료구조를 소개합니다. 이론 및 구현은 쉽지 않지만, 여러 문자열 문제들을 자명하게 만들거나 더 어려운 문자열 문제들을 해결하는 데 유용하게 쓸 수 있습니다. 문자열 $S$의 길이를 $m$이라고 하고, $i$번째부터 $j$번째까지 글자로 이루어진 부분문자열을 $S[i..j]$로 표기하겠습니다. 접미사 트라이 먼저, $S$의 모든 접미사로 이루어진 트라이를 생각해 봅시다. 이를 접미사 트라이(suffix trie)라고 합니다. 예를 들어 아래는 문자열 banana에 대한 접미사...
-
jh05013's profile image
jh05013
January 19, 2021
#P-완전성, 그리고 완전 매칭의 개수
이 글은 튜링 기계와 NP-complete에 대한 기본 배경지식을 전제로 합니다. 서론 이분 그래프가 주어졌을 때 최대 매칭을 구하는 문제는 알고리즘 문제 풀이에서 잘 알려져 있습니다. 심지어 일반적인 그래프가 주어져도 최대 매칭을 다항 시간에 구할 수 있습니다. 그러므로 완전 매칭이 존재하는지도 같은 방법으로 구할 수 있습니다. 하지만 완전 매칭의 개수를 구하라고 하면 어떻게 될까요? 카운팅 문제와 #P-완전 NP-완전성을 이야기할 때는 문제가 결정 문제로 한정됩니다. 예를 들어 최대 클릭 문제는 “가장 큰 클릭은 무엇인가?”가 아니라 “크기가 $k$...
-
jh05013's profile image
jh05013
November 21, 2020
프로그래밍 문제 출제하기
서론 삼성 소프트웨어 멤버십 블로그에는 대회 개최에 관한 글을 몇 개 찾아볼 수 있습니다. 대회 준비와 운영이 어떻게 진행되는지를 알 수 있는 유용한 글입니다. Acka1357님의 프로그래밍 대회를 개최하기 위한 10가지 djm03178님의 Codeforces #578, Codeforces #620 출제 후기 evenharder님의 UCPC 2020, KCPC 2018 출제 후기 hojoon0205님의 shake! 2019 출제 후기 이 글은 문제를 어떻게 만들 것인가에 초점을 둡니다. 아이디어를 어떻게 구상하고, 지문은 어떻게 작성하고, 데이터는 어떻게 만들고, 문제 검수는 어떻게 해야 하는지를 다룹니다. 백준 온라인 저지에...
-
jh05013's profile image
jh05013
September 20, 2020
S/W 멤버십 기술 블로그 고치기
이 블로그에 있는 버그와 문제점을 고쳤습니다. 태그 시스템이 제대로 동작하지 않습니다. 거의 모든 태그를 눌러도 404 오류가 나타납니다. 태그 기능을 추가하였습니다. 일부 글의 작성자가 표시되지 않습니다. 모두 올바르게 표시되도록 수정하였습니다. 일부 글이 표시되지 않습니다. 모두 보이도록 수정하였습니다. 검색 기능이 동작하지 않습니다. 정상 동작하도록 수정하였습니다. 사실 저는 알고리즘 문제풀이를 주로 하고, 실제 소프트웨어 등의 코드를 다뤄 본 경험은 별로 없습니다. 그래서 소프트웨어 디버깅의 일종의 체험과 배움을 하는 것에 의의를 뒀습니다. 이 글은 “단순히 어떤 버그가 있었고...
-
jh05013's profile image
jh05013
August 18, 2020
Karp의 21대 NP-완전 문제
Richard Karp는 알고리즘의 선두를 이끈 인물 중 한 명입니다. Problem solving을 하는 사람들에게는 Edmonds-Karp 최대 유량, Hopcroft-Karp 이분 매칭, Rabin-Karp 부분문자열 탐색 등으로 잘 알려져 있는데, 이 분의 업적으로 NP-완전성을 빼놓을 수 없습니다. 배경 지식 P, NP, 다항 시간 환원, 그리고 NP-완전 문제에 대해서는 koosaga님의 글 계산 복잡도 위계와 불리언 식의 “QBF 문제” 직전까지를 참조해 주시기 바랍니다. NP-완전 문제 1971년, Stephen Cook은 The complexity of theorem proving procedures 논문에서 “비결정적 튜링 기계로 다항 시간에 결정할...