정글 4주차 회고

사람에게는 각자만의 최적의 세팅이 있다.
각자 쓰는 키보드가 있고, 선호하는 기기가 다르고 테이블 셋업도 다 다르다.
여기 오기전만 해도 너무 세팅이 튀면 안될거 같아서 로우프로파일 키보드 하나 빼고 나름 평범하게 들고 왔는데
듀얼 세로모니터, 듀얼 키보드, 스플릿 키보드, 무소유 메타 등등...
시도 안해본 셋업들을 많이 봤다.
모니터암이라도 들고올걸 그랬나.

컴퓨터, 소프트웨어에게도 각각의 최적의 세팅이 있다.
이번주는 본격적으로 컴퓨터에게 최적인 알고리즘들을 학습했다.

트리

노드들이 나뭇가지처럼 연결된 비계층적 구조다. 뿌리에 더 가깝게 보이지만 뒤집어진 나무다. 트리에는 또 다른 하위트리가 있고 그 하위트리 아래에 또 다른 하위트리가 있는 구조이다. 재귀적인 자료구조라고 할수 있다.

노드에는 데이터와 하위 노드에 대한 포인터 값이 들어있고. 노드와 노드간의 연결된 선을 '간선'(edge)라고 부른다.
한 노드의 상위 노드를 부모 노드, 하위노드를 '자식 노드'라고 부르며 하나 이상의 하위 노드를 가지면 가지 노드, 하위노드가 없는 노드를 리프 노드, 상위 노드가 없는 노드를 루트 노드라고 부른다.
어떤 노드가 루트노드로부터 간선기준으로 얼마나 떨어져있냐를 깊이라고 부른다. 루트 노드의 깊이는 0이라고 할수 있고, 그 자식 노드의 깊이는 1이라고 할 수 있다. 루트 기준으로 같은 간선만큼 떨어져 있는 노드들을 같은 레벨로 묶는다.

트리중에 자식노드가 최대 2개인 트리가 이진 트리. 그 중에서도 리프 노드들을 제외한 같은 층의 노드들이 전부 차있고 리프노드를 왼쪽부터 오른쪽으로 차례대로 쌓아놓은 트리를 완전 이진 트리라고 부른다.

이 완전 이진트리의 특징이라면.
루프노드를 숫자 1로 놓고 낮은 레벨부터 좌 우 순서대로 나열할 때 숫자 N인 한 노드에 대해 부모 노드는 N/2, 자식노드는 2N, 2 N +1이 된다.
이를 잘 이용하면 부모노드와 자식노드를 계산 한번으로 찾을수 있게 된다.

그래프

트리는 그래프의 일종이라고 할수 있다.
그래프는 트리와 동일하게 노드와 그 노드를 연결하는 간선으로 이루어진 비계층적 구조다. 트리와 달리 방향성이 없을수도 있고 그래프에는 순환이 존재할수 있다. 부모나 자식 개념은 없고 정점과 간선 개념이 있다.

탐색 알고리즘

그래프와 트리에는 탐색 알고리즘이 있다. 보통 모든 정점을 효과적으로 전부 방문하기 위한 방법이다. 목적에 따라 깊이 우선 탐색(dfs) 너비 우선 탐색(bfs)로 나눠진다.
dfs는 하나의 정점에서 한방향으로 갈수 있을 때까지 깊게 파고들며 탐색하고 다시 돌아와서 다른방향으로 또 깊게 파고 들고... 그런 탐색 방식이다. 보통 재귀함수를 호출하여 구현하거나 FILO방식인 스택을 활용하여 구현한다. 스택 사용시 최근에 방문한 노드에서 인접한 노드 먼저 들어가게 되므로 DFS로 구현할수 있다.
BFS는 너비우선 탐색으로 거리가 가까운 정점들 먼저 모두 방문하고 그 다음 가까운 정점들을 탐색하는 방식이다. FIFO 방식인 큐를 활용하여 구현한다. 처음 노드에서 인접한 노드먼저 차례대로 들어가게 되므로 BFS로 구현할수 있다.

위상정렬

위상정렬은 대충보면 이해하기가 쉽지않다. 선행으로 방문해야하는 노드들이 있을 때 그 방문 순서를 결정해주는 알고리즘이다. 기본적으로 그래프와 달리 방향성이 무조건 있어야 하고 순환구조가 아니어야만 한다.
위상정렬을 구현할때는 진입 차수라고 특정 정점으로 들어오는 간선의 개수를 활용한다. 진입차수가 0인 정점의 경우 제일 먼저 방문하는 정점이거나 선행으로 방문해야하는 정점을 방문해서 진입차수가 변한 경우이므로 진입차수가 0이고 방문하지 않은 노드 순서대로 나열하면 되는 정렬이다.

수요코딩회

돌고 돌아 다시 돌아온 수요코딩회다.
리액트의 Virtual DOM과 diff알고리즘을 구현하는 것이 목표이다.
하지만 웹 개발과는 담 쌓고 지냈던지라 이게 뭔지 학습해야 했다.

React

메타에서 페이스북 UI구축을 위해 만든 자바스크립트 라이브러리이다. 가상 돔을 활용하여 렌더링 성능을 극대화 해주고, UI를 독립적이고 다시 사용가능한 컴포넌트 단위로 분할하여 개발을 용이하게 만들며, state에 따라 화면을 효율적으로 업데이트 하는데 특화되어있다.

Virtual DOM(가상 돔)

VDOM은 화면을 그리기 위해 사용되는 DOM의 가벼운 복사본이다. 브라우저의 메모리상에만 존재하며 자바스크립트 객체 형태를 가진다.
DOM을 직접 조작하면 레이아웃을 재계산과 리페인트 과정을 유발하여 성능에 저하가 생긴다. VDOM끼리 비교하여 나온 patch로 변경된 부분만 일괄 반영하면 렌더링 성능을 극대화 시킬수 있다.

Diffing 알고리즘

react에서 두개의 가상돔 트리를 비교하여 어떤 부분이 변경 되었는지 파악하는 알고리즘이이다. 일반적인 트리 비교는 O(N^3)의 시간 복잡도를 가지지만 React에서는 key로 자식요소를 식별하는 방법과 노드의 태그 이름이 다르면 그 하위 트리를 전부 버리고 새로 구축하는 방식으로 동작시켜 O(n)에 가깝게 성능이 향상된다

수요코딩회 회고

diff 알고리즘이 dfs와 유사하기 때문에 개념 자체를 이해 못하는 수준은 아니었다. 웹 개발 자체가 익숙치 않다는 것 때문에 왜 VDOM이 DOM보다 가벼운지, 왜 DOM을 직접 건드리는게 성능에 저하가 생기는건지 이해하지 못해 시간이 걸렸다. 자바스크립트 또한 익숙치 않다는것이 힘들게 만들었다.
거기에 자바스크립트가 익숙치 않으니 AI협업으로 코드를 짜도 바로 와닿는게 없어 코드리뷰하는데 한참이 걸렸다.

저번주에 수요코딩회를 하면서 아쉬웠던 점 중 하나가 공통규약을 정해놓지 않아서 협업할때 동시작업을 못했던것이었는데, 이번에는 공통규약도 정해놓고 분업을 하였다. 효과적이었다. 물론 저번주 redis보다는 구현이 쉬웠겠지만 개발 시간이 크게 줄었다.
이렇게 분업을 하면서 느낀 것이 있다면, AI로 개발하면서 분업을 한다는게 아무래도 비효율적이 었던거다. 다 끝나고 팀원끼리 회고를 하면서 관련해서 토의를 했다. 다른 조에 각자 만들어서 제일 좋은걸로 제출한 조가 있었는데, 퀼리티도 더 좋아보였다. 그런데 그런 방법은 여러 사람의 코드를 비교해야하다 보니 분명 애로사항이 생길 것이었기 때문에, 명세서를 분업하여 고도화 한뒤에 각자 개발을 하고 거기서 제일 좋고 명세서를 잘 따라 만들어진 코드를 베이스로 분석하는 것으로 협의점을 찾았다.
다음주에 진행하는 나머지 React 구현에서는 한번 활용해볼 생각이다.

마치며

이번주는 알고리즘 학습에도 시간을 들였지만 알고리즘 이후에 있을 컴퓨터 구조 준비와 React 이해에 더 정성을 들인거 같다. 알고리즘 이후부터도 수요코딩회때 웹개발을 할지는 모르겠으나 앱이나 os만지는걸 좀 더 빨리 하고 싶은 마음이 든다.