20/12/28 TL.

오늘 할 일

모각코 계획

백준 알고리즘 시간 초과 문제 검토

백준 알고리즘 문제 풀이

인프라 엔지니어 교과서 - 2장

 

내일 할 일

백준 알고리즘 검토

백준 알고리즘 문제 풀이

인프라 엔지니어 교과서 읽기

모각코 - 강의 수강, 복습

---

클라우드 컴퓨팅 공부

www.coursera.org/learn/introduction-to-cloud#syllabus

클라우드 컴퓨팅 입문

www.coursera.org/learn/ibm-containers-docker-kubernetes-openshift

Introduction to Containers w/ Docker, Kubernetes & OpenShift

www.coursera.org/learn/uva-darden-continous-delivery-devops

Continuous Delivery & DevOps

---

1655 가운데를 말해요

나의 풀이(python) - time over

from bisect import bisect_left


def run():
    size = int(input())
    arr = list()

    for _ in range(size):
        num = int(input())
        arr_length = len(arr)
        pointer = bisect_left(arr, num)
        arr.insert(pointer, num)
        arr_length += 1

        if arr_length % 2 == 1:
            index = arr_length // 2 + 1
        else:
            if arr_length / 2 < (arr_length / 2) + 1:
                index = arr_length // 2
            else:
                index = arr_length // 2 + 1
        index = index - 1
        print(arr[index])


if __name__ == '__main__':
    run()

 bisect를 이용해서 이진 탐색을 통해 반복 수를 줄여 연산 속도를 줄이려고 했다. 입력할 때 마다 적절한 위치에다가 insert를 하면 sort된 효과를 볼 수 있을 것이라 생각했다. 그러나 이 방법 또한 시간 초과가 발생했다.

-> 아마 insert를 반복하면서 중간에 삽입할 경우 인덱스를 밀거나 당기는 것을 반복하는 과정에서 연산이 많아지는 것으로  예상된다.

 

다른 사람의 풀이

 많은 사람들이 haepq를 이용해서 풀었다. (가끔 이진탐색으로 푼 분도 있었다.) 이 분의 코드가 가장 보기 좋은 것 같아 분석해보았다. 이 분도 heapq를 이용해서 푸셨다.

inspirit941.tistory.com/200

[Python] 백준 1655. 가운데를 말해요

import sys
import heapq#heapq는 최소힙만 지원한다 최대힙을 구현하기위해선 -를 곱해서 넣어 주고 꺼낼때 다시 -를 곱해준다
 
 
def middleheap(minheap,maxheap,x):#넣기만함
    if len(maxheap)==len(minheap):#같다면 max힙에 넣어준다
        heapq.heappush(maxheap,-x)
    else:#max힙이 크다면 minheap넣어 균형을 맞춰준다.
        heapq.heappush(minheap,x)
    if minheap and -maxheap[0]>minheap[0]:#minheap이 비어잇지않고 최대 힙의 루트는 항상 최소 힙의 루트보다 작게 유지해준다.
        #최대힙의 루트노드가 더크다면 스왑해주고 다시 힙구조로 만들어주어야한다.
        a=heapq.heappop(minheap)
        b=-heapq.heappop(maxheap)
        heapq.heappush(maxheap,-a)
        heapq.heappush(minheap,b)
 
 
n=int(sys.stdin.readline())
minheap,maxheap=[],[]
while n>0:
    n-=1
    middleheap(minheap,maxheap,int(sys.stdin.readline()))
    print(-maxheap[0])

 우선, 이 분은 input()이 아니라, int(sys.stdin.readline())이란 걸 사용했다. 무슨 차이인지 검색해 보았다.

velog.io/@gouz7514/%ED%8C%8C%EC%9D%B4%EC%8D%AC-input-vs-sys.stdin.readline

[파이썬] input() vs sys.stdin.readline()

여기에 잘 정리돼 있었는데, 

num = sys.stdin.readline()
print(type(sys))

를 수행해보니, class module이라고 나온다. 즉, char로 변환돼서 나오는 게 아니다. 따라서, int(num)으로 해주면,

모듈 -> char -> int가 아니라, 모듈 -> int이므로 연산 속도가 더 빨라질 것으로 예상된다. (뇌피셜)

 

우선, minheap과 maxhaep에 대해 알아보자.

minheap은, 부모노드에 있는 값이 자식노드에 있는 값보다 항상 작거나 같다.

maxhaep은, 부모노드에 있는 값이 자식노드에 있는 값보다 항상 크거나 같다.

이 점을 이용하여 작성한다.

 

heapq는 minheap을 기준으로 작성돼있는 이진트리이다. 따라서 maxheap을 사용하기 위해 값을 넣을 때 -을 넣어서 사용한 듯 싶다.

 

python.flowdas.com/library/heapq.html

heapq --- 힙 큐 알고리즘 — 파이썬 설명서 주석판

를 참고해보자면,

 

heap[0]이 루트이고,

이러한 함수들을 제공한다.

 

다시 코드 분석으로 돌아가자. 이 분은 maxheap과 minheap을 2개 구현해서, 중간값을 구하려는 시도를 한 것이다. maxheap은 루트가 항상 제일 크다는 성질에, 루트가 가장 작은 minheap의 루트보다 항상 작게 유지함으로써, 중간값을 항상 maxheap의 루트로 만들어준 것이다. meaheap의 루트는 중간값, minheap의 루트는 중간값 + 1형태로 만든 것이다. maxheap부터 push하고, 항상 maxheap의 루트를 검사하므로, 짝수 홀수를 나눌 필요도 없어진다.

 

참고해서 내가 한 풀이

 

import sys
import heapq


def run():
    minheap, maxheap = list(), list()
    num = int(sys.stdin.readline())
    for _ in range(num):
        cur = int(sys.stdin.readline())
        if len(maxheap) == len(minheap):
            heapq.heappush(maxheap, -cur)
        else:
            heapq.heappush(minheap, cur)
        if minheap and -maxheap[0] > minheap[0]:
            tmp1 = -heapq.heappop(maxheap)
            tmp2 = heapq.heappop(minheap)
            heapq.heappush(maxheap, -tmp2)
            heapq.heappush(minheap, tmp1)
        print(-maxheap[0])


if __name__ == '__main__':
    run()

 안 보고 풀었는데 거의 완전 비슷하다. 다른 사람의 코드를 참고하면 이 점이 안 좋은 것 같다. 

 

다음은 준희형이 추천해 준 알고리즘 공부 참고 자료

blog.naver.com/kks227/220777333252

이분 탐색(Binary Search) (수정 2019-02-15)