# inversion

hhyang986

▲ 미국의 우주 스타트업인 인버전스페이스가 ‘우주 딜리버리’를 위해 개발한 캡슐. photo 트위터 국제우주정거장에 머물고 있는 우주인이 지구에 사는 아들의 생일날에 선물을 전해줄 방법은 없을까. 미국의 우주 스타트업인 인버전스페이스(Inversion Space)가 ‘우주 배송 시대’를 열 준비를 하고 있다. 원심력을 이용해 우주에서 지구의 특정한 위치로 정확히 물건을 떨어트려 전달하는 서비스다. 황당하게 들릴지 모르지만 전문가들은 ‘우주 택배’ 서비스가 앞으로 가장 유망한 사업이 될 것으로 전망한다. 지난 3월 초의 일이다. 인버전스페이스가 미국 캘리포니아주의 하늘에서 배송물을 목적지에 떨어뜨리는 실험에 성공했다. 약 914m 상공을 날아다니던 항공기에서 지름 50㎝ 크기의 캡슐이 비행체 밖

whipbaek

Problem https://www.acmicpc.net/problem/1517 Bubble Sort를 실행할시 수행되는 Swap의 횟수를 출력하는 프로그램을 작성하라 >Solution 일반적으로 Bubble Sort를 실행해서 횟수를 세는 방법도 있겠지만 기본적으로 시간복잡도가 O(N^2) 이기에 문제의 조건을 맞추지 못하고 시간초과가 나버린다. 그렇기에 이 문제는 Inversion counting 방법을 사용해야하는데, 프로그래밍에서 Inversion은 A[i] > A[j] (i<j) 일때를 의미한다. 예를들어 3 1 2 값이 주어졌을때 Inversion 의 개수는 {3 1, 3 2} 로 총 2개가 존재한다. 쉽게 생각해서 앞서있는 숫자가 현재 위치의 숫자보다 클시 Inversion하다고 말한다. Bubble Sort의 Swap횟수 또한 자신의 뒤에 작은숫자의 개수와 같기때문에 위와 같은 방법을 사용할 수 있다. (3 1 2 를 정렬시 `3 1

victor

problem code 1st try: check if 0 a[j] Time: O(N^2) Space: O(1) 2nd try: O(N) Time Time: O(N) Space: O(1)