펜윅트리 문제1 삽입정렬 시간 재기

이한울·2019년 7월 16일
0

트리

목록 보기
10/10

문제 풀이

이 문제에는 세 가지 풀이가 있다.

1. 펜윅 트리 활용

펜윅 트리는 구간합을 간단하고 빠르게 구할 수 있는 자료 구조이다. 구간합을 활용해서 이 문제를 푸는 방법은 펜윅 트리의 크기를 문제에서 주어진 정수 범위로 하는 것이다. 모든 정수에 대해여 펜윅 트리를 만들고, 배열의 첫 원소부터 하나씩 갱신하면서 그 원소보다 큰 원소의 개수를 구하면 그 원소가 몇번 움직여야 되는 지를 간단하게 구할 수 있다.

2. 트립 활용

트립을 활용해도 매우 간단히 해결된다. 트립은 특정 원소보다 작은 원소 개수가 몇 개 있는지를 효율적으로 구할 수 있다. 따라서 전체 들어온 배열의 크기에서 주어진 원소보다 작은 원소의 개수를 빼면 그 원소보다 큰 원소가 몇 개 있는가를 알 수 있고 이를 활용해 펜윅트리와 같이 문제를 해결 할 수 있다.

3. 병합 정렬 활용

병합 정렬을 활용할 경우 나눠진 구간을 병합하는 과정에서 횟수를 셀 수 있다. 위 문제에서 움직이는 회수는 더 큰 수가 더 작은 수보다 앞에 있는 경우가 몇 번인가를 세면 되는데, 이는 병합 정렬 과정에서 효율적으로 계산할 수 있다. 분할된 구간을 병합하는 과정에서 각 구간의 첫 원소부터 비교하면서 만약 오른쪽 구간의 원소가 왼쪽 구간의 원소보다 작은 경우라면 그 원소는 왼쪽 구간의 모든 원소와 자리를 바꿔야 하므로 그 만큼 횟수가 증가한다. 같은 구간에 속한 원소들은 아래에서 병합되는 과정에서 움직이는 횟수가 계산된다.

느낀점

결국 모든 풀이는 nlogn의 시간 복잡도를 갖게 되므로 문제의 조건을 통과한다. 배열과 관련되어 시간 제한을 통과하기 위해 효율적인 접근을 필요로 하는 경우 분할하고 병합하는 과정에서 대부분 효율을 얻는다. 그 방법을 깨닫기 위해서는 자료 구조와 구현에 대한 익숙함과 이해가 더 필요할것 같다.

profile
Backend Engineer 이한울입니다

0개의 댓글