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

재귀(콜 스택) 대신 child / sibling / return 세 포인터로 트리를 순회한다 → 스택 없이 DFS pre-order, 언제든 중단·재개 가능. Fiber가 렌더링을 쪼갤 수 있는 이유.

재귀로 짜면 진행 상태가 JS 콜 스택에 쌓이는데, requestIdleCallback으로 도중에 yield하면 그 스택을 버리게 된다. 재개하려면 스택을 다시 쌓아야 해서 “어디까지 했는지”를 외부에서 들고 있어야 한다.

그 상태를 workInProgress 포인터 하나로 환원한다. 노드마다 걸린 세 링크를 직접 따라가므로 호출 스택이 필요 없다.

1. child 있으면?      → 내려간다
2. root에 도달했으면? → 종료
3. sibling 없으면?    → return(부모)으로 올라가며 반복
4. sibling 있으면?    → 옆으로 간다

내려가는 길 = beginWork, 올라오는 길 = completeWork. 한 노드를 두 번(하강·상승) 지나는 흐름이 그대로 두 단계로 갈린다.

---

• 참고: React Fiber Architecture — facebook/react#7942