log 2021-08-29

---

• study
  • rl - 3,4장 학습
• sport
  • 코테연습 - 카카오 2021 다시풀기
    • 합승 택시 요금
    • 광고 삽입

study

rl - 3,4장 학습

벨만 방정식 개념 이해. 수식은 아직 제대로 익히지 못함

sport

코테연습 - 카카오 2021 다시풀기

합승 택시 요금

그래프 g에서, 출발지점 s에서 a,b 두 경로로 갈 때, 중간 목적지 c를 어디로 해야 가장 효율적 (중복제외 두 경로 코스트 합을 최소화)인지 찾는 문제.

hint

어떻게 해야 어디까지 합승을 해야 할 지 알 수 있을까? 합승 지점을 C라고 하면, 경로는 d(s,c)+s(c,a)+s(c,b)가 된다. 그리고 이 값은 c에서 다익스트라를 돌리면 한 번에 찾을 수 있다.

X에서 다익스트라를 돌리면 X부터 출발하여 각 노드까지의 최단거리들을 얻게 되기 때문이다.

지점 개수가 200으로 크지 않으므로 모든 노드에서 다익스트라를 돌려서, 위의 값 중 최소값을 찾으면 될 것이다.

py solution

다익스트라 로직 구현이 생각 안나는데도 github copilot을 써서 실 15분정도만에 풀었다.. 주석만으로 필요한 변수까지는 선언해주지 않고, 필요한 변수들이 미리 선언되어 있지 않으면 제대로 로직이 만들어지지 않는 듯하다.

def solution(n,s,a,b,fares):
    # n: nodes
    # s: start
    # a: node a
    # b: node b
    # fares: array of node1,node2,cost
    
    # import pq
    import heapq

    # build adjaency list from fares list
    adj = {}
    for i in range(n+1):
        adj[i] = []
        
    for i in range(len(fares)):
        adj[fares[i][0]].append((fares[i][1],fares[i][2]))
        adj[fares[i][1]].append((fares[i][0],fares[i][2]))

    # print(adj)
    min_cost = 99999999999
    for c in range(1, n+1):
        dist = [99999999999]*(n+1)
        # run djiikstra for all nodes to get min cost of d(s,c)+d(c,a)+d(c,b)
        dist[c] = 0
        q = []
        heapq.heappush(q, (0, c))
        while(len(q) > 0):
            d, node = heapq.heappop(q)
            if(d > dist[node]):
                continue
            for nb, cost in adj[node]:
                if(dist[nb] > d + cost):
                    dist[nb] = d+cost
                    heapq.heappush(q, (dist[nb], nb))
            
        # d(s,c)+d(c,a)+d(c,b)
        cur_cost = dist[a] + dist[b] + dist[s]
        if(cur_cost < min_cost):
            min_cost = cur_cost
    return min_cost

광고 삽입

누적 재생 시간이 최대가 되도록 광고 삽입하기.

hint

보통 방법으로는 특정 위치에 삽입했을 때의 누적 시청 시간을 계산하려면 다음과 같이 하게 된다:

• 각 logs읽어서 해당하는 시간들에 누적시켜서, 각 시작 시간마다 쿼리해서 누적 시간 계산하여 최대인지 확인

그러나 logs 레코드 수가 최대 30만이므로 이 방법으론 시간초과된다.

그렇다면, 어떻게 더 효율적으로 만들 수 있을까? 일단, start나 end가 아닌 시간에 누적 시청량이 변하지 않으므로, 누적 시청량이 변하는 지점만 기록하여 이용하는 것이 효율적일 것이다.

1 차이 문제로 다 못품..

---