List에서 두 원소와 두 원소 사이의 길이를 합을 cost로 할때 최대값 구하기

간단한 문제 풀일이 있었습니다.

List가 있을 때,

value1 + value2 + abs(index(value1) - index(value2))

의 최대값을 구하는 문제!

그냥 전부 다 해보는 취지로 다음과 같이 처음에 접근했습니다.

    def oriSolution(self, A):
        r = -1000000001
        l = len(A)
        if l == 1: # length is 1
            return 0

        for P in range(l):
            for Q in range(P+1, l):
                t = A[P] + A[Q] + (Q-P)
                r = max(r, t)
        return r

특별할 부분은 없는데, O(n^2) (등차수열의 합이니 아마)의 연산비용이 나오는게 영 꺼림직 해서 고민을 좀 해봤습니다.

현재의 최대값인 r(그러고보니 변수 이름이 적절하지 않네요)을 갱신하는 알고리즘인데,

안쪽의 Loop를 생략 할 수 있는 case가 생길 것 같았습니다.

우선 cost는 위에 기술된 것처럼 A[P] + A[Q] + Q-P (항상 양수) 로 기술됩니다.

현재의 최대값이 만약 A[P] + A[Q] + Q-P 에 의해 갱신이 되는 경우에만 안쪽 loop가 유효 하겠죠.

때문에 이걸 생략 할 수 있는 case를 만들었습니다.

현재의 최대값을 curMax 라고 하면,

curMax <= A[P] + A[Q] + (Q-P) 이면 의미가 있습니다.

이는,

curMax - A[P] - (Q-P) <= A[Q] 

으로 표현이 가능한데요, 만약 Q를 확인하지 않아도 이를 만족하지 않음이 자명하다면 안쪽 loop는 생략해도 괜찮습니다.

이를 위해 최대값을 미리 구해둡니다. (max(A)인데 O(n)의 비용으로 구해집니다. 1번만 하면 되므로 그리 큰 비용은 아닙니다)

curMax - A[P] -(Q-P) 가 만약 리스트 전체에서 가장 큰 값보다 크다고 하면, 

즉, curMax - A[P] - (Q-P) > maxValue 이면

curMax - A[P] -(Q-P) <= A[Q]

는 언제나 틀립니다.

따라서 curMax - A[P] - (Q-P) > maxValue 인 경우는 안쪽 Q loop는 돌지 않아도 됩니다.

여기서 Q-P 계산에 Q 가 사용되어서 문제인데,

Q-P의 최대값은 List의 길이를 넘지 않으므로 그냥 l로 치환합니다. 이렇게 해도 논리적 흐름에는 영향이 없으므로 괜찮습니다.

코드는 이렇습니다.

    def betterSolution(self, A):

        r = -1000000001

        l = len(A)

        if l == 1: # length is 1

            return 0

        maxV = max(A)

        for P in xrange(l):

            if r - A[P] - l > maxV:

                continue

            for Q in xrange(P+1, l):

                t = A[P] + A[Q] + (Q-P)

                r = max(r, t)

        return r

별거 아닌 변화 같지만, random한 case에서 속도 향상이 유의미 하네요.

        A = []

        for _ in range(5000):

            A.append(random.randint(1,1000))

        startTime = time.time()

        self.assertTrue(P().betterSolution(A))

        print("{0}: {1}".format("Better", time.time() - startTime))

        startTime = time.time()

        self.assertTrue(P().oriSolution(A))

        print("{0}: {1}".format("Ori", time.time() - startTime))

        self.assertEquals(P().oriSolution(A), P().betterSolution(A))

와 같은 test code에서

Better: 0.205455064774

Ori: 1.86105298996

의 결과가 나오네요.

혹시 잘못생각한 부분이 있다면 comment 주세요 :)

jws rbtree 분석(작성중..)

Python 의 RBTree에 대해 파악하다 http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx 를 알게되었습니다.

유용한 내용이 많아 찬찬히 업데이트 합니다.

1. Left, Right 대신 0, 1

left, right 표현 대신 0, 1을 쓰는 저자의 코드도 흥미롭네요.

/* Classic binary search tree insertion */
struct cbt_node *cbt_insert(struct cbt_node *root, int data)
{
    if (root == NULL)
    {
        root = make_node(data);
    }
    else if (data < root->data)
    {
        root->left = cbt_insert(root->left, data);
    }
    else
    {
        root->right = cbt_insert(root->right, data);
    }

    return root;
}

/* Julienne Walker's binary search tree insertion */
struct jsw_node *jsw_insert(struct jsw_node *root, int data)
{
    if (root == NULL)
    {
        root = make_node(data);
    }
    else
    {
        int dir = root->data < data;

        root->link[dir] = jsw_insert(root->link[dir], data);
    }

    return root;
}

가독성을 조금 희생시킨 것 같지만 라인수를 많이 줄여줍니다. 내용을 이해한다면 사실 가독성이 많이 떨어진다고 하기도 애매하네요 ㅎㅎ

python에서도 무리 없이 써먹을 수 있을 것 같습니다.

가령

>>> (1>0) == (True)
True
>>> (1<0) == (False)
True
>>> (1>0) == (1)
True
>>> (1>0) == (0)
False
>>> (1<0) == (0)
True
>>> (1<0) == (1)
False

좋네요

Python 의 RBTree

손고리즘 스터디에서 재경님이 알려주시길 C++에서는 Map이 RBTree로 되어 있으나 python 은 RBTree 구현체가 없다고 합니다.

C/C++이랑 Python이 결속력(?)이 좋아서 특별히 안만든게 아닐까 하는 생각도 있지만, 뭐 일단 좀 의문이네요-

그래서인지 Tree 구현체가 많이 있는데, pip를 통해 쉽게 설치 할 수 있는 bintrees가 유용한 것 같습니다.

어떻게 RBTree를 구현했는지 코드를 좀 파악해야겠네요 :)

https://github.com/doctorpangloss/bintrees

Python django

예전에 개인적인 호기심으로 잠깐 만저본 django.

이번에도 호기심 차원에서 조금 더 만져보고 있다. 전에 기억이 하나도 안나서 아예 처음부터 하는 기분인데, 참 잘 만들어진 것 같다.

생산성이 수십배 오르는게 당연하겠구나.

Python lambda function 과 unittest

수학식이 좀 많이 나오는 것 같은 문제를 풀다보니 아래와 같은 함수를 만들 일이 생겼습니다.

    def getFunction(self, c1, c2):
        x1 = c1[0]; y1 = c1[1]
        x2 = c2[0]; y2 = c2[1]
        if x1 == x2:
            return (lambda x,y: x1)
        if y1 == y2:
            return (lambda x,y: y1)
        return (lambda x,y: (y1-y2)/(x1-x2)*x + y1 - (y1-y2) / (x1-x2)*x1)

두 점을 지나는 직선을 구하는 함수로 함수 자체를 리턴시키기 위해 lambda를 사용했습니다.

보통 TDD를 하기에 TestCase를 만들긴 했는데, 생각보다 고민이 되더군요-

"기대값을 뭘해야 하지?"

종이에 쓰는경우면 쉽습니다.

가령 (0,0), (1,1)을 지나는 함수 f(x)는 이렇게 되겠죠.

f(x) = x

unittest에 넣는다고 치면(당연히 안되지만)

assertEquals(f(x) = x, getFunction((0,0), (1,1)))

과 같은 포멧이 될텐데 기대값에 f(x) = x 와 같은 형태는 둘 수 없습니다.

String 으로 뽑아도 당연히 저렇게 나타나지 않구요-

일단 대안으로는 기대함수(편의상)에 값을 넣었을 때 올바르게 나오는지 검사하도록 했습니다.

다음과 같네요.

        # y = 2*x function

        F = Treasure().getFunction((0,0), (1,2))

        self.assertEquals(0, F(0,2))

        self.assertEquals(2, F(1,2))

        self.assertEquals(10, F(5,10))

대략 적으로 검출은 되는데, 영 찝찝합니다.

뭔가 lambda function 을 unittest에서 적절하게 검출하는 방법이 있으면 좋을 것 같습니다.

검색을 좀 해보니 eval을 만들어 string으로 비교하는 방법도 있는 것 같은데, 이정도가 최선일까요? 고민해봐야겠네요 ㅎ

정리

정리를 그렇게 잘하지는 못하는 것 같습니다.

블로그도 그렇고 메모도 그렇고.

그래도 일단 쓰는게 안쓰는 것보단 좋겠져.

STRJOIN 문제에서 python list의 sort 개선!

비교적 쉬운 카테고리인 'Greedy algorithm' 에 속하는 STRJOIN 문제를 풀었습니다.

https://algospot.com/judge/problem/read/STRJOIN

간만에 술술(...) 풀렸고, 혹시해서 가장 짧은 정답을 확인하니 3줄에 짜신 분도 있더군요-_-..


여튼, 제가 푼 풀이에서 중요한 부분은 sorting 이었습니다.

주어진 list를 갱신하고, 이때마다 '최소값'을 알기 위해서 list를 sort하였는데요- 문제 요구사항에 주어진 list의 길이가 그리 길지 않아 이 부분을 더 생각하진 않고 그냥 계속 sort 시켰습니다.

이런식으로 할 수 있겠죠.

a = [..data..]

sorted(a) # 내장함수를 사용
혹은
a.sort()

TDD로 접근하다보니 사실 별로 신경 쓰지도 않는 시간에도 괜히 한번 눈길이 가는데요,
재미있는 점은 sorted() 와 같은 함수는 성능이 그다지 좋지 않더군요. (아무래도 일반적으로 쓸 수 있어서 그런 것 같네요)

당연하게도 리스트에 특화된 a.sort() 의 경우가 훨씬 빠른 성능을 보였습니다.

이쯤에서 왠지 sort() 를 이기고 싶은 생각이 들었습니다.

뭐 언제나 모든 정렬에서 sort() 를 이기려는게 아니고 이 문제에 특화된 경우에라도 이기고 싶었죠.

(스포주의)
문제의 힌트가 될수도(...뭐 도움 안될수도) 있지만 풀이를 설명하자면 이렇습니다.

1. 정렬된 리스트를 받습니다.
2. 종료 조건으로 리스트의 길이를 검사합니다.
3. 가장 앞의 두 값이 가장 작은 두 값이므로, 이 두 값을 합해서 cost를 만듭니다.
4. 만들어진 cost를 누적합니다.
5. 새로운 값을 리스트에 다시 넣고 1을 반복합니다.

코드로 쓰면 대략 이렇습니다. (본 코드에서는 새로운 값을 가장 뒤에 붙였습니다. append)

    def calCost(self, sortedList):
        totalCost = 0
        while len(sortedList) >= 2:
            sortedList.sort()
            firstMin = sortedList[0]
            secondMin = sortedList[1]
            cost = firstMin + secondMin
            totalCost = totalCost + cost
            sortedList = sortedList[2:]
            sortedList.append(cost)
        return totalCost

이미 리스트 연산에서 많은 낭비가 생기지만(...) 무시하고, sort()의 개선이 성능에 가장 큰 영향을 미친다고 생각했습니다.

이를 다음의 TestCode로 돌려보면,

    def testSolveWithDefaultSort(self):
        self.assertEquals(3222, StrJoin().calCost(
            [1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,
             1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,
             1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,
             1,1,1,1,1,1,1,1,2]))

testSolveWithDefaultSort (__main__.StrJoinTest) ...

__main__.StrJoinTest.testSolveWithDefaultSort: 2.6798248291

시간은 너무 작아서 제가 임의로 *10000 을 한 값을 출력했습니다. (그러니까 2초씩이나 걸리지 않습니다...)

def tearDown(self):

        print("{0}: {1}".format(self.id(),

                                (time.time() - self.startTime)*10000)) # * 10000

우선 뼈대를 위한 코드는 이렇습니다. 위와 동일한데 단지 sort를 sortMethod를 통해 연산합니다. sortMethod는 제가 만들 함수입니다. (정확하게는 sortMethod는 아니지만 비교를 위해 이런 이름을 붙였습니다.)

    def calCostWithSortMethod(self, sortedList, sortMethod): 

        totalCost = 0

        sortedList.sort()

        while len(sortedList) >= 2:

            sortedList = sortMethod(sortedList) # Custom

            firstMin = sortedList[0]

            secondMin = sortedList[1]

            cost = firstMin + secondMin

            totalCost = totalCost + cost

            sortedList = sortedList[2:]

            sortedList.append(cost)

        return totalCost

이를 다음과 같이 TestCode로 검증합니다.

self.assertEquals(26, StrJoin().calCostWithSortMethod([3,1,3,4,1], self.mySort))

TestCode 에서 적절한 sort를 작성합니다.

그럼 원 문제인 sort() 를 한번 다른 방법으로 개선 시켜보겠습니다. (TestCode의 mySort 작성)

본 문제의 특징은 이렇습니다.

1. 이미 정렬된 값이 들어옴

2. 새로운 값이 어디에 들어갈지만 알면됨

즉, 매번 모든 리스트 데이터가 '정렬되지 않음'을 가정 할 필요가 없습니다.

1개의 데이터만 올바른 위치에 insert하면 끝이기에 아 이러면 sort() 를 이길 것 같아서 시도했습니다.

1번째 시도는 그냥 앞에서 부터 비교하기 입니다.

왜냐하면 순서대로 정렬된 값에서 가장 작은 두 값을 합한 결과가 앞쪽에 위치할 확률이 더 높다고 생각했기 때문이죠.

1번 시도의 코드는 이렇습니다. (pop() 으로 위에서 뒤에 붙이 값을 꺼냅니다)

    def mySort(self, l):

        newValue = l.pop()

        for idx in xrange(len(l)):

            if l[idx] > newValue:

                l.insert(idx, newValue)

                return l

        l.append(newValue)

        return l

결과는?!

testSolveWithCustomMethod (__main__.StrJoinTest) ...

__main__.StrJoinTest.testSolveWithCustomMethod: 5.04970550537

졌습니다. ㅠㅠ 

아무래도 앞에서 부터 비교하는 것이 그리 좋은 접근이 아닌 것 같네요.

2번째는 '일반적인' 접근인 binary search 를 사용했습니다.

즉, 반으로 나눠서 위치를 잡아가는 방법이죠.

다음과 같습니다.

    def myImproveSort(self, l):

        newValue = l.pop()

        start = 0

        end = len(l) - 1

        while True:

            if start == end:

                if l[start] > newValue:

                    l.insert(start, newValue)

                    break

                else:

                    l.insert(start+1, newValue)

                    break

            if start > end:

                l.insert(start, newValue)

            mid = (start+end)/2

            if l[mid] < newValue:

                start = mid + 1

            elif l[mid] > newValue:

                end = mid + 1

            else:

                l.insert(mid, newValue)

                break

        return l

결과는!!

testSolveWithCustomImproveMethod (__main__.StrJoinTest) ...

__main__.StrJoinTest.testSolveWithCustomImproveMethod: 3.24964523315

원래 결과는

testSolveWithDefaultSort (__main__.StrJoinTest) ...

__main__.StrJoinTest.testSolveWithDefaultSort: 2.6798248291

방법1 보단 훨씬 나아졌지만 역시 졌네요..

List가 더욱 커지면 효과가 나지 않을까 싶지만, 일단 거기까진 안했습니다.

역시 List에 내장된 sort() 가 짱입니다... 다만, 제가 구현한 Code에서 개선될 수 있는 부분이 좀 있을 것 같으니 얼추 비등해지지 않을까요? (희망사항이겠죠)

결론: 특수한 경우지만 이기지 못하였다. 하지만 더 크기가 커지거나 몇몇 부분을 개선하면 이기지 않을까?.. (Code에 cost가 큰 연산이 좀 있는 것 같기도...)