가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)

페이스북 생활코딩 그룹에서 발견한 문제.

왠지 재미있어 보여서 (라고 쓰고 어떻게 풀지 감이 안와서 라고 읽...) pycharm을 켰다.

자존심상 일단 다 풀어놓고나서 댓글을 보니 http://seungkwan.tistory.com/m/8 이분은 두 가지 답이 있다고 친절히 써주셨다.

일단 감이 안와서 무식한 방법을 해본다.

1. 순서를 바꾸지 않은 모든 부분집합을 구한다. 모든 원소가 있을수도 없을수도 있으니 부분집합의 수는 2^N개. 구하는건 재귀호출을 쓴다.

def tuple_to_sublist (_tuple):     result = []     if _tuple == ():         result = [()]     else:         for _subtuple in tuple_to_sublist(_tuple[1:]):             result.append(_subtuple)             result.append((_tuple[0],) + _subtuple)     return result

2. 각각이 점점 증가하는 순서로 되었는지 확인한다. 비교할 원소의 수는 N x 2^N개.

_maxtuple = () for _tuple in _sublist:     if _tuple != ():         _before = _tuple[0]-1         _flag = 1         for _element in _tuple:             if _before >= _element:                 _flag = 0             else:                 _before = _element         if _flag == 1 and len(_maxtuple) < len(_tuple):             _maxtuple = _tuple[:]

자질구레한 검증코드가 마음에 안든다. 반복횟수도 너무 많다. 더 좋은 방법 없을까? 당연히 있겠지...

생각을 바꿔본다. 서브리스트를 만들 때, 맨 앞 것 보다 뒤의 것이 작은 숫자가 있으면 빼버리는걸로 해보자. 그러면

    result.append((_tuple[0],) + _subtuple)

요기를 바꾸면 되는데, 이왕 손대는거 그럴듯하게

     result.append((_tuple[0],) + tuple(filter(lambda x: x > _tuple[0], _subtuple)))

요렇게 바꾸면 된다. 

그러면 순서가 맞는 놈만 나올테니, 나중에도 다 비교하지 말고 가장 긴 놈만 꺼내면 된다.

이놈도 람다로 그럴듯하게 해본다.

    print (max(_sublist, key=lambda l: len(l)))

캬... 파이선 좋다.

완성코드

def tuple_to_sublist (_tuple):     result = [()]     if _tuple != ():         for _subtuple in tuple_to_sublist(_tuple[1:]):             result.append(_subtuple)             result.append(tuple(_tuple[0]) + tuple(filter(lambda x: x > _tuple[0], _sub_tuple)))     return result number_tuple = (0, 8, 12, 2, 6, 14, 9, 5, 13, 3, 11, 7, 15) print (max(tuple_to_sublist(number_tuple), key=lambda l: len(l)))

심플하다! ^^