[DE 데브코스] 04.15 TIL - 팀미팅 1차, 반성.., 코딩테스트 문제 풀이(Heap, DFS/BFS, DP)

토요일은 딱히 TIL을 작성하지 않아도 되는 날이나,

평일에 학습 시간이 부족했기 때문에 주말을 이용해서 추가 학습을 진행했다.

 

멘토님의 이야기와 팀 미팅 1차

• 멘토님께서 본인이 DE로 취직하시기 전에 하루 루틴, 취업 준비 과정, 코테 대비 등에 대한 경험을 말씀해주셨다.
• 확실히 공부 시간을 고3 처럼 정말 많이 가져가셨다. 나는 반성해야겠다.(1)
• 그리고 고3 마냥 정해진 시간에 공부하고, 운동하고, 취침하는 루틴을 충실히 세우셨다.. 또 반성해야겠다.(2)
• <빅데이터를 지탱하는 기술>, <데이터 파이프라인 핵심 가이드> 등의 책도 추천해주셨다.
• 가장 중요한 공부는 CS 기본기라고 강조해주셨다. 티스토리에 네트워크-OS 정리하다가 말았는데 반성해야겠다.(3) 
• 짧은 시간이었지만 반성에 반성에 반성을 하는 계기.. 좀 더 치열함을 가지고 여유를 놔줘야겠다.

 

Heap 문제 풀이

• 프로그래머스의 <더 맵게> 라는 Lv.2 Heap 문제를 풀이했다.
• (해설을 듣기 전) scoville을 오름차순으로 정렬하고, 앞에 원소가 K보다 작다면 popleft()로 2개 뺀다음에 섞은 음식으로 만든다.
• (해설을 듣기 전) 섞은 음식은 list를 탐색하여 적절한 위치에 넣는다.
• (해설을 듣기 전) 앞에 원소 체킹 반복.
• (해설을 듣기 전) len(scoville)이 2보다 작은데, K값 보다 원소가 작다면 return -1
• 위는 O(n^2)로 시간초과 나기 딱 좋다. min Heap을 이용한 알고리즘을 생각해보자.
• 힙의 삽입, 삭제 연산과 필요에 따라서 heap[0], heapify 등을 이용하면 되겠다.
• 힙의 삽입, 삭제 연산은 O(log N)의 시간 복잡도를 가지고, heapify는 O(N log N)이 든다.
• 이 문제는 힙을 이용하여 최소 값을 꺼내고, 최소 값이 K보다 크거나 list의 길이가 0이 될때는 예외처리.
• 그렇지 않으면 2번째 수도 pop으로 꺼내서 새로운 원소로 만들고 이를 heap으로 넣는다.
• 이를 쭉 반복한다. ( 반복문의 종료 조건은 min > K 거나, len(list) == 0이다. )
• 위 힙을 이용한 풀이는 O ( N log N ). -> heapify 연산이 지배한다.
• 문제에 대한 답안 코드는 다음과 같다.

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while True:
        # heap을 이용해서 최소값을 꺼낸다.
        min1 = heapq.heappop(scoville)
        if min1 >= K:
            break
        elif len(scoville) == 0:
            answer = -1
            break 
        min2 = heapq.heappop(scoville)
        newval = min1 + min2 * 2
        heapq.heappush(scoville, newval)
        answer += 1
    return answer

 

DFS/BFS

• 프로그래머스의 <여행경로> 라는 Lv.3 탐색 문제를 풀이했다.
• 내가 제일 좋아하는 유형이다. DP처럼 점화식 생각하느라 머리가 빠지지도 않는다. 쉽게 말하면 만만하다.
• DFS는 보통 stack을 이용할 수 있고, BFS는 Queue를 이용해서 풀이할 수 있다.
• 위 문제는 모든 간선을 거치는 것이 핵심이다. 모든 정점 방문이 아니고.
• 그래프는 사전을 이용하여 각 노드에서 출발하는 엣지의 집합을 표현할 수 있다.
• 예시로 { ICN : [ATL, SFO], ATL : [ICN,SFO] } 이런식으로..
• 단, 리스트의 경우 뒤에서부터 제거하는게 좀 더 효율적이므로, 알파벳의 역순으로 정리한다.

def solution(tickets):
    dic = {}
    for t in tickets:
        dic[t[0]] = dic.get(t[0], []) + [t[1]]
    
    for d in dic:
        dic[d].sort(reverse=True)
        
    print(dic)
    #DFS
    stack = ["ICN"]
    answer = []

    while len(stack) > 0:
        top = stack[-1]
        if top not in dic or len(dic[top]) == 0:
            answer.append(stack.pop())
        else:
            stack.append(dic[top][-1])
            dic[top] = dic[top][:-1]
    return answer[::-1]

 

다이나믹 프로그래밍(DP)

• 프로그래머스의 <N으로 표현> 이라는 Lv.3 DP 문제를 풀이했다.
• 부분해가 전체 문제의 해가 되는 알고리즘이다.
• 피보나치 수열을 구하는 문제들이 보통 DP로 구현하는 대표적인 유형이다.
• 피보나치 문제를 재귀로 구현하면 200% 시간초과가 발생하기 때문에 ex) f(100) = f(99) + f(98) : 지수시간
• 다이나믹 프로그래밍으로 divide and quanquer 방식을 이용하곤한다.
• f(0) = 0, f(1) = 1, for i in range(2:N+1): f(i) = f(i-1) + f(i-2) 와 벌써 쉽다!
• 다이나믹 프로그래밍을 적용한 알고리즘은 복잡도가 선형함수의 형태로 나타난다. (기껏해봐야 O(N))

 

공부하며 어려웠던 내용

• 여전히 알고리즘 문제 풀이에서 좀 더 효율적인 최적의 알고리즘을 찾아내는건 쉽지 않게 느껴진다.
• DFS/BFS는 나에게 익숙한 유형임에도 불구하고 lv.3 문제는 풀이법을 스스로 생각해내지 못했다.
• 특히 재귀를 이용한 DFS에 익숙한 나머지 스택 방법을 이해하는데 시간이 좀 걸렸다.