DFS (깊이 우선 탐색)

// 재귀 방식
function dfs(graph, node, visited = new Set()) {
  visited.add(node)
  console.log(node)
  graph[node].forEach((neighbor) => {
    if (!visited.has(neighbor)) dfs(graph, neighbor, visited)
  })
}

// 스택 방식
function dfsStack(graph, startNode) {
  const stack = [startNode]
  const visited = new Set()

  while (stack.length > 0) {
    const node = stack.pop()

    if (!visited.has(node)) {
      console.log(node)
      visited.add(node)
      graph[node]
        .slice()
        .reverse()
        .forEach((neighbor) => {
          if (!visited.has(neighbor)) stack.push(neighbor)
        })
    }
  }
}

const graph = {
  0: [1, 2],
  1: [0, 3, 4],
  2: [0, 5],
  3: [1],
  4: [1],
  5: [2],
}
dfs(graph, 0) // 0, 1, 3, 4, 2, 5

캘린더 이벤트 겹침 처리 알고리즘

겹치는 이벤트들을 나란히 배치하기 위한 레인 할당: 시작 순으로 보며 비어 있는 가장 낮은 레인에 넣으면, 레인 수가 동시에 겹치는 최대 개수와 같아진다(구간 그래프의 탐욕 색칠).¹

interface Event {
  id: string
  start: number
  end: number
}
interface PositionedEvent extends Event {
  lane: number
  totalLanes: number
}

function calculatePositions(events: Event[]): PositionedEvent[] {
  // 1. 시작 시간 순 정렬
  const sorted = [...events].sort((a, b) => a.start - b.start || a.end - b.end)

  // 2. 겹침 그룹 찾기 + 레인 할당
  const result: PositionedEvent[] = []
  let group: Event[] = []
  let groupEnd = 0

  sorted.forEach((event) => {
    if (group.length === 0 || event.start < groupEnd) {
      group.push(event)
      groupEnd = Math.max(groupEnd, event.end)
    } else {
      processGroup(group, result)
      group = [event]
      groupEnd = event.end
    }
  })
  if (group.length) processGroup(group, result)

  return result
}

function processGroup(group: Event[], result: PositionedEvent[]) {
  const activeLanes: number[] = []

  group.forEach((event) => {
    // 사용 가능한 가장 낮은 레인 찾기
    let lane = activeLanes.findIndex((end) => end <= event.start)
    if (lane === -1) lane = activeLanes.length

    activeLanes[lane] = event.end
    result.push({ ...event, lane, totalLanes: 0 })
  })

  // totalLanes 업데이트
  const maxLane =
    Math.max(...result.slice(-group.length).map((e) => e.lane)) + 1
  result.slice(-group.length).forEach((e) => (e.totalLanes = maxLane))
}

// CSS 적용: left = lane/totalLanes * 100%, width = 100%/totalLanes

• FullCalendar
• Interval Scheduling

---

Footnotes

1. Interval graph - Wikipedia: “An optimal graph coloring of the interval graph represents an assignment of resources that covers all of the requests with as few resources as possible; it can be found in polynomial time by a greedy coloring algorithm that colors the intervals in sorted order by their left endpoints.” ↩

---

• 참고: Fiber Principles: Contributing To Fiber — react/react#7942¹

Footnotes

1. “Nothing in Fiber uses the normal JS stack.” / 스택을 다시 쌓는 비용보다 중단이 문제다 — “…we would spend some time unwinding and rebuilding the stack each time. It is not too bad. However, everything along the stack would have to be aware of how to “unwind” when we abort in the middle of the work flow.“ 다만 원문도 Fiber 사정이라고 못박는다 — ”…a few unique design patterns that apply to Fiber, but not necessarily anything else.“ ↩