log 2021-03-28

---

• 할 일
• 알고리즘 문제풀이
  • boj 5397 - 키로거
  • boj 1937 - 욕심쟁이 판다
• 기타

할 일

• 알고리즘 문제풀이

알고리즘 문제풀이

boj 5397 - 키로거

같은 코드인데 python3로는 시간초과나고 pypy3로는 통과한다.

py solution

이중 연결 리스트를 만드는 데 애먹었다. 커서 처리때문에 굉장히 헷갈렸다. 진작 출력 함수 만들고 디버깅을 하는게 풀이 시간을 줄였을 듯하다. python3로 제출하면 시간초과가 나는데, print 자체가 느려서라는 말도 있는 듯하다.

class dictlist:
    def __init__(self):
        self.data = {}
        self.cur = {'val': None, 'prev': None, 'next': None}
        self.head = {'val': 'head', 'prev': None, 'next': self.cur}
        self.cur['prev'] = self.head
        self.size = 0

        # self.pos = -1

    def getList(self):
        pointer = self.head['next']
        ret = []
        while(pointer):
            if(pointer['val']):
                ret.append(pointer['val'])
            pointer = pointer['next']
        return ret

    def printList(self):
        pointer = self.head
        ret = []
        while(pointer):
            if(pointer == self.cur):
                ret.append('*')
            if(pointer['val']):
                ret.append(pointer['val'])
            pointer = pointer['next']
        print(' '.join(ret))

    def findNext(self):
        nextnode = self.cur['next']
        # assert(pos < self.size)
        return nextnode if nextnode != None else self.cur

    def findPrev(self):
        prevnode = self.cur['prev']
        # assert(pos < self.size)
        return prevnode if prevnode != None else self.cur

    def moveNext(self):
        nextnode = self.cur['next']
        self.cur = nextnode if nextnode != None else self.cur
        return self.cur

    def movePrev(self):
        # it('moving prev')
        prevnode = self.cur['prev']
        if(prevnode):
            if(prevnode['val'] == 'head'):
                return self.cur
            self.cur = prevnode if prevnode != None else self.cur
        return self.cur

    def add(self, val):
        # prev -> cur -> next
        # prev -> newnode -> cur
        prevnode = self.cur['prev']
        newnode = {'val': val, 'prev': prevnode, 'next': self.cur}
        if(prevnode):
            prevnode['next'] = newnode
        newnode['prev'] = prevnode
        newnode['next'] = self.cur
        self.cur['prev'] = newnode

        return newnode

    def remove(self):
        # pprev -> prev -> cur -> next
        # pprev -> cur -> next
        # if(not self.cur['val']):
        # if(self.cur['val'] == None):

        prevnode = self.cur['prev']
        pprevnode = prevnode['prev'] if prevnode else None

        if((not prevnode) or (not pprevnode)):
            return self.cur

        # it(f'deleting {prevnode["val"]}')

        pprevnode['next'] = self.cur
        self.cur['prev'] = pprevnode

        # self.cur = self.movePrev()
        # if(self.cur):
        #     it(f'deleting {self.cur["val"]}')
        #     if(self.cur['val'] == 'head'):
        #         return self.cur
        # prevnode = self.cur['prev']
        # nextnode = self.cur['next']
        # if(prevnode):
        #     prevnode['next'] = self.cur['next']
        #     if(nextnode):
        #         nextnode['prev'] = self.cur['prev']
        #     self.cur = prevnode
        # else:
        #     self.cur = nextnode
        return self.cur


def solve():
    n = ria()[0]

    for tt in range(n):
        ins = list(rsa()[0])
        # it(ins)
        li = dictlist()
        curlen = 0
        pos = 0

        for i, cur in enumerate(ins):
            if(cur == '<'):
                li.movePrev()
                pass
            elif(cur == '>'):
                li.moveNext()
                pass
            elif(cur == '-'):
                li.remove()
                pass
            else:
                li.add(cur)
                pass
        # li.printList()
        lis = li.getList()
        print(''.join(lis))
    pass

boj 1937 - 욕심쟁이 판다

골3인데 아이디어가 떠올라서 생각보다 쉽게 풀었다.

hint

• 바텀업

py solution

어디서 출발할 지 모르는데 누적해나가기엔 반복 수가 너무 많고 과거를 기억하는것도 무리여서 오히려 방법을 찾을 수 있었다. 입력을 정렬해서 가장 낮은 수부터 (주변 셀 최대+1)값을 저장하게 하는 것이다.

def solve():

    # 판다가 처음에 어디서 출발할 지 모르므로 상당히어렵다.
    # 맵크기가 최대 500x500=250000이므로 무턱대고
    # 복사할 수도 없다.
    # 원본 맵과, 각 위치에서 시작했을 때 최대 생존일수를 담은 맵을 유지한다면?
    # 그러면 과거 원본 맵중에 어디어디를 먹었는지 모르게 된다.
    # 그걸 셀마다 배열로 저장한다면 메모리를 너무 많이 먹게 된다.
    # 왜 하필 최대 크기가 1백만일까?
    # ...
    # 주변에서 생존 일수 정보를 합치려면 데이터를 어떻게 저장해야 할까??

    # 일단 처음에는 모든 위치에서 1일 것.
    # 그 다음은, 이전과 비교하여 전보다 원본이 높은 쪽 기준으로 더해나간다.
    # 문제는, 역시 이 누적이 원본 맵중에 어디어디를 먹었던 것인지 알 수 없는것,
    # 근데, 그게 꼭 필요한가? 최종 상태만 안다면, 최종 누적과 마지막으로 먹었던 양만 각 셀이 기록해 둔다면 충분할지도??
    # 1차원으로 생각해보자. 임의 위치에서 시작해서 돌아다닐 때,
    # 점점 커지는 쪽으로 움직여야 할 때 최대 길이는 얼마인가를 구하는
    # 문제이다.
    #

    n = ria()[0]

    maps = create2DArray(n, n, 0)
    vals = create2DArray(n, n, 0)
    cells = []
    for r in range(n):
        ins = ria()
        for c in range(n):
            this = ins[c]
            cells.append([this, r, c])
            maps[r][c] = this

    # it(maps)
    cells.sort()
    # it(cells)

    # 근데 이거.. 대나무의 양이 의미가 있나? 어차피 상하좌우로
    # 늘어나는 방향으로만 움직이는 그래프 또는 트리 형태가 될 텐데
    # 그러면 위상 정렬을 해서 가장 긴 경로를 찾으면 되지 않나?
    # 근데 그 정렬상태에서 긴 경로를 어떻게 찾을지도 문제다.
    # 플로이드 워셜처럼 전체 노드에 대해 주변에서 누적을 반복
    # 하게 한다면, 맵 크기 25000*최대길이 25000이므로 무조건
    # 시간초과다.
    # 그렇다면, 가장 작은 셀부터 위치를 기록해놓고 주변에서 더하면서
    # 초기화한다면? 25000개를 정렬해야 하는데, 그건 가능할 듯하고,

    def boundCheck(cr, cc, mr, mc):
        if(cc < 0 or cr < 0 or cc >= mc or cr >= mr):
            return False
        return True

    def getMaxv(rr, cc):
        maxv = 1
        for i in range(4):
            nr, nc = rr+dy[i], cc+dx[i]
            if(not boundCheck(nr, nc, n, n)):
                continue
            # 주변에 원본이 여기보다 작은데 누적수가 큰 셀이 있다면 그것 +1 을 가지고, 없다면 값 1을 가진다.
            if(vals[nr][nc]+1 > maxv and maps[nr][nc] < maps[rr][cc]):
                maxv = vals[nr][nc]+1
        return maxv
    totalMax = -1
    for i, v in enumerate(cells):
        # it(v)
        val, r, c = v
        vals[r][c] = getMaxv(r, c)
        totalMax = max(totalMax, vals[r][c])
    # it(vals)
    print(totalMax)
    pass

기타

devstack 셋업해봄. aws ubuntu 18.04에서는 잘 되는데, rpi에서는 쉽지 않을 듯하다.

---