오늘도 한 문제를 풀었다. LeetCode에서 처음 풀어보는 Hard 단계 문제였는데, 아마도 Hard중에서는 그렇게 어려운 편은 아니었을 것 같다.
https://leetcode.com/problems/longest-path-with-different-adjacent-characters/
이것도 Tree관련 순회 문제인데, 풀고 나서 다른 사람의 코드를 보니 필요없는 코드들이 꽤 많다는 것을 확인했다.
public class LongestPathNode
{
public int LongestPathAsRoot;
public int LongestPathAsChild;
public char Label;
public List<int> Childs;
}
public int LongestPath(int[] parent, string s)
{
var nodes = Enumerable.Range(0, parent.Length).Select(i => new LongestPathNode
{
LongestPathAsRoot = 0,
LongestPathAsChild = 0,
Label = s[i],
Childs = new()
}).ToList();
for (var i = 1; i < parent.Length; ++i)
{
var parentIndex = parent[i];
var node = nodes[parentIndex];
node.Childs.Add(i);
}
CalculateLongestPath(nodes[0], nodes);
return nodes.Max(node => node.LongestPathAsRoot);
}
public void CalculateLongestPath(LongestPathNode currentNode, List<LongestPathNode> nodes)
{
var longestPathOfChild = 0;
var secondLongestPathOfChild = 0;
foreach (var childIndex in currentNode.Childs)
{
var childNode = nodes[childIndex];
CalculateLongestPath(childNode, nodes);
if (childNode.Label == currentNode.Label)
{
continue;
}
if (childNode.LongestPathAsChild > longestPathOfChild)
{
secondLongestPathOfChild = longestPathOfChild;
longestPathOfChild = childNode.LongestPathAsChild;
}
else if (childNode.LongestPathAsChild > secondLongestPathOfChild)
{
secondLongestPathOfChild = childNode.LongestPathAsChild;
}
}
currentNode.LongestPathAsRoot = longestPathOfChild + secondLongestPathOfChild + 1;
currentNode.LongestPathAsChild = longestPathOfChild + 1;
}
http://filmicworlds.com/blog/visibility-buffer-rendering-with-material-graphs/
오늘 위 글을 마저 좀 봤다.
Visibilty Rendering이 포워드, 디퍼드 렌더링에 비해서 갖는 우위점은 Triangle이 Pixel 대비 점점 작아질 수록, 2x2 Quad로 실행되는 Pixel Shader에서 이 Quad를 여러 삼각형이 차지하게 되고, 그 경우 Quad Utilization이 낮아지면서 Pixel Shader와 Material, Lighting Shading이 강력하게 바인딩이 되어있는 포워드, 디퍼드 렌더링은 상대적으로 손해를 보는데, Visibility Rendering은 그렇지 않아 고정 비용을 감당 가능하다면 이 점에서 이득을 본다는 것이다.
좋은 글이라고 느꼈고, 만약 따로 이 글에 대해서 글을 쓰게 된다면 번역 이상의 수준으로 뭔가를 써내려갈 수 있을지? 싶다.
오늘은 끝. 내일부터는 주말이다.