1517, 10090 - Inversion Counting (역순 갯수) / 최근 드는 생각

안녕하세요. 꼬동입니다.

 

진짜 큰 일 났습니다.

 

알고리즘이 너무 재밌습니다.

 

주말에 띵가 띵가 놀다가 갑자기 아이디어가 생각나서, 일을 했는데요.

 

일을 하다, 잠시 멈추고, 카페에서 커피 쪽쪽 마시며, 알고리즘 공부했는데, 너무 재밌어..!!

 

친구가 디아블로2 하자고 하는데, 솔직히 디아블로2보다 알고리즘이 더 재밌을거 같아서, 계속 미루는 중

 

최소한 알고리즘은 풀다가 자진 않는다.

오늘의 알고리즘은 바로바로바로 Inversion Counting (역순 정렬)

 

플레 5의 쉽지 않은 문제입니다.

 

한 번 볼까용.

---

https://loosie.tistory.com/328

[BOJ] 백준 1517번 버블소트 (Java)

사실 제가 이 분만큼 잘 설명할 수 없을거 같습니다.

 

블로그 한 10개 찾아봤는데, 9개의 블로그는 자기들만 알 수 있도록, Blah Blah 썼더라고용.

 

이 쪽입니다

 

그냥 이 분 블로그로 가시길 바랍니다. 다 이해 됩니다.

---

그래서 제 코드가 두 버전이 나왔습니다.

 

Merge Sort 버전 / 세그먼트 트리 버전

 

# 세그먼트 트리 버전

import sys

input = sys.stdin.readline

def update(s, e, t, node):
    if e < t or t < s:
        return TREE[node]

    if s == e == t:
        TREE[node] = 1
        return TREE[node]

    m = (s + e) // 2
    TREE[node] = update(s, m, t, node * 2) + update(m + 1, e, t, node * 2 + 1)

    return TREE[node]

def check(s, e, l, r, node):
    if e < l or r < s:
        return 0

    if l <= s and e <= r:
        return TREE[node]

    m = (s + e) // 2

    return check(s, m, l, r, node * 2) + check(m + 1, e, l, r, node * 2 + 1)

N = int(input())
ARR = sorted([[i + 1, int(v)] for i, v, in enumerate(input().split())], key=lambda x: x[1])
TREE = [0 for _ in range(N * 4)]

ans = 0
for _ in range(N):
    ans += check(1, N, ARR[_][0], N, 1)
    update(1, N, ARR[_][0], 1)

print(ans)

 

# 병합 정렬 버전

import sys

input = sys.stdin.readline

def merge_sort(s, e):
    global cnt

    if (s >= e):
        return
    
    m = (s + e) // 2

    merge_sort(s, m)
    merge_sort(m + 1, e)

    l = idx = s
    ll = r = m + 1

    while l <= m and r <= e:
        if ARR[l] <= ARR[r]:
            TMP[idx] = ARR[l]
            l += 1
        else:
            TMP[idx] = ARR[r]
            cnt += ll - l
            r += 1
        idx += 1
    
    while l <= m:
        TMP[idx] = ARR[l]
        l += 1
        idx += 1
    
    while r <= e:
        TMP[idx] = ARR[r]
        r += 1
        idx += 1
   
    for i in range(s, e + 1):
        ARR[i] = TMP[i]

N = int(input())
ARR = list(map(int, input().split()))
TMP = [0 for _ in range(N)]
cnt = 0

merge_sort(0, N - 1)
print(cnt)

근데 10090의 문제는 세그먼트 트리 버전으론 안 풀리더라고용 ?

 

사실 세그먼트 트리 공부하려고, 이 문제 푼건뎅

 

그래서 확 열 받아서 Merge Sort로 혼쭐냈습니다.

짜식이 까불어

근데, 사실 저도 양심이 없는게, 4792ms 걸리는 코드로 두 배의 데이터 문제를 뚫으려고 했던게,, ^_^;;

그래도 정답이라며 !

---

이상 1517, 10090 - Inversion Counting (역순 갯수) 였습니다. ^_^

---

아니 근데, 저는 쫌 놀랜게, S전자에서 배운 알고리즘들이 정말 쓸모 있다고 생각이 드네요.

 

세그먼트 트리 / 머지 소트 전부 안 짠지 약 1년 다 돼가는데, 몸이 기억하고 있네요.

 

S 전자식 주입식 교육이 통한건가 ..?

 

그리고, 최근 플레티넘 문제를 풀면서 느낀 점이 많은데,

 

플레티넘 문제들이 뭔가 다 아이디어 문제 혹은 새로운 알고리즘을 겪게 해주는 문제들이라서,

 

골드 문제 푸는것보다 훨씬 재밌더군요.

 

뭔가, 문제를 부수려고, 무기(알고리즘)를 얻어나가는 그런 느낌 ?

 

언젠가는 한 번 대회라도 참여해봐야하는거 아냐 ^_^ ??

 

우승하면 어떡해 !! >_<