11월 5주차

이번주는 수요일부터는 면접때문에 못하는 김에 수요일부터 2학년 시험볼때까지는 안하려고 한다.

즉, 월요일과 화요일만 할거다.

시간이 얼마 없기 때문에 문제는 두 문제만 준비했다.

 

A. 버블 소트 (1517)

아마도 널리 알려진 버블 소트의 정렬하는 데 걸리는 스왑 횟수 구하기

 

결론부터 말하자면 버블 정렬의 스왑 횟수는 인버젼의 개수와 같다.

인버젼이란 0 <= i < j < N인 두 임의의 정수 i, j에 대해 a[i] > a[j]인 것이라고 할 수 있다. 단순히 말하면 정렬을 하려할 때 뒤집힌(잘못된) 관계인 것이다.

버블 소트에서 스왑을 의미없게 사용하지는 않는다. 즉, 스왑을 한 번 할 때마다 인버젼의 개수가 1씩 감소하고, 인버젼의 개수가 0이 되었을 때가 정렬이 완료된 상태이므로 인버젼의 개수 = 스왑 횟수가 되는 것이다.

 

그럼 이제 인버젼의 개수만 세면 된다.

인버젼의 정의를 떠올리면 쉽게 세그먼트 트리를 사용하는 방법을 떠올릴 수 있다.

가장 마지막 인덱스부터 시작해서 현재까지의 세그에서 a[i]보다 작은 값의 개수를 답에 더하고, a[i]를 세그먼트 트리에 넣어주면 된다.

 

이 문제의 경우에는 값의 범위가 크기 때문에 바로 세그에 넣으면 메모리가 터진다.

값의 대소관계만 유의미하므로 좌표압축을 해서 해결할 수 있다.

 

세그먼트 트리로 해결할 수도 있지만, 펜윅트리를 연습해보자.

 

B. 북서풍 (5419)

문제를 읽고, 풀기 편한 형태로 바꿔 생각해보면 (당연하지만) 더 쉽고 빠르게 풀 수 있다.

문제가 요구하는 게 복잡해질수록 이런 작업이 필요하다.

이 문제도 문제를 살짝 바꿔서 생각해볼 필요가 있다.

 

문제에서 말하는 '항해할 수 있는 섬'이란 x좌표가 크거나 같고, y좌표가 크거나 같은 섬을 뜻한다.

 

만약에 2차원이 아니라 1차원(x축만 있다)이라면 어땠을까? 그냥 세그먼트 트리를 써서 자신보다 크거나 같은 값의 개수를 세면 풀린다.

 

2차원이면 어떻게 처리할 수 있을지 생각해보자.

x값도 크거나 같고, y값도 크거나 같아야 한다. 반대로 말하면 x값이 작거나 y값이 작으면 항해를 할 수 없는 것이다.

우선 한 축을 처리하기 위해 y축을 정렬을 통해 걸러볼 거다. x축으로 해도 상관없다.

그러면 y값이 큰 것부터 세그먼트 트리에 추가해 나가면, 세그먼트 트리에는 자신보다 y값이 크거나 같은 것만 넣어둘 수 있다. (y값이 큰 것만을 저장하는 게 아니라 같은 것도 저장해야 하기 때문에 관리를 잘 해줘야 된다.)

그러면 y값은 전혀 신경쓰지 않아도 되기 때문에 아까 설명한 1차원에서의 문제와 같아지게 된다.