목록2020/06/10 (2)
Joonas' Note

https://www.acmicpc.net/problem/11012 문제 2차원 평면에서 점들의 위치가 주어지고, [left, right]×[bottom, top] 으로 그려지는 사각형 내에 있는 점의 개수를 쿼리마다 출력하는 문제이다. 이 문제는 PST(Persistent Segment Tree)로 해결할 수 있다. PST의 이해를 위해서는 Segment Tree를 먼저 알아야한다. 이 글에서는 자세한 설명은 생략하고, 도움이 될 만한 글로 대체한다. 사실 같은 내용을 이 문제에 대해서만 다시 정리하는 것이라 봐도 무방하다. 혼동이 있을 수 있지만, 이 글에서는(필자는) 세로/수직 방향을 y축으로 가로/수평 방향을 x축으로 한다. 즉, (0, 0)은 왼쪽 아래를 의미한다. y축을 ..

오랜만의 코딩으로 풀어보기 시리즈이다. 오늘은 아주 간단하고 쉬운 문제이다. 문제 1부터 9까지의 숫자를 한번씩만 사용해서, 수식을 성립시키는 문제이다. 이런 유형의 문제는 "복면산 문제"라고 불리는 수학 퍼즐의 한 종류이다. 여담이지만, 개인적으로 좋아하는 문제이다. 이와 관련한 알고리즘 문제를 출제한 적도 있다. 완전 탐색류 알고리즘을 연습하기 좋은 문제라고 생각한다. 아래 링크에서 풀어볼 수 있다. BOJ 15811 - 복면산?! (https://www.acmicpc.net/problem/15811) 위 문제는 9개의 숫자와 9개의 알파벳이니 더 쉽다. 1부터 9까지 A부터 I까지 모두 대응시켜보며 만들어지는 세 값이 일치하는 지 확인하면 된다. 즉, 모든 순열을 확인하면 된다. 경우의 수는 \(9..