Gi-Log

문제: SW Expert Academy 1248번 공통조상 (효율적인 풀이인지 검증이 필요한 풀이입니다) 주어진 트리 정보를 바탕으로, 두 정점의 공통 조상을 파악하고, 그 조상의 자식 노드 수 + 1(=서브 트리 크기)를 구하는 문제이다. 개인적으로 트리 문제가 나오면 긴장하는 편인데, 주어진 정보를 바탕으로 트리를 구현해야하나...라는 고민을 처음에 했고, 배열을 이용해서 트리를 구현하려고 했다. 하지만 공통조상을 찾기 위해서는 트리를 거슬러 올라가야할 필요가 있었기에 단순히 각 노드의 부모가 누구인지 parent라는 배열에 저장하고, 각 노드의 자식 노드는 누구(들)인지 child라는 2차원 배열에 저장하기로 하였다. 이 때 2차원 배열인 이유는, 주어진 트리가 이진 트리이기 때문인데, 그냥 vec..