say_ye.log

[JS] 비트연산을 이용한 2차원 Map Editor 만들기

Sat, 21 Jan 2023 11:50:20 GMT

2차원 지형을 표현하는 맵은 어떻게 구현할 수 있을까요? 이번 포스팅에서는 비트연산을 활용하여 2차원 Map Editor를 만드는 방법에 대해 알아보겠습니다.

준비물 : map image asset

https://cupnooble.itch.io/sprout-lands-asset-pack 저는 위의 무료 애셋을 사용했습니다.

참고로 예시처럼 sprite 이미지로 저장되어 있는 애셋을 사용하면 코드작성 및 리소스 관리측면에서 편리하고 네트워크 요청을 한번만 보내기 때문에 성능상 유리할 수 있습니다. 만일 타일 이미지가 따로 저장되어있는 애셋을 구했다면 Sprite generator(링크) 툴을 이용하여 만들어 사용하기를 권장합니다.

각 타일의 정보를 저장

맵 애셋을 준비했으면 각 타일들의 정보를 데이터로 저장해야합니다. 저는 각 타일의 데이터를 key(비트마스크) => value(sprite상의 좌표) 형식의 Map 데이터로 저장했습니다.

각 맵의 타일모양은 위와같이 3x3 그리드 형식으로 표현될 수 있습니다. 이 타일들을 비트마스크 형식의 데이터로 치환하기위해 빈 곳을 0, 땅을 1이라고 했을 때, 가장 왼쪽위의 타일은 000 011 011 이 됩니다. 그리고 sprite 좌표상으로는 0번째 행과, 0번째 열에 있습니다. 그럼 해당 타일에 대한 정보는 000011011 => [0,0] 이 되는 것입니다.


export const GRASS_COORDINATE = new Map([
  [0b000011011, [0, 0]],
  [0b000111111, [0, 1]],
  [0b000110110, [0, 2]],
  [0b000010010, [0, 3]],
  [0b000011010, [0, 4]],
  [0b000111110, [0, 5]],
  [0b000111011, [0, 6]],
  [0b000110010, [0, 7]],
  [0b000111010, [0, 8]],
  [0b110111011, [0, 9]],
  [0b011011011, [1, 0]],
  [0b111111111, [1, 1]],
  [0b110110110, [1, 2]],
  [0b010010010, [1, 3]],
  [0b011011010, [1, 4]],
  [0b111111110, [1, 5]],
  [0b111111011, [1, 6]],
  [0b110110010, [1, 7]],
  [0b111111010, [1, 8]],
  [0b011111110, [1, 9]],
  [0b011011000, [2, 0]],
  [0b111111000, [2, 1]],
  [0b110110000, [2, 2]],
  [0b010010000, [2, 3]],
  [0b010011011, [2, 4]],
    ...
]);

Map의 key는 이진수 리터럴로 작성합니다. (댓글로 의견주신 superlipbalm님 감사합니다)

여기서 순수 Object가 아닌 Map 타입을 쓴 이유는, Number타입을 key로 사용하기 위해서입니다. 순수 Object는 String, Symbol값만을 key로 가질 수 있습니다. ({1:'hello'} 와 같이 Object를 선언하는것이 가능하지만 이 경우도 key가 String 타입으로 묵시적 형변환 되는 것입니다.)

🤔 타일이 이게 전부인가요?

그런데, 각 맵타일이 3*3 그리드, 즉 9비트짜리 이진수와 대응된다는 점에서 착안하면 훨씬 많은 타일이 있어야하지 않을까요? 비어있는 맵을 제외하면 000000001 ~ 111111111 에 해당하는 타일이 모두 있어 총 2^9-1개의 타일이 있어야 하는거 아닌가? 라는 의문이 들 때쯤, 가져온 map asset을 다시 살펴봅시다.

보아하니 모든 타일들은 두가지 가정을 만족합니다.

중앙 비트(5번째비트)가 1이다.

꼭지점 비트(1,3,5,7번째 비트)가 1인 경우, 해당 비트와 인접한 두개의 비트도 모두 1이다.

이는 타일들이 밟을 수 있는 땅(중앙비트가 1)만을 표현하며, 타일이 이어질때는 항상 면끼리 맞대어서 이어진다는 것을 의미합니다.

위의 두 가정을 만족하지 못하는 타일 데이터는 asset에 존재하지 않는다. 즉, 빈 땅으로 보여지는 유효하지 않은 타일이다.

위 규칙을 잘 활용하면, 47개의 타일로도 면으로 인접했을 때 이어지는 맵 을 충분히 구현해낼 수 있습니다. 참고로 꼭짓점 비트를 기준으로 세어보면 타일의 경우의 수를 쉽게 찾아낼 수 있습니다.

에디터에서의 타일 데이터 저장

그렇다면 현재 편집중인 map 데이터는 어떻게 저장하면 좋을까요? 저는 맵 데이터를 유효한 데이터로 변경하는 전처리를 위해 raw, real 이라는 두가지 배열을 선언하여 사용했습니다.

가령, 위처럼 맵을 그리면 데이터는 다음과 같이 변합니다. (주변의 비어있는 부분은 편의상 생략했습니다.)

raw : 땅과 주변에 이어진 땅의 유무를 모두 가지고 있는 데이터 배열 real : raw 데이터를 유효한 타일 데이터로 변경한 데이터 배열

raw, real 초기화

raw = Array.from(Array(CONSTANT_ROW), () => Array(CONSTANT_COL).fill(0))
real = Array.from(Array(CONSTANT_ROW), () => Array(CONSTANT_COL).fill(0))

원하는 맵 에디터의 행, 열만큼 0으로 채운 동일한 Array로 선언합니다.

raw 생성

셀을 클릭하면 해당 셀의 중앙비트를 1로 변경
클릭한 셀의 주변 8개 셀 중에 땅이 있으면 해당 방향의 인접비트를 1로 변경
주변 8개 셀의 마주보는 부분의 비트도 1로 변경

real 생성

raw 데이터의 선택셀과 주변 셀을 확인하여 유효 타일로 변환 후 real 배열에 반영 [유효타일 변환 과정] - 중앙비트가 1이 아닌경우 -> 000000000 - 모든 꼭짓점을 확인하여 꼭짓점 비트가 1이면서 해당 꼭짓점과 인접한 비트가 1이 아닌경우 해당 꼭짓점비트 0으로 변경

위의 작업들을 처리하기위해 자바스크립트에서 지원하는 몇가지 비트 연산자들을 사용할 수 있었습니다.

비트연산

n번 비트를 1로 변경 bitData |= 1 << n-1
n번 비트가 1인지 확인 bitData & (1 << n-1)
n번 비트를 0으로 변경 bitData &= ~(1 << n-1)
꼭짓점 비트가 1이면서 꼭짓점 주변 비트가 1이 아닌지 확인 (bitData & (1 << 꼭짓점인덱스)) && !(bitData & (1 << 주변1인덱스) && bitData & (1 << 주변2인덱스))

sprite 이미지 사용하기

const [coordX, coordY] = GRASS_COORDINATE.get(bitData)
...

real 데이터 배열을 2중 map을 돌려 bitData로 뽑아내고, 위에서 정의한 GRASS_COORDINATE 를 이용하여 asset상의 좌표로 변환합니다. 이 좌표와 한 타일의 가로, 세로 픽셀크기에 해당하는 GRID_SIZE를 이용하여 해당하는 맵 이미지를 가져올 수 있습니다. (GRID_SIZE는 본인이 사용하는 이미지에 맞게 정의해서 사용하면 됩니다.)

소스코드 및 실행화면

https://playcode.io/1083380 위의 링크를 누르면 react로 구현한 소스코드와 실행화면을 확인해 볼 수 있습니다.

[백준] 1477 : 휴게소 세우기

Tue, 27 Dec 2022 06:34:11 GMT

문제링크

풀이

import math
import sys

input = sys.stdin.readline
n, m, l = map(int, input().split())
분기점 = [0] + list(map(int, input().split())) + [l]
분기점.sort()

for i in range(m):
  구간길이 = [분기점[i+1] - 분기점[i] for i in range(n+1)]

몇등분 = [1] * len(구간길이)

for _ in range(m):
  등분된길이 = [math.ceil(x / y) for x,y in zip(구간길이, 몇등분)]
  더나눌구간 = 등분된길이.index(max(등분된길이))
  몇등분[더나눌구간] += 1

최대구간길이 = max([math.ceil(x / y) for x,y in zip(구간길이, 몇등분)])
print(최대구간길이)

풀이방법

각 구간길이와 각 구간길이를 몇등분할지 저장하는 배열을 선언한다.
m번의 시행마다 구간길이 / 몇등분을 반올림한 결과가 가장 큰 인덱스의 등분을 +1 증가시킨다.
최종적으로 구간길이 / 몇등분 을 반올림한 결과가 가장 큰 값이 휴게소간 최대거리가 가장 짧은때의 값이된다.

채점결과

[JS] 소수점 계산 오차

Mon, 26 Dec 2022 13:28:54 GMT

컴퓨터는 숫자를 2진수로 저장하여 계산합니다. 이때 만일 2진수로 변환하고자 하는수가 소수타입이라면 어떻게 될까요?

0.5 => 0.1 0.25 => 0.01 0.75 => 0.11 0.3 => 0.0100110011001.....(무한소수)

위의 예시 케이스들을 보면 알 수 있다시피, 2의 제곱 꼴의 합으로 소수를 표현해야 하므로 몇 가지의 케이스(분모가 2의 거듭제곱 꼴)를 제외하고는 소수들을 정확하게 표현하기에는 한계가 있습니다.

그래서 이런 문제가 눈앞에서 발생하곤 합니다.

우리의 JS가 또...🤦 라고 생각 할 수 있지만 사실 이는 JS만의 문제는 아닙니다. 사실 파이썬을 포함한 많은 언어가 이렇습니다.

서치하면서 몇가지 글들을 살펴보니까 JS는 부동소수점 방식을 사용해서 그렇다고 이야기하는데.. 부동소수점 방식이든, 고정소수점 방식이든 둘 다 오차가 발생합니다. 소수부를 이진수로 표현하고자 하기때문에 오차가 나는 것이니까요.

이런 오차를 해결하기 위한 방법으로 어떤것들이 있는지 알아봅시다.

1. toFixed 메서드 사용

Number.prototype.toFixed() 를 사용하면 파라미터로 주어진 자릿수까지 반올림한 결과를 문자열로 리턴합니다. 문자타입으로 리턴하므로 다음 계산에서 사용하기 위해서는 숫자형으로 변환해야 합니다.

2. 정수로 만들어서 계산

10ⁿ(n=소수점 최대 길이) 만큼 곱해줘서 정수로 만들고, 계산 후 마지막에 다시 10ⁿ만큼 나누는 방법입니다.

3. Math 모듈을 사용

Math.ceil, Math.floor, Math.trunc, Math.round 와 같은 정수형 변환 메서드들을 사용하는 방법입니다. 정수로만 변환이 가능하므로 소수 계산을 위해서는 자릿수 보정이 필요합니다.

###

4. decimal.js 같은 라이브러리 사용

Source Code 위의 소스코드를 보면 decimal.js 에서 소수점 오차문제를 어떻게 해결하고 있는지 알 수 있습니다.

d3로 동적인 네트워크 차트 그리기 (3) - D3.js - Simulation

Fri, 23 Dec 2022 04:58:57 GMT

앞선 포스팅에서 간단한 네트워크 차트를 그려봤습니다. 앞에서는 데이터에 각 노드별 x, y좌표를 직접 설정 해주고, nodes-links를 직접 매핑해 줬습니다. 이번 포스팅에서는 D3의 forceSimulation과 simulation객체의 메서드들을 이용하여 이 과정을 자동화하고, 꿈틀거리며 그래프가 부드럽게 생성되는 애니매이션도 함께 구현해보겠습니다.

simulation

d3.forceSimulation(nodes) nodes 배열을 사용하는 새로운 시뮬레이션을 생성합니다. 시뮬레이션은 자동으로 시작되며, simulation.on("tick", callback)을 통해 각 tick마다(default-300회) 실행될 콜백을 지정할 수 있습니다. 만일 시뮬레이션의 실행시점을 직접 조작하고싶다면, simulation.stop()을 호출하고, 원하는 시점에 simulation.tick()을 실행하면 됩니다.
simulation.force(name[, force]) 시뮬레이션에 지정된 name과 함께 force를 할당하고, 그 시뮬레이션을 리턴합니다. 이 때 name은 사용자가 원하는대로 이름 붙이는 값이므로 마음대로 써도 됩니다. (이 name은 메모리에서 내부적으로 forces Map의 key값이 될 뿐입니다) (simulation.force("중력", d3.forceManyBody()) 이렇게 해도 됨) 하지만 공식문서에서 charge, center, link 와 같은 이름을 사용하기때문에 어느정도 저런 명칭을 사용하는 암묵적인 약속(?)은 있는 듯 합니다.
simulation.on(typenames, [listener]) typenames("tick" 혹은 "end")에 해당하는 이벤트에 대한 리스너를 등록합니다. tick : 시뮬레이션 내부 타이머의 틱마다 발생합니다. end : 시뮬레이션 내부 타이머의 틱이 종료될 때 발생합니다. simulation.on("tick", callback)을 이용하여, 부드러운 애니매이션을 표현하는게 가능해집니다. 노드의 좌표가 tick마다 조금씩 변경되면서 x,y 속성이 계산되고, 이 때마다 node, links를 그리면 부드러운 애니매이션이 구현되는 것입니다.

nodes, links data-set

이제 node에 직접 x, y를 설정하거나 links를 전처리하지 않아도 됩니다.

let nodes = [
  { name:"ye" },
  { name:"jun" },
  { name:"mi" },
  { name:"sung" },
]
let links = [
  { source:"ye", target:"jun" },
  { source:"jun", target:"mi" },
  { source:"mi", target:"sung" },
  { source:"sung", target:"jun" },
]

data-binding, attribute 정의

node, link selection에 데이터를 바인딩하고, 속성을 정의하는 로직은 기존 방식과 동일합니다.

const node = 
      d3.select("#node")
        .selectAll("g")
        .data(nodes)
        .join("g")
        .each(function(d) {
          d3.select(this)
            .append("circle")
            .attr("r", 5)
            .style("fill", "red");
          d3.select(this)
            .append("text")
            .text(d => d.name);
      })

  const link = 
        d3.select("#link")
          .selectAll("line")
          .data(links)
          .join("line")
          .attr("stroke", "black");

function drawNodes(){
  node.attr("transform", d =>"translate("+[d.x, d.y]+")" );
}

function drawLines() {
  link
    .attr("x1", d => d.source.x)
    .attr("y1", d => d.source.y)
    .attr("x2", d => d.target.x)
    .attr("y2", d => d.target.y)

}

simulation 객체를 이용한 노드 좌표계산 및 nodes-links 매핑

d3.forceSimulation(nodes)
  .force('charge', d3.forceManyBody().strength(-200)) // 1️⃣
  .force('center', d3.forceCenter(250, 250)) // 2️⃣
  .force('link', d3.forceLink(links).id(d => d.name)) // 3️⃣
  .on("tick", () => {
    drawNodes();
    drawLines();
}); // 4️⃣

1️⃣ 노드간의 중력을 정의합니다. default값은 -30이며, strength() 메서드를 이용하여 힘의 크기를 정의할 수 있습니다. 음수이면 척력, 양수이면 인력을 의미합니다. 2️⃣ viewport에서 그래프의 중앙 좌표를 설정합니다. 3️⃣ nodes와 매핑될 links 배열을 넘겨, 매핑된 결과 생성합니다. 이 links는 source, target 을 속성으로 가지는 객체의 배열입니다. id() 메서드를 통해 node의 어느 속성을 식별자로 가질지 설정할 수 있습니다. (설정하지않으면 node의 index로 매핑됩니다) 4️⃣ simulation tick마다 실행할 함수를 정의합니다.

코드 실행화면

!codepen[yeynii/embed/rNrVzgN?default-tab=js%2Cresult]

그럼 이렇게 노드 좌표도 자동으로 계산해주면서, 꿈틀거리는(‼️) 네트워크 차트가 완성됩니다.

d3로 동적인 네트워크 차트 그리기 (2) - D3.js - selections & join

Tue, 20 Dec 2022 08:55:43 GMT

d3-selections

selections는 data 기반의 DOM 변형객체입니다. d3.select, d3.selectAll을 사용하면 html과 svg 요소를 선택하는 selection 객체를 반환합니다.

d3.select(selector)

selector에 해당하는 첫번째 element와 매칭됩니다.

d3.selectAll(selector)

selector에 해당하는 모든 element와 매칭됩니다.

여기서 selector는 css에서의 selector string 혹은 해당 파라미터 자체를 의미합니다.

d3.select() source

import {Selection, root} from "./selection/index.js";

export default function(selector) {
  return typeof selector === "string"
      ? new Selection([[document.querySelector(selector)]], [document.documentElement])
      : new Selection([[selector]], root);
}

d3.selectAll() source

export default function(selector) {
  return typeof selector === "string"
      ? new Selection([document.querySelectorAll(selector)], [document.documentElement])
      : new Selection([array(selector)], root);
}

⇒ 코드 내부적으로 string이 아닌 파라미터가 들어오면 그 파라미터 자체를 select

따라서 리액트에서 다음과 같이 useRef를 이용하여 돔요소를 select할 수 있습니다.

function App() {
  const svgRef = useRef();

  useEffect(() => {
    const p = d3
      .select(svgRef.current)
  }, []);

  return (
    
      
    
  );
}

join

selection.join(enter[, update][, exit]) selection 객체에서 사용할 수 있는 메서드로, data를 기반으로 element를 추가/수정/변경합니다.

join 함수를 사용하는 방법은 두가지가 있는데, 1️⃣파라미터로 string을 넘기거나 2️⃣파라미터로 enter, update, exit 콜백 함수를 넘기는 방법입니다.

svg.selectAll("circle")
  .data(data)
  .join("circle")

위 코드는 아래코드의 축약형입니다.

svg.selectAll("circle")
  .data(data)
  .join(
    enter => enter.append("circle"),
    update => update,
    exit => exit.remove()
  )

enter : data개수 > dom개수여서, 남아도는 data에 해당하는 selection을 처리하는 방법을 정의 update : data에 대응하는 dom요소가 존재해서, 해당 data selection을 업데이트하는 방법을 정의 exit : data개수 < dom개수여서, 사라진 data selection을 처리하는 방법을 정의

(중요) d3.select는 추후 생성/변경/삭제될 element를 가리킬 수 있다.

document.querySelectorAll 은 이미 존재하는 element 배열만을 선택하여 반환하지만, d3.selectAll은 현재 매치되는 요소가 존재하지 않으면 빈 Selection 객체를 반환하게 되고, 이 Selection 객체는 추후 binding되는 data와 joining할 element-type에 해당하는 element들로 채워질 가능성이 있습니다.

즉, 지금은 selector에 해당하는 요소가 없더라도 데이터를 binding, joining 하면서 해당 요소를 생성/삭제할 수 있습니다.

예를들어, 다음과 같은 비어있는 svg 태그와 array 가 주어진다면 각 체이닝 시점별 반환 selection은 다음과 같습니다.

html

array = [1,2,3]

d3.select("svg") //1
  .selectAll("circle") // 2
  .data(array) //3
  .join("circle") //4;

container 역할을 할 element를 가리키는 Selection을 반환합니다.
데이터 배열의 요소와 join될 엘리먼트 타입을 선택합니다. 현재는 해당 엘리먼트 타입(circle)에 매치되는 요소가 없으므로, 비어있는 NodeList를 가리키는 Selection을 반환합니다.
join될 data array를 정의합니다. data의 변화를 나타내는_enter, _exit 프로퍼티에 data가 바인딩된 EnterNode 배열이 있는 Selection을 반환합니다.
실제 문서의 엘리먼트 타입으로 요소로 생성/변경/삭제하고, 이를 가리키는 Selection을 반환합니다.

실행 후 돔은 다음과 같이 변화됩니다.

이처럼 binding되는 data의 변화에 따라 svg 요소를 생성/변경/제거할 수 있습니다. d3가 왜 data-driven documents인지 알 수 있는 대목입니다.

간단한 네트워크 차트 그려보기

위에서 알아본 selections, data-join을 이용하여 간단한 네트워크 차트를 만들어봅시다.

nodes, links 데이터 정의

우선 네트워크 차트를 그리기 위해서는 각 노드와 간선의 정보가 필요합니다. 이 데이터들을 각각 다음과 같이 nodes, links 로 정의해보겠습니다.

let nodes = [
  { x:100, y:100, name:"ye" },
  { x:200, y:300, name:"jun" },
  { x:300, y:200, name:"mi" },
  { x:200, y:400, name:"sung" },
]

let links = [
  { source:"ye", target:"jun" },
  { source:"jun", target:"mi" },
  { source:"mi", target:"sung" },
  { source:"sung", target:"jun" },
]

links-nodes 매핑 전처리

그리고 각 link의 source, target을 다시 node로 매핑하는 전처리가 필요합니다.

links = links.map(link =>
    ({
      source: nodes[nodes.findIndex(node => link.source === node.name)], 
      target: nodes[nodes.findIndex(node => link.target === node.name)]
    })
  )

나중에 사용할 d3.forceSimulation() 의 nodes, links 데이터 구조와 mapping을 모방한 방식입니다. (솔직히 개인적으로는 이 방식이 좋은지는 잘 모르겠습니다. nodes가 Map 타입이었으면 이터러블하면서도 매핑이 더 효율적이었을 것 같고, links의 source, target type이 string -> node로 변경되는 부분때문에 ts에서 type 정의할 때 살짝 애를 먹었습니다. 처음부터 객체였으면 더 수월했을 것 같습니다.)

html container tag 정의

html쪽 태그에서는 svg와 그 내부에 link그룹, node그룹을 표현할 g tags를 정의합니다.

nodes draw

node는 g elements(text, circle을 그룹핑하기 위함)로 구성합니다.

const node = 
      d3.select("#node")
        .selectAll("g")
        .data(nodes)
        .join("g")
        .each(function(d) {
          d3.select(this)
            .append("circle")
            .attr("r", 5)
            .style("fill", "red");
          d3.select(this)
            .append("text")
            .text(d => d.name);
        })

function drawNodes(){
  node.attr("transform", d =>"translate("+[d.x, d.y]+")" );
}

여기서 주의할 점은 each내부 함수에서 this(각 그룹노드를 가리키는)를 사용하고 있기때문에, 이 내부함수를 화살표 함수가 아닌 함수 선언식으로 작성해야합니다.

selection.each 소스코드를 보면, callback함수에 각 node를 this로 바인딩해서 호출하는 구문을 확인할 수 있습니다.

// each.js
export default function(callback) {

  for (var groups = this._groups, j = 0, m = groups.length; j < m; ++j) {
    for (var group = groups[j], i = 0, n = group.length, node; i < n; ++i) {
      if (node = group[i]) callback.call(node, node.__data__, i, group);
    }
  }

  return this;
}

하지만 화살표 함수는 this를 가질 수 없기때문에, 자신을 둘러싼 scope의 this를 가리키게 됩니다. 그래서 call, bind, apply와 같이 this를 바인딩하는 methods도 이용할 수 없습니다.

links draw

links는 line elements로 구성합니다.

const link = 
      d3.select("#link")
        .selectAll("line")
        .data(links)
        .join("line")
        .attr("stroke", "black");

function drawLines() {
  link
    .attr("x1", d => d.source.x)
    .attr("y1", d => d.source.y)
    .attr("x2", d => d.target.x)
    .attr("y2", d => d.target.y)
}

실행구문

drawNodes();
drawLines();

코드 전문과 실행화면은 codepen을 통해서 확인 가능합니다. !codepen[yeynii/embed/dyjoMNZ?default-tab=js%2Cresult]

d3로 동적인 네트워크 차트 그리기 (1) - D3.js란?

Sun, 18 Dec 2022 13:22:06 GMT

굉장히 오랜만의 포스팅이네요. 그동안 놀았던건 아니고.. 부스트캠프 일정이 엄청 바빴던터라 못올리고 있었습니다....🥲

제가 부스트캠프 팀프로젝트로 했던 논문 인용관계 시각화 서비스입니다. 이제 자유의 몸이 되었으니, 위 프로젝트에서 논문 데이터를 어떻게 네트워크 차트로 시각화 했는지 그 과정들을 조금씩 기록해 보겠습니다.

D3.js란?

Data-driven-documents. 맞춤형의, 인터랙티브한 charts/maps를 웹에 그리기위해 사용되는 자바스크립트 라이브러리

특징

data-driven modification of HTML and SVG elements data 기반으로 html, svg element를 그려 낼 수 있습니다.
scale functions data values ⇒ visual values로 스케일링 하는 함수를 제공합니다.
loading and transforming data (e.g. CSV data) csv → js array convert 기능을 제공합니다.
helpers for generating complex charts such as treemaps, packed circles and networks treemaps, packed circles, network graphs and geographic maps 등의 복잡한 차트를 building 할 수 있는 block들을 제공합니다.
a powerful transition system for animating between different chart states chart states의 변화를 부드러운 애니매이션으로 표현할 수 있다. 요소가 어떻게 나타날지, 이동할지, 사라질지를 제어할 수 있는 강력하고 간편한 transition 기능을 제공합니다.
powerful user interaction support, including panning, zooming and dragging panning, zooming과 같은 상호작용 기능을 지원합니다.

D3를 사용한 이유

D3는 Chart.js나 Highcharts와 같이 이미 만들어진 차트를 제공하는 라이브러리가 아닌, 더 작은 단위의 블럭들을 조합시켜 커스텀 차트를 만드는 저수준 라이브러리입니다.
제가 만들고자 했던 네트워크 차트는 동적으로 데이터가 추가되고, 다양한 사용자 인터랙션이 필요했기에 세부적인 기능을 조절하기 위해서는 D3를 사용하는 것이 적합하다고 판단했습니다.
D3가 제공하는 메서드를 이용하면 그래프를 zooming, dragging하는 기능을 아주 쉽게 구현할 수 있습니다.

D3를 사용할때 주의해야 할 점

React 베이스에서 D3를 사용해야 했는데, 리액트 렌더링과 d3 렌더링이 같이 일어나면서 각자의 생명주기가 엉켜 사이드이펙트가 발생할 수 있습니다. 어느 시점에 d3에 렌더링을 위임할지, 어떤 state까지 리액트에서 관리할지 잘 고민해서 설계해야 합니다.
매번 네트워크 node와 line의 좌표를 계산하는데 시간이 많이 걸린다고 하는데, 이 계산로직을 어디서, 어떻게 처리할지에 대한 고민이 필요합니다.

다양한 방법이 있겠지만.. 저의 경우는 web-worker를 이용하여 서브스레드에서 node, line 좌표 계산 + 메인스레드에서 렌더링 하는 방식으로 계산로직/렌더링로직을 분리해서 병렬처리하는 방법으로 성능개선을 했습니다. 추후 포스팅에서 좀 더 자세히 다뤄보겠습니다.

svg, D3 찍어먹기

여기서 끝내기는 좀 아쉬워서.. 차트구현 내용은 아니지만, 제가 로딩스피너로 넣었던 위상이 변하는 달모양 spinner 만드는 과정을 알아보며 svg랑도 좀 친해질겸, D3를 찍먹 해봅시다.

svg 하위에서 사용한 태그들

추후 사용될 그래픽 객체를 저장해두는 태그
svg 영역을 채울 패턴을 정의하는 태그 달 표면 그림을 패턴으로 정의하기위해 사용
svg elements를 그룹화하는 태그
원을 그리는 태그
선을 그리는 태그 d 속성으로 선의 경로를 표현할 수 있습니다. 이 속성에 다양한 형태의 선을 정의하여 그릴 수 있는데, 저는 제가 사용한 두가지 속성 명령어에 대해서만 설명하겠습니다.
- M x y 좌표 x, y로 이동합니다.
- A rx ry x축 회전각 큰 호 플래그 쓸기 방향 플래그 x y 현재 좌표와 (x, y) 두 점을 지나면서 x축 반지름rx, y축 반지름ry, x축 회전각만큼 기울어진 타원호를 그리며 이동합니다. 이 때, 4가지 경우의 수가 생기는데, 이걸 특정해주는게 두개의 플래그입니다. 큰 호 플래그 - 0: 중심각이 180도 미만(작은 호) 1: 중심각이 180도 이상(큰 호) 쓸기 방향 플래그 - 0: 음각(반시계방향), 1: 양각(시계방향)

구현방법

어두운부분(원) ⇒ 밝은부분(반원 + 타원 or 반원 - 타원) ⇒ 달표면 레이어를 차례로 쌓은다음, path의 d 속성(밝은부분의 궤적)을 100ms마다 변경하는 방법으로 구현했습니다. 우선 달의 밝은부분을 그리기 위해서는 원호, 타원호 궤적 2개가 필요합니다.

원호, 타원호 두개와 쓸기방향 플래그를 잘 바꿔가면서 그려주면 되겠군요.

M x y A rx ry x-axis-rotation large-arc-flag sweep-flag x y A 안쪽타원 rx ry x-axis-rotation large-arc-flag sweep-flag x y

: 고정값들

접선좌표, 바깥쪽 원의 반지름, 안쪽타원의 ry는 고정값이고, 반원과 안쪽타원의 larg-arc-flag는 모두 0으로 고정이 가능합니다.(180도 궤적이니) 따라서, 반원의 sweep-flag, 안쪽타원의 rx, sweep-flag 세가지만 계산해주면 됩니다.

안쪽 타원의 rx 는 r * cos(t) (아래그림참고), 쓸기 방향 플래그만 🌑 -> 🌓 -> 🌕 -> 🌗 이 시점에 잘 바꿔서 그리면 됩니다.

그림실력이 이게 최선이네요... 저 두꺼운 선이 구의 입체면이라고 생각해주세요.

최종적으로, path를 계산하는 함수는 다음과 같이 만들어졌습니다.

const calculateMoonLightPath = (radian: number) => {
  return `M 50 0
            A 50 50 0 0 ${Math.floor(radian / Math.PI) % 2} 50 100
            A ${50 * Math.cos(radian)} 50 0 0 ${Math.floor((radian / Math.PI) * 2) % 2} 50 0`;
};

코드 전문

import * as d3 from 'd3';
import { useEffect, useRef } from 'react';
import styled from 'styled-components';
import theme from '../style/theme';

const calculateMoonLightPath = (radian: number) => {
  return `M 50 0
            A 50 50 0 0 ${Math.floor(radian / Math.PI) % 2} 50 100
            A ${50 * Math.cos(radian)} 50 0 0 ${Math.floor((radian / Math.PI) * 2) % 2} 50 0`;
};

const MoonLoader = () => {
  const pathRef = useRef(null);

  useEffect(() => {
    let radian = Math.PI;
    const timer = d3.interval(() => {
      d3.select(pathRef.current).attr('d', calculateMoonLightPath(radian));
      radian += Math.PI / 10;
    }, 100);
    return () => timer.stop();
  }, []);

  return (
    
      
    
  );
};

const MoonContainer = styled.div`
  text-align: center;
`;

export default MoonLoader;

d3.select(selector) selector가 string이면 해당 selector와 매칭되는 첫번째 element와 매칭되며, string이 아니면 파라미터 그 자체(여기서는 path 돔요소)와 매칭되는 Selection을 반환합니다.
Selection.attr("d", string) 선택요소의 d 속성을 변경합니다.
d3.interval(callback, delay) 주어진 delay시간마다 함수를 반복해서 실행합니다. callback : (elapsed) ⇒ void; delay : callback을 수행시킬 interval time.

참고) 달의 위상은 ← 방향으로 변해야합니다. 거꾸로 돌리지 않게 조심.... (이거 때문에 유튜브 중등과학 시청함)

위의 방법으로 리액트 + D3코드로 path를 100ms마다 변형시켰습니다

그럼.. 잘 돌아갑니다 ^^

네부캠에서 상을 받았습니다.

Tue, 06 Sep 2022 15:10:37 GMT

상이라고 하면 좀 거창하긴하지만... 부캠배 줌 배경화면 공모전에서 수상을 했습니다..ㅋㅋ 퀄리티로는 자신이 없었기 때문에 국뽕tv 컨셉으로 특별상 전형을 노려보았구요.. 영광스럽게도 받게 되었네요 원래 '실제상황' 옆에 '아님' <- 글자가 있는데 사진에서는 깨져서 안보이네요. 허위사실 유포죄로 잡혀간다면 삭제하겠습니다 부상이 따로 있는건 아니고 그냥 기분이가 좋다. 부캠 인스타에 박제될 수 있다 정도..? 그리고 몇몇분들이 웃어주셔서 행복했습니다. 그럼 이만 마저 슬기로운 부캠생활 보내고 오겠습니다. 아좌자 ~!

멤버십 1주일 후기 : 챌린지에 절여져서 그런가.. 생각보다 할만함 ~~그렇지만 다한건 아님~~

[JS] V8 엔진의 메모리 모델

Sun, 24 Jul 2022 07:25:08 GMT

V8 엔진의 메모리 모델

메모리 구조

V8 엔진의 메모리에서 실행되고 있는 프로그램을 Resident Set이라고 하며 크게 Heap memory와 Stack으로 나누어집니다.

Heap memory

참조형 데이터의 실체와 동적 데이터가 저장되는 장소입니다.

New space (Young generation) 최근에 만들어진 데이터가 저장되는 장소이며 Minor GC의 타겟이 됩니다. Old 영역에 비해 매우 작아 가비지 컬렉션이 매우 빈번하게 발생됩니다.
Old space (Old generation) New 영역에서 살아남은 객체들이 이동되는 곳입니다. 이후에는 Major GC에 의해 관리됩니다. Old pointer space(살아남은 객체들이 저장), Old data space(살아남은 리터럴이 저장) 부분으로 나눠집니다.
Large object space 다른 영역으로는 감당하지 못하는 매우 큰 객체들이 저장되어 있습니다. 가비지 컬렉터에 의해 이동되지 않습니다.
Code space 컴파일러의 의해 컴파일된 코드가 저장되는 장소입니다. 유일하게 실행가능한 데이터가 저장되어있으며, Large object space에 할당 될 수도 있습니다.

Stack

변수, 함수, 클래스, 함수 프레임과 같은 정적 데이터가 저장됩니다. 함수, 클래스는 미리 스택에 올려놓으며, 변수는 해당 스코프를 만날 때 스택에 올립니다. 스코프를 벗어나면 스택에 올라와있던 변수, 함수, 매개변수등을 해제합니다. 함수가 종료되어도 아직 외부에서 참조되고 있는 지역변수가 있다면 스택이 아닌 힙으로 이동되어 파기되지 않습니다. 이것이 클로저입니다.

메모리 관리

Minor GC (Scanvenger)
힙의 New 영역을 관리합니다. 작은 크기의 space를 매우 잦은 주기로 순회합니다. 두 작은 영역으로 나누어져 있고 From-영역, To-영역으로 부릅니다.
[동작 방식] 1️⃣ 새로운 데이터를 From-영역의 빈 공간에 할당하려고 시도합니다. 2️⃣ 할당할 수 없다면, 스케벤져를 실행시켜 살려야 할 데이터만 From-영역 → To-영역으로 이동시킵니다. (이 과정에서 To-영역이 자동으로 압축되어 단편화를 줄입니다.) 3️⃣ From-영역에 남아있는 데이터를 제거합니다. 4️⃣ 이제 To-영역을 From-영역처럼 사용합니다. 5️⃣ 두번의 Minor GC 과정에서 생존한 객체들은 Old 영역 으로 이동합니다.
Major GC 힙의 Old 영역를 관리합니다. Minor GC 보다 긴 주기로 동작합니다.
- 초기의 자바스크립트 : 참조 카운팅 방식을 사용했습니다. 누구도 참조하지 않는 데이터를 가비지로 취급합니다. 이 방식은 순환참조가 발생하는 데이터를 반환하지 못하는 취약점이 존재합니다. 이 경우 메모리 누수가 발생합니다.
- 최근의 자바스크립트 : Mark Sweep 방식을 채택하여 Mark - Sweep - Compact(디스크 조각 모음) 과정으로 메모리를 관리합니다. Root에서 닿을 수 없는 데이터를 가비지로 취급합니다. Root에서 닿을 수 있는 데이터만 Mark 하고 그 외에는 Sweep 하는 방식입니다.
  Mark : 힙 메모리를 방향 그래프로 간주해 DFS 방식으로 사용중인 객체를 식별합니다. Sweep : 가비지 컬렉터가 힙 메모리를 순회하면서 활성 상태로 표시되지 않은 객체들의 메모리 주소를 기록합니다. Compact : 단편화를 줄이기 위한 압축단계입니다.

네이버 부스트캠프 7기 합격했습니다!!!

Wed, 13 Jul 2022 12:22:36 GMT

부스트캠프 선발 과정에 대한 짧은후기 남깁니다. 자세한 내용은 두루뭉술하게 적는점 양해 바랍니다.

서류전형

여타 서류전형이 그렇듯이 주어진 몇 가지 문항에 답을 작성해야 하는데 저는 진정성을 강조했던 것 같습니다. 회사 다니는 거 현타왔던 날 잡고 새벽감성으로다가 구구절절 썼습니다. 솔직히 1년 전에는 적을 말이 없었는데, 5개월 독학 + 7개월 스타트업 굴러보니까 생기더라고요.

그리고 문항에서 언급한 내용을 증명할만한 자료가 있으면 제출하라고 하는데, 저는 그동안 노션에 스터디 정리해둔 거랑 블로그 같이 첨부했습니다. 첨부파일/링크 여부는 선택사항이라는데 솔직히 선발되려면 필수인 듯합니다. 그동안 했던 거 아무리 작은 거라도 쥐어짜 내서 제출하는 것을 추천해 드립니다.

1차 코딩테스트

빡 구현 + CS 였습니다.

2차 코딩테스트

빡!!!! 구현 이었습니다. 이정도 구현문제면 피지컬 싸움 아닌가 싶을정도로요. 혹시 내년에 지원하실 분들은 피지컬을 기릅시다 ...(?)

이제 시작이네요. 멤버십 전환을 목표로 불태워봅시다 야호!!!!

[백준] 11725 트리의 부모 찾기

Thu, 16 Jun 2022 12:19:27 GMT

문제링크 https://www.acmicpc.net/problem/11725

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

graph = list([] for _ in range(n+1))

for i in range(n-1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

rootNode = list([] for _ in range(n+1))
visited = [False] * (n + 1)
queue = deque([1])

while queue:
  current = queue.popleft()
  visited[current] = True
  for v in graph[current]:
    if not visited[v]:
      queue.append(v)
      rootNode[v] = current

for r in rootNode[2:]:
  print(r)

접근 방법 : BFS
시간 복잡도 : O(N)
배운점 밑의 제출에서는 input(), 위의 제출에서는 sys.stdin.readline()을 사용했는데, 시간이 10배 이상 차이가 났다. 파이썬의 input() 함수는 단순 입력뿐 아니라 1️⃣개행문자를 제거하고 2️⃣prompt message를 전달받아 출력하는 기능을 포함하고 있어 sys.stdin.readline()보다 시간이 더 오래걸린다고 한다. 그러니 여러줄의 입력을 받을 때는 반드시 input()대신 sys.stdin.readline() 을 사용하자.

[JS] webpack 에 유용한 plugin 설정하기

Mon, 13 Jun 2022 06:44:58 GMT

plugin

`html-webpack-plugin`

css 애셋, js파일을 포함한 html 파일을 생성합니다.

CSS 애셋과 엔트리 포인트에 명시된 script를 html에 자동으로 추가합니다. html 파일의 요소 안에서 css파일은 , js파일은