Coding 공부

def solution(board, skill):
    answer = 0
    N = len(board)
    M = len(board[0])
    skill_board = [[0 for i in range(M+2)] for _ in range(N+2)]
    cnt = 0
    for sk in skill:
        sk_type, r1,c1,r2,c2 ,degree = sk
        if sk_type == 1:
            degree = -degree
        r1 +=1; r2+=1; c1+=1; c2+=1
        skill_board[r1][c1] += degree
        skill_board[r1][c2+1] -= degree
        skill_board[r2+1][c1] -= degree
        skill_board[r2+1][c2+1] += degree
    for x in range(1,N+1):
        for y in range(1,M+1):
            skill_board[x][y] = skill_board[x][y] + skill_board[x-1][y] + skill_board[x][y-1] - skill_board[x-1][y-1]
    for x in range(N):
        for y in range(M):
            if board[x][y] +skill_board[x+1][y+1] >0:
                answer += 1
    return answer

이 문제도 실전에서 풀지 못했던 문제였다.

7번 문제에 너무 힘을 쏟은 나머지, 마지막 20분동안 풀다가 범위 측정을 제대로 못해서, 풀지 못한 문제였다.

평소 2차원 누적합을 잘 다루지 않다보니, 범위를 구하는데 실수를 했고, 그 범위의 누적합을 구하는데 연산을 실후 했다.

이 문제에서 중요한 것은 폭발 범위에 맞춰서 누적합을 할 수 있게, 숫자들을 정리해 놓고, 누적합을 구하면 되는 문제이다.

폭발이 시작하는 r1,c1에는 +degree을 해주고,

폭발이 끝나는 위치인 r2+1,c1 , r1,c2+1에는 -degree을 해준다.

그리고 중요한 것은 r2+1, c2+1 에서는 +degree를 해주는 것이다.

이 누적합을 마킹해놓은 상태에서 가로로 1번 누적합 세로로 1번 누적합을 진행을 한다고 생각을 해보면, 왜 그 위치에서 마킹을 해줘야하는지 이해할 수 있다.

이 문제는 누적합이라는 접근까지 했지만, 디버깅 할 시간이 부족해 풀지 못했던 아쉬웠던 문제였다..

2차원 누적합은 매번 풀때마다, 햇갈려하는 유형이기 때문에 좀 더 연습해야겠다.

# 매출하락 최소화

def solution(sales,links):
    N = len(sales)
    sales = [0]+sales
    tree = [[] for _ in range(N+1)]
    for parents,child in links:
        tree[parents].append(child)
    loss_sale = [[0]*2 for _ in range(N+1)]
    # loss_sale[x][0] = x번 노드가 참석하는 경우
    # loss_sale[x][1] = x번 노드가 불참석하는 경우
    def dfs(node):
        nonlocal loss_sale,tree,sales
        if not tree[node]:
            loss_sale[node][0] = sales[node]
            return

        for child_node in tree[node]:
            dfs(child_node)
            loss_sale[node][0] += min(loss_sale[child_node][0],loss_sale[child_node][1])

        
        loss_sale[node][0] += sales[node]
        atamp_loss = float('inf')
        for child_node in tree[node]:
            atamp_loss = min(loss_sale[child_node][0]-loss_sale[child_node][1],atamp_loss)
        loss_sale[node][1] = max(0,atamp_loss) + loss_sale[node][0] - sales[node]
    dfs(1)
    return min(loss_sale[1])

www.youtube.com/watch?v=FX9n1PFv2K4

BaaarkingDog 님의 풀이와 

카카오 공식블로그에 있는, tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/를 참조하여 푼 문제이다.

그러니 실질적으로, 내힘으로 푼 문제라 할순 없지만, 내가 잘 모르는 Tree-dp에 관련된 문제이고, 코드를 분석하면서, 이러한 문제 유형에 대해서 경험해보기 위해서 풀었다.

자세한 설명을 원하시는 분은 상단에 링크된 유튜브와 카카오 공식 블로그를 참조하길 바란다.

기본적인 풀이는 tree-dp에 관련된 문제였다. dp를 tree에 적용시킨 거고, dfs를 재귀방식으로 해서 푼 문제로 생각했다..

먼저 들어온 links에 대해서 부모노드에 자식노드를 추가해주는 작업을 했다.

그리고 index가 전부 1부터 시작하기 때문에 풀이의 용이함을 위해, sales 앞에 0을 추가해주었다.

이 상태에서 dfs를 통해, 매출하락 최소화를 구하는 작업을 해줬다.

loss_sale 이란 변수는 해당 노드가 워크샵에 참여유무에 따른 매출하락을 저장해놓은 변수이다.

ex ) loss_sale[x][0] 은 x번 노드가 워크샵에 참석하는 경우

      loss_sale[x][1] 은 x번 노드가 워크샵에 참석하지 않는 경우

dp는 작은단위부터 해야된다고 생각해서, 가장 끝단부터 하겠다.

1) 리프노드일 경우

  리프노드 일 경우엔, 자기자신이 참석하는 거 외에는 loss_sale을 갱신해줄만한 요소가 없다.

   loss_sale[leaf_node][0] = sales[leaf_node] 를 넣어주고 return 해주면 된다.

2) 리프노드가 아닐 경우

   리프노드가 아닐경우, 그 노드들은 팀원이면서 팀장이다. 여기서는 dfs를 들어갔을때, 팀장노드인 시점에서 들어가므로, 팀장노드라고 부르겠다.

   2-1) 팀장노드가 참석하는 경우

      > 팀장노드가 참석하는 경우에는 팀원노드들이 어떤 상태인지 상관 없기 때문에, 각 자식노드들의 참석 불참석했을          때 둘 중 최소값을 더해주면 된다.

      > 그리고 마지막으로 팀장노드의 매출 값을 저장해주면 된다.

      즉, 각 팀원노드마다  min(loss_sale[팀원노드][0],loss_sale[팀원노드][1]) 를 구해서 더해주고, 마지막에 팀장의 sales를 더해주면 된다.

   2-2) 팀장노드가 참석하지 않는 경우

       > 팀장 노드가 참석하지 않는 경우엔, 팀원 노드들 중에 한명이 무조건 참석을 해야한다. 그렇다면 매출하락폭이 최소화가 될려면 불참이었을때와 참여했을때의 loss_sale을 비교해서 그 차이가 최소값인 것을 찾아서 그 팀원노드을 선택하면 된다. 그 팀원이 불참이였다가, 참여로 전환시키는 것이기때문에 그 값을 더해주면 된다.

       > 여기서 max(0,atamp_loss)라고 해준 이유는 카카오 공식문서에서 나온 설명 마지막 부분과 부합된다.

          만약 팀원노드 A가 있다고 했을때,

          팀원노드 A가 팀장인 팀에서 최소가 되는 경우가, 팀원노드 A가 참석을 했을 때라고, 하면,

          위에서 구한, loss_sale[팀원노드 A의 부모노드][0]에 포함이 되어있을것이고, 이미 A라는 팀원이 참석한것이기

          때문에, 더해줄 필요성이 없다.

          그래서 팀원노드 A의 loss_sale은 참석했을때 loss_sale[팀원노드A][0] 보다 loss_sale[팀원노드A][1]이

           더 클 것이기 때문에 음수가 나오므로, max를 통해 0과 비교하여 음수를 방지해 주는 것이다.

        > 이렇게 참석과 불참석의 차이가 최소가 되는 노드를 선택하고 그 값에 팀장노드가 참석했을때의 값에서

           팀장노드가 참석을 안하기 때문에, 팀장노드의 매출을 빼주면 된다.

위와 같은 과정을 거친 후 CEO인 1번노드의 loss_sale의 최소값을 출력해주면 된다.

이 문제는 풀이를 보면서 풀었지만, tree와 dp에 대한 개념이 잡히지 않고서는 쉽게 풀 수 없는 문제 인것같다.

평소에도 가장 어려워하는 알고리즘이 dp와 tree이기때문에, 어려웠고, 그 2개가 합쳐진거라 더 나에게 어려움으로 느껴졌다.

이 풀이를 보면서 느낀점은 dp를 풀때에는 소분화해서 풀어야 하고, 점화식을 찾아서 동적으로 해야한다.

상반기까지 남은기간이 얼마 안남았는데,

내가 평소에 약점인 tree, dp, 플로이드, prefix_sum, 투포인터,segement tree (거의 대부분이지만) 에 대해서 더 공부해야겠다.