C# Jagged Array

LeetCode라는 곳에서 하루에 한 문제씩 알고리즘을 풀고 있는데, LINQ를 좋아해서 C#을 이용하여 풀고 있다.
요즘은 트리에 관한 문제를 풀고 있어 Edge 정보를 문제의 인풋으로 받는 경우가 많은데, 이를 테면 int[][]와 같은 형식이다.
그런데 테스트 케이스를 작성할 때에는 int[,]와 같은 dimensional array로 작성하는게 편한데, 이것이 int[][]와 어떤 차이일까 하는 생각이 들었다.

잠깐 찾아보니 int[][]와 같은 형태를 jagged array라고 하는데, dimensional array는 width x height의 길이가 일정한 배열이지만, int[][]와 같은 형태는 이 형태가 들쭉날쭉 할 수 있기 때문에 jagged array라고 부른다고 한다.

   public static class ArrayUtilities
   {
       public static T[][] ToJaggedArrayStyle<T>(this T[,] source)
       {
           var jaggedArray = new T[source.GetLength(0)][];
           for (var i = 0; i < source.GetLength(0); ++i)
           {
               jaggedArray[i] = new T[source.GetLength(1)];
               for (var j = 0; j < source.GetLength(1); ++j)
               {
                   jaggedArray[i][j] = source[i, j];
               }
           }

           return jaggedArray;
       }
   }

나 같은 경우 테스트 케이스는 dimentional array로 작성하고, 실제 로직은 문제에 맞춰 jagged array 형태로 사용하는 경우가 많아, 위와 같이 extension method를 하나 만들어두었다.

LeetCode 1519

원래도 알고리즘은 잘못했었고, 취직을 한지 오래되어서 더더욱 알고리즘에서는 거리가 멀어졌다.
아침마다 하나씩 간단하게 풀어보려고 하는데, 생각보다 시간이 길어져서 끊고 퇴근하고 푸는 경우도 있다.
1519번은 간단한 Tree를 순회할 수 있는지 물어보는 문제였다.

https://leetcode.com/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/

        private static readonly object[] TestSource_1519 =
        {
            new object[] {7, new[,] {{0, 1}, {0, 2}, {1, 4}, {1, 5}, {2, 3}, {2, 6}}, "abaedcd", new[] {2, 1, 1, 1, 1, 1, 1}},
            new object[] {4, new[,] {{0, 1}, {1, 2}, {0, 3}}, "bbbb", new[] {4, 2, 1, 1}},
            new object[] {5, new[,] {{0, 1}, {0, 2}, {1, 3}, {0, 4}}, "aabab", new[] {3, 2, 1, 1, 1}},
            new object[] {4, new[,] {{0, 2}, {0, 3}, {1, 2}}, "aeed", new[] {1, 1, 2, 1}},
        };
        
        [TestCaseSource("TestSource_1519")]
        public void Test_1519(int n, int[,] edges, string labels, int[] expectedResult)
        {
            var result = CountSubTress(n, edges.ToJaggedArrayStyle(), labels);
            Assert.AreEqual(expectedResult, result);
        }
        
        public class NodeInfo
        {
            public int NodeIndex;
            public char NodeLabel;
            public List<int> ConnectedNodes = new();
            public Dictionary<char, int> AccumulatedScores = new();
            public int DistanceFromRoot = -1;

            public int GetSubTreeScore()
            {
                return AccumulatedScores[NodeLabel];
            }

            public void AddLabelScore(char label, int value)
            {
                if (AccumulatedScores.ContainsKey(label) == false)
                    AccumulatedScores.Add(label, 0);

                var prevValue = AccumulatedScores[label];
                AccumulatedScores[label] = (prevValue + value);
            }
        }

        public int[] CountSubTress(int n, int[][] edges, string labels)
        {
            var nodes = Enumerable.Range(0, n).Select(index => new NodeInfo
            {
                NodeIndex = index,
                NodeLabel = labels[index],
            }).ToList();

            foreach (var edge in edges)
            {
                var aNode = nodes[edge[0]];
                aNode.ConnectedNodes.Add(edge[1]);
                
                var bNode = nodes[edge[1]];
                bNode.ConnectedNodes.Add(edge[0]);
            }
            
            FillOutNodeScore(nodes[0], nodes, 0);
            return nodes.Select(node => node.GetSubTreeScore()).ToArray();
        }

        public void FillOutNodeScore(NodeInfo currentNode, List<NodeInfo> nodes, int distanceFromRoot)
        {
            if (currentNode.DistanceFromRoot != -1)
                return;

            currentNode.DistanceFromRoot = distanceFromRoot;
            foreach (var connectedNodeIndex in currentNode.ConnectedNodes)
            {
                var connectedNode = nodes[connectedNodeIndex];
                FillOutNodeScore(connectedNode, nodes, distanceFromRoot + 1);

                if (connectedNode.DistanceFromRoot < currentNode.DistanceFromRoot)
                    continue;

                foreach (var (label, value) in connectedNode.AccumulatedScores)
                {
                    currentNode.AddLabelScore(label, value);
                }
            }
            currentNode.AddLabelScore(currentNode.NodeLabel, 1);
        }

나 같은 경우에는 간단한 문제더라도 좀 객체를 만들어서 하는 걸 좋아하는데, 사실 쥐뿔도 쓸모 없긴 한 것 같다.
그래도 LeetCode의 경우에는 좋은 것이, 문제를 풀고 내가 어느 정도의 시간과 공간 복잡도로 작성했는지, 다른 사람의 코드는 어떤지를 알려줘서 그걸 보면서 좀 배워가는 중이다.

Visibility Buffer Rendering with Material Graphs

언리얼의 나나이트가 매터리얼과 어떻게 상호작용하고 있는지 찾아보던 참에, 괜찮아 보이는 문서를 하나 발견했다.
http://filmicworlds.com/blog/visibility-buffer-rendering-with-material-graphs/
Visibility Buffer Rendering이 Forward, Deferred Rendering과 어떻게 다른지 설명하고, 기존 Visibility Buffer Rendering과 언리얼의 nanite가 다른 점, 그 과정에서 partial derivative를 이용해 mip-level을 구해오는 과정에서 발생할 수 있는 비효율성 뭐 그런것들을 설명해주고 있다.

좀 보고 잘 정리 + 사견을 좀 담아서 글로 정리해볼까 싶다.