세그먼트 트리 - (2). Counting Inversions
이번 글은 세그먼트 트리를 활용 방법 중 하나인 Counting Inversions 이다. 길이가 N이고 1부터 N까지의 수를 1개씩 가지고 있는 순열이 있다고 하자. Counting Inversions는 각 수에서 오른쪽으로 자기 자신보다 작은 수의 갯수의 합(또는 왼쪽으로 자기 자신보다 큰 수의 갯수의 합)을 말한다. 예를 들어, A ={4, 1, 3, 2} 라는 수열이 있다고 하자. 4-1, 4-3, 4-2, 3-2 총 4개의 inversion이 존재한다. 이를 세그먼트 트리로 해결할 수 있는데, 저번 글에서 우리는 먼저 세그먼트 트리를 구성해놓고, 최소값을 찾으러 갔다. 하지만 이 문제에서는 먼저 세그먼트 트리를 구성하는 것이 아니라, 세그먼트 트리를 구성하면서 답을 찾아가는 것이다. 배열에 수열..
세그먼트 트리 - (1). 기본 구조
PS분야에서 정말 다양하게 쓰이고 있는 자료구조로 자유자재로 쓰고싶은 마음에 이번 기회에 정리하고자 한다. 세그먼트 트리는 흔히 일차원 배열의 특정 구간에 대한 쿼리를 빠르게 답하는 데 사용한다. 물론 다차원 배열의 특정 구간에 대한 세그먼트 트리도 구현이 가능하다. 가장 기본적인 예로 어떤 배열의 부분 구간의 최소치를 구하는 연산을 여러번 하는 것이다. 배열 A = {1, 2, 1, 4, 6, 1, 5, 8}가 있다면 구간[2, 4]의 최소값은 1이고 구간[6, 7]의 최소값은 5이다. 이 문제를 세그먼트 트리를 통해 O(qlogn)에 해결할 수 있다. 세그먼트 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것이다. 루트는 전체 구간을 표현하고, 리프는 1개만을 표현한다..
13140. Hello World!
https://www.acmicpc.net/problem/13140 13140번: Hello World! N이 주어질 때 hello + world = N을 만족하는 서로 다른 한 자리 자연수(0 포함) d, e, h, l, o, r, w를 구해서 아래 그림과 같은 형태로 출력하는 프로그램을 작성하여라. 단, h와 w는 0이 될 수 없다. www.acmicpc.net 문제 설명 복면산 문제와 같은 문제이다. hello + world = N을 만족하는 d, e, h, l, o, r, w 7글자에 서로다른 숫자를 대입해서 N이 나오는가를 묻는 문제이다. 재귀 완전탐색으로 7글자에 대한 수를 0부터 9까지 넣는 과정을 진행했는데, w와 h에는 0이 들어갈 수 없으므로 이 부분을 처리해주면 된다. 1 2 3 4 ..
