Coding 공부

import sys
sys.setrecursionlimit(10000)
def input():
    return sys.stdin.readline().rstrip()


def LCS(X,Y):
    if depth[X] != depth[Y]:
        if depth[X]>depth[Y]:
            X,Y = Y,X
        for i in range(MAX_NODE-1,-1,-1):
            if (depth[Y]-depth[X] >= (1<<i)):
                Y = parents[Y][i]
    if X == Y:
        return X
    if (Y != X):
        for i in range(MAX_NODE-1,-1,-1):
            if parents[X][i] != parents[Y][i]:
                X = parents[X][i]
                Y = parents[Y][i]
    return parents[X][0]
def tree_make(idx,cur_node,node_cnt,parent_idx):
    if idx == len(binary_list):
        return
    if binary_list[idx] == 0:
        node_cnt += 1
        cur_node = node_cnt
        binary_search[idx+1] = cur_node
        tree[cur_node].visited.append(idx+1)
        tree[cur_node].parent = parent_idx
        depth[cur_node] = depth[parent_idx] + 1
        parents[cur_node][0] = parent_idx
        if cur_node != 1:
            parent_node = tree[cur_node].parent
            if tree[parent_node].left == None:
                tree[parent_node].left = cur_node
            else:
                tree[parent_node].right = cur_node
        tree_make(idx+1,cur_node,node_cnt,cur_node)
    else:
        binary_search[idx+1] = cur_node
        tree[cur_node].visited.append(idx+1)
        cur_node = tree[cur_node].parent
        tree_make(idx+1,cur_node,node_cnt,cur_node)



class Node():
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        self.parent = None
        self.visited = []

N = int(input())
binary_list = list(map(int,list(input())))
i,j = map(int,input().split())
tree = [Node(i) for i in range(N+1)]
MAX_NODE = 15
binary_search = [0 for _ in range(len(binary_list)+1)]
depth = [0 for _ in range(N+1)]
parents = [[0 for _ in range(MAX_NODE)] for _ in range(N+1)]

tree_make(0,0,0,0)
for par_idx in range(1,MAX_NODE):
    for k in range(1,N+1):
        parents[k][par_idx] = parents[parents[k][par_idx-1]][par_idx-1]

X,Y = binary_search[i],binary_search[j]

result_node = LCS(X,Y)
print(*tree[result_node].visited)

LCA를 이용해서 풀어본 처음 문제였다.

LCA를 공부하면서 푼 풀이이다. 

LCA에 대한 자세한 설명은

https://jason9319.tistory.com/90    https://www.crocus.co.kr/660    https://m.blog.naver.com/kks227/220820773477  https://velog.io/@lre12/LCA-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Lowest-Common-Ancestor

위의 사이트들을 참조하길 바란다.

LCA를 공부하면서, 이해하다가 막혔다가 푼 부분을 적으면 다음과 같다.

1. 부모를 저장하는 dp 테이블에는 해당 노드의 모든 부모를 저장하는 것이 아닌 2^k번째 부모들만 압축해서 저장해놓는것이다.

2. 위의 파생이지만, 그렇기 때문에, 두 높이의 차이가 1<<i 즉 2^i 차이가 나면, i만큼 올려주면 되는것이다.

3. 그리고 두 높이가 같고, 서로 다르다면, k번째 위치부터 다른 값까지 한꺼번에 올려버린다.

  즉, dp[node1][k] , dp[node2][k] 는 다르지만, dp[node1][k+1], dp[node][k+1]이 같으면

   각 노드들의 2^k + 1 ~ 2^(k+1) 사이에 최소 공통 조상이 있을 것이다. 이 부분을 주의하면 된다.

4. 또한, 첫번째에서 말한것처럼 2^k번째 만 저장을 시켜놓은것이기때문에

    2^(k+1) = 2^k + 2^k 이다.

    2^k = 2^(k-1) + 2^(k-1) 이므로,

dp[node][k] = dp[ dp[node][k-1] ] [k-1] 으로 하면 LCA의 해당 노드들의 모든 공통조상부모에 대해서 저장시킬수 있다.

위의 것들이 윗 링크들을 공부하면서 제가 깨달은 부분이다.

인제는 문제로 돌아가서 

여기서 문제에 주어진 비트를 트리구조로만 바꾸면 우리는 위에서 배운 LCA를 적용시키면 된다.

저는 여기서 이 문제를 해결하기 위해 Node라는 클래스를 만들어놨습니다.

해당 Node에는 총 5가지의 파라미터가 있습니다.

data는 이 노드의 번호를 나타내고,

left는 왼쪽 자식번호

right는 오른쪽 자식번호

parent는 부모 번호

visited는 우리가 주어진 비트에서 몇번재 비트에서 이 노드를 방문했는지 표시르 위한 것입니다.

저는 tree_make라는 재귀함수를 만들어 이 문제를 해결했습니다.

입력 parameter는 4가지가 있고, idx는 현재 입력으로 주어진 비트의 몇번째 idx인지를 나타냅니다.

cur_node는 현재 노드의 번호입니다.

node_cnt는 지금까지 생성된 노드의 개수입니다.

parent_idx는 부모 노드의 번호입니다.

비트에서 우리가 0을 만나면 최초로 생성되는 노드로 진입하게 되는겁니다.

그래서 node_cnt를 1을 늘려주고, cur_node를 node_cnt로 바꿔줍니다.

그러면 우리는 현재 부모노드의 정보를 알고 있으므로,

부모노드의 left와 right 중 빈 순서대로 넣어주면 됩니다.

그리고 1을 만나게 되면 우리는 현재 방문하고 있던 노드에서 다시 되돌아가서 부모노드로 가야합니다.

그렇기 때문에 cur_node를 부모노드로 치환시키고, 재귀를 반복하면 됩니다.

즉 0을 만나면 새로운 노드가 생성이되고,

1을 만나면 부모노드로 되돌아간다는 점만 기억을 하면, 문제에서 주어진 비트를 트리로 만들 수 있습니다.

코드가 깔끔하지 못해, 다른 분들의 코드를 보는 것을 더 추천합니다.

위와 같은 작업을 해서 비트를 트리구조로 바꾼뒤에 LCA을 적용시키면 이 문제를 해결 할 수 있습니다.

LCA와 관련된 문제를 처음 풀어보았기에, 헷갈리던 점도 많았고, 트리에 대해 숙달되지 못했기에,

비트를 트리로 구현하는데에 오래 걸린 문제였습니다.

매번 트리와 관련된 문제가 나오면 문제를 해결하는데 시간이 오래걸리는 것 같은데,

이 부분을 숙달하는데 더 노력을 해야할 것 같습니다.

import sys

input = sys.stdin.readline
def dfs(node,flag,*args):
    stack = [(node,0)]
    distance_list = [0 for _ in range(N+1)]
    visited = [False for _ in range(N+1)]
    visited[node] = True
    if not flag:
        visited[args[0]] = True
    while stack:
        node,distance = stack.pop()
        distance_list[node] = distance

        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                stack.append((next_node,distance+graph[node][next_node]))
    
    temp = []

    for i in range(1,N+1):
        temp.append((distance_list[i],i))
    temp.sort(key=lambda x :-x[0])
    if flag:
        return_value = temp[0][1]
    else:
        return_value = temp[0][0]
    return return_value


N = int(input())
graph = [{} for _ in range(N+1)]
for _ in range(N-1):
    x,y,pay = map(int,input().split())
    graph[x][y] = pay
    graph[y][x] = pay

first_point = dfs(1,True)
second_point = dfs(first_point,True)

first_value = dfs(first_point,False,second_point)
second_value = dfs(second_point,False,first_point)

print(max(first_value,second_value))

 이 문제는 트리의 지름을 구하는 방법을 응요한 문제이다.

총 4번의 dfs를 통해 두번째 트리의 지름을 알 수 있다.

첫번째 dfs를 통해 아무지점에서 가장 먼 지점을 구한다.

이 지점은 지름을 구성하는 한 점이 될것이다.

두번째 dfs를 통해 첫번째 dfs에서 구한 점에서 가장 먼 점을 구한다.

그러면 이 점은 트리의 지름을 구성하는 가장 먼 점이 될것이다.

이렇게 2번의 dfs를 통해 우리는 가장 먼 점 2개를 구했다.

그러면 이 2점을 각각 dfs를 돌려, 가장 먼 점에서 2번째인 것을 찾아낸다.

그리고 이렇게 두 거리를 구한 뒤 그 중에 더 큰 점을 선택하면 되는 문제이다.

import sys

input = sys.stdin.readline
def dfs(node):
    distance_list = [0 for _ in range(N+1)]
    visited = [False for _ in range(N+1)]
    visited[node] = True
    stack = [(node,0)]
    while stack:
        node,distance = stack.pop()
        distance_list[node] = distance
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                stack.append((next_node,graph[node][next_node]+distance))
    return distance_list

N = int(input())
graph = [{} for _ in range(N+1)]

for _ in range(N-1):
    x,y,pay = map(int,input().split())
    graph[x][y] = pay
    graph[y][x] = pay


distance1 = dfs(1)
far_point1 = distance1.index(max(distance1))
distance2 = dfs(far_point1)
far_point2 = distance2.index(max(distance2))
distance3 = dfs(far_point2)
result = sorted(distance2+distance3)[-3]
print(result)

단 3번의 dfs를 통해 구하는 방법도 있다.

이 방법은 지름을 구성하는 2점의 전체길이를 한 리스트로 정하고 뒤에서 3번째를 출력해주는 것이다.

왜냐하면 한 리스트당 한 지점에서 가장 먼 지점은 서로 자신들이기 때문에, 그 2점을 제외하고 그 다음번으로 큰 것이

두번째 트리의 지름의 답이된다.

import math
import sys


def dfs(node):
    stack = [(node,0,0)]
    visited = [True]*(N+1)
    distance = 0
    max_node = -1
    min_time = float('inf')
    visited[node] = False
    while stack:
        node,dis,time = stack.pop()
        if dis > distance:
            distance = dis
            max_node = node
            min_time = time
        elif dis == distance and min_time > time:
            max_node = node
            min_time = time

        for next_node in graph[node]:
            if visited[next_node]:
                new_dis = dis + 1
                new_time = time + graph[node][next_node]
                visited[next_node] = False
                stack.append((next_node,new_dis,new_time))

    return [max_node,distance,min_time]



input = sys.stdin.readline

N,T = map(int,input().split())


graph = [{} for _ in range(N+1)]


for _ in range(N-1):
    x,y,time = map(int,input().split())
    graph[x][y] = time
    graph[y][x] = time

far_node_info = dfs(1)

result = dfs(far_node_info[0])


print(math.ceil(result[2]/T))

트리의 지름 이 문제를 풀어보면 해당 문제를 좀 더 쉽게 풀 수 있다.

문제의 조건은 총 2가지이다. 문제를 가장 많이 풀어야하며, 그 푸는데 시간이 가장 짧아야한다.

이 문제는 트리구조이다. 그래서 문제를 가장 많이 푼다는 것은 트리의 지름을 구하는것과 같다.

그러므로 처음 dfs로 아무 노드에서 가장 먼 노드를 찾고, 그 노드에서 가장 먼 노드들을 찾으면 그게 트리의 지름이 된다.

이걸 응용해서, 첫 dfs로 가장 먼 노드 하나를 찾는다.

그리고 두번째 dfs로 찾은 가장 먼 노드를 기준으로, dfs를 돌려서 깊이가 가장 깊은 노드들을 찾는다. 그리고 그 중에서, 시간이 가장 짧은 것을 선택해주면 된다.

이 문제는 1967번 문제의 트리의 지름을 응용한 문제이고, 트리의 특성에 대해 알고 있으면 쉽게 풀 수 있었던 문제였지만,

처음에 트리의 지름에 대한 아이디어를 얻지 못해서 어려웠던 문제이다.

import sys
input = sys.stdin.readline
def check(num):
    visited[num] = True
    stack = [num]

    while stack:
        node = stack.pop(0)

        for next_node in tree[node]:
            if tree[node][next_node] == 1:
                if not visited[next_node]:
                    visited[next_node] = True
                    stack.append(next_node)
                    tree[node][next_node] = 0
                    tree[next_node][node] = 0
                else:
                    return False
    return True
            


tc = 1
while True:
    N,M = map(int,input().split())
    if N+M == 0:
        break
    parent_cnt = [0]*(N+1)
    tree = [{} for _ in range(N+1)]
    for _ in range(M):
        x,y = map(int,input().split())
        tree[x][y] = 1
        tree[y][x] = 1
    cnt = 0
    visited = [False]*(N+1)
    for num in range(1,N+1):
        if not visited[num]:
            if check(num):
                cnt += 1
    if cnt == 0:
        print(f'Case {tc}: No trees.')
    elif cnt == 1:
        print(f'Case {tc}: There is one tree.')
    else:
        print(f'Case {tc}: A forest of {cnt} trees.')


    tc += 1

import sys

sys.setrecursionlimit(100001)


def dfs(node):
    visited[node] = True
    child_node = []
    for next_node in graph[node]:
        if not visited[next_node]:
            child_node.append(next_node)
    if not len(child_node):
        dp[node][0] = 1
        return
    else:
        for child in child_node:
            dfs(child)

        for child in child_node:
            if dp[child][0]:
                dp[node][1] = 1
                break
        else:
            dp[node][0] = 1

N = int(input())
graph = [[] for _ in range(N+1)]


for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
visited = [False]*(N+1)
dp = [[0]*2 for _ in range(N+1)]
dfs(1)

answer = min(list(map(sum,list(zip(*dp)))))
print(answer)

import sys
sys.setrecursionlimit(10000)
def dfs(node):
    if not graph[node]:
        return 0
    ind = 0
    for next_node in graph[node]:
        distance_nodes[node][ind] += dfs(next_node) + graph[node][next_node]
        ind += 1
    return max(distance_nodes[node])
N = int(input())
graph = [{} for _ in range(N+1)]
parents = [0]*(N+1)
for _ in range(N-1):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    parents[A] += 1

distance_nodes = [[0]*(parents[ind]+2) for ind in range(N+1)]

dfs(1)
result = 0
for ind in range(1,N+1):
    distance_nodes[ind].sort(reverse=True)
    result = max(result,distance_nodes[ind][0]+distance_nodes[ind][1])
print(result)

첫 풀이방식은 다음과 같았다. 각 노드에서 가장 긴 노드들을 더해주는 방식이었다. 리프노드에 도착하면 0을 반환해주고 

재귀를 활용해서, 현재의 노드에서 자식노드까지의 거리 + 그 자식노드의 재귀함수를 통해 최대값을 더해주는 방식으로 했다.

이렇게 모든 노드들에 대해서 거리들을 전부 구한뒤, 모든 노드들의 거리의 합이 최대가 되는것을 구해주었다.

import sys
input = sys.stdin.readline
def dfs(ind):
    global N,result,max_Node
    visited = [True]*(N+1)
    stack = []
    stack.append((ind,0))
    visited[ind] = False
    while stack:
        node, distance = stack.pop()
        if distance > result:
            result = distance
            max_Node = node
        if graph[node]:
            for next_node in graph[node]:
                if visited[next_node]:
                    visited[node] = False
                    stack.append((next_node,distance+graph[node][next_node]))


N = int(input())
graph = [{} for _ in range(N+1)]
for _ in range(N-1):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C

result = 0
max_Node = 0

dfs(1)
dfs(max_Node)
print(result)

두번째 방식은 훨씬 간단하다. 두번의 dfs로 풀리는데 다음과 같다.

어느 한 지점에서 제일 거리가 멀리 떨어진 곳에 위치 한 곳을 구하면, 그 지점이 트리의 지점을 구할 수 있는 한 점인 것을 알 수 있다.

왜냐하면, 지름은 해당 트리에서 제일 긴 곳은 지름일테고, 그렇기 때문에 그 안에 있는 점의 가장 먼거리를 가지는 점은 지름의 두 점 중 하나가 될것이다.

이걸 이용해서 첫번째 dfs에서 트리의 지름에 해당하는 한 점을 구하고,

그 점에서 dfs를 통해 최대거리를 구하면 답이 된다.

def preorder(key):
    if tree[key] == ('.','.'):
        result[0] += key
        return
    result[0] += key
    if tree[key][0] != '.':
        preorder(tree[key][0])
    if tree[key][1] != '.':
        preorder(tree[key][1])

def inorder(key):
    if tree[key] == ('.','.'):
        result[1] += key
        return
    if tree[key][0] != '.':
        inorder(tree[key][0])
    result[1] += key
    if tree[key][1] != '.':
        inorder(tree[key][1])
def postorder(key):
    if tree[key] == ('.','.'):
        result[2] += key
        return
    if tree[key][0] != '.':
        postorder(tree[key][0])
    if tree[key][1] != '.':
        postorder(tree[key][1])
    result[2] += key


tree = {}


N = int(input())
for _ in range(N):
    root,left,right = input().split()
    tree[root] = (left,right)
result = ['','','']
preorder('A')
inorder('A')
postorder('A')

for answer in result:
    print(answer)

트리의 대표적인 순회 종류인 전위, 중위, 후위 탐색기법을 적용시킨 것이다. 트리에 대해서 아직 잘 몰라, 실제 이진 트리를 만들면서 더 연습해봐야겠다.

일단 풀이는 재귀방식을 이용해서, 구해줬다. 일단 

전위 순회 방식은 (루트 -> 왼쪽 -> 오른쪽 자식) 이므로, 함수를 돌릴때 root에 해당되는 함수에 들어온 key를 결과값에 넣어주고, 그 다음에 왼쪽 , 오른쪽 순으로 함수를 재귀적으로 실행시켜줬다.

중위 순회는 왼쪽 -> 루트 -> 오른쪽 순으로 해줬다.

후위 순회는 왼쪽 -> 오른쪽 -> 루트  순으로 해줬다.

# 매출하락 최소화

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 (거의 대부분이지만) 에 대해서 더 공부해야겠다.