[파이썬 알고리즘 심화 스터디] 2주차 정리

2주차

AC 프로필

티어는 크게 의미없는 것 같지만, 점진적으로 푼 문제가 쌓여가는걸 보면 뿌듯해서 남긴다.

Git 활용

다행히 2주차 문제들을 pull해오는 것은 수월했지만, 저번주의 삽질 시도는 장렬히 실패했다! 더 찾아보니 원하는 파일만 커밋하는 기능인 cherrypicker라는게 있긴 한데, 이건 내용을 보니 실패하면 파일이 꼬일 수도 있을것 같아서 잘 알아보고 적용시킬지 말지 더 고민해야겠다.

알고리즘

• 1181 단어정렬

  람다식과 set을 사용해서 문제를 풀었다. 이왕 람다식을 사용해서 더 줄일 수 있는 문제였음에도 내 눈엔 복잡하게 느껴져서 굳이 두 번 정렬했던 것이 조금 아쉬웠다. 검색을 통해 람다식을 한 번만 쓴 예시를 봤는데, 막상 코드를 보고 나니 다음엔 활용할 수 있을 것 같아 자신감이 생기기도 했다. 여러 문제를 풀면서 감각을 늘려야 될 것 같다.

• 2751 수 정렬하기

  단순히 파이썬의 기본 정렬로 정렬했으나 운 좋게도 sys 라이브러리의 sys.stdin.readline() 을 사용해서 통과할 수 있었다.

  다른 정렬 방식들을 사용한 풀이들이 궁금해서 찾아봤는데, 병합 정렬의 경우 주어진 예제로는 time라이브러리를 이용하여 시간을 재본 결과 되려 더 느렸기 때문에(게다가 소요시간도 3초대로 sys 라이브러리를 사용하지 않았을 때와 비등비등했다), 각 정렬들의 결과물을 대충 예상하기 어렵다는 점이 막막한 것 같다.

  코딩테스트를 할 땐 직접 여러 정렬을 구현하면서고 많은 양의 input을 직접 넣어서 시간을 잴 환경이 아니므로, 역시 평소 문제를 많이 풀어보면서 시간복잡도를 계산하는 감을 길러야 될 것이다.

• 17478 재귀함수가 뭔가요

  문제의 첫인상은 별로 어려워보이지 않았는데도 막상 해보니 미묘하게 틀리는 부분들이 많아서 출력도 많이 해보고 시행착오도 많이 겪었다. 다들 이렇게 푸는건지 체계적으로 방식을 정해서 한 번에 통과하는건지 모르겠지만, 앞으로 풀 문제들은 점점 더 복잡해질 것이므로 후자가 될 수 있도록 문제를 보면 수도코드를 제대로 짜보는 연습을 해야겠다.

시험

• 1026 보물

  하나는 오름차순, 하나는 내림차순으로 정렬하여 같은 자리의 수들을 곱해 더하면 최솟값이 되어 어렵지 않게 풀 수 있었다.

• 15501 부당한 퍼즐

  시간초과난 퍼즐이다. 문제에 쓰여진 그대로 정직하게 적으면 시간초과를 면할 수 없나보다. 재홍 님의 풀이에서 인덱스 슬라이싱을 활용한 예시를 볼 수 있었고, 이를 이용하면 배열의 길이가 줄어들어 시간단축이 된다는 아이디어를 얻을 수 있었다.

    import sys
    from collections import deque
      
    def is_good_puzzle(num):
        if num == 0:
            # print("0before_nums:", before_nums, "0after_nums:", after_nums)
            return "bad puzzle"
        for i in range(num):
            before_nums.reverse()
            print("reverse list:", before_nums)
            if before_nums == after_nums:
                # print("1before_nums:", before_nums, "1after_nums:", after_nums)
                return "good puzzle"
            before_nums.append(before_nums[0])
            before_nums.popleft()
            print("pop list:", before_nums)
            if after_nums == before_nums:
                # print("2before_nums:", before_nums, "2after_nums:", after_nums)
                return "good puzzle"
        print("3before_nums:", before_nums, "3after_nums:", after_nums)    
        return "bad puzzle"
      
    n = int(sys.stdin.readline())
    before_nums = deque(map(int, sys.stdin.readline().split(" ")))
    after_nums = deque(map(int, sys.stdin.readline().split(" ")))
      
    print(is_good_puzzle(n))
  

• 16505 별

  아직까지는 평소 문제를 풀 때 직감에 의존하는 경향이 강한데, 체계적으로 알고리즘을 짜서 풀어야된다는 생각이 들었다. 특히 17478 재귀함수가 뭔가요 문제를 풀 때의 데자뷰가 느껴져서, 더 유심히 생각하는 자세와 비슷한 유형들을 풀어보는 경험의 필요성을 느꼈다.