[Menu DB structure + Algorithm] DP , DFS , get Menu Full path

export interface MenuListItem {
  id: number;
  name: string;
  root_yn: 'Y' | 'N';
  parent_id: number | null;
  sort_order: number;
  path: string | null;
  alias: string;
  use_yn: 'Y' | 'N';
  create_time: string;
}



기존 (while 루프)	DP (메모이제이션)	DFS (트리 탐색)
Time	O(n·d)	O(n)	O(n)
Space	O(d) per call	O(n) cache + O(d) stack	O(d) stack
방향	leaf → root	leaf → root (캐시)	root → leaf
n = 메뉴 수, d = 트리 깊이

기존 (while 루프)


export const buildMenuFullPaths = (menus: MenuListItem[]): Set<string> => {
  const menuMap = new Map<number, MenuListItem>();       // Space: O(n)
  menus.forEach((m) => menuMap.set(m.id, m));

  const getFullPath = (item: MenuListItem): string => {
    const segments: string[] = [];
    let current: MenuListItem | undefined = item;
    while (current) {                                    // Time: O(d) per call
      if (current.path) segments.unshift(current.path);
      current = current.parent_id ? menuMap.get(current.parent_id) : undefined;
    }
    return segments.join('');
  };

  const paths = new Set<string>();
  for (const menu of menus) {                            // Time: O(n) × O(d) = O(n·d)
    if (menu.use_yn === 'Y' && menu.path) {
      paths.add(getFullPath(menu));
    }
  }
  return paths;
};
DP (메모이제이션)


export const buildMenuFullPathsDP = (menus: MenuListItem[]): Set<string> => {
  const menuMap = new Map<number, MenuListItem>();       // Space: O(n)
  menus.forEach((m) => menuMap.set(m.id, m));

  const cache = new Map<number, string>();               // Space: O(n)

  const getFullPath = (item: MenuListItem): string => {
    if (cache.has(item.id)) return cache.get(item.id)!;  // Time: O(1) 히트

    const parentPath = item.parent_id
      ? getFullPath(menuMap.get(item.parent_id)!)         // Stack: O(d)
      : '';
    const fullPath = parentPath + (item.path ?? '');

    cache.set(item.id, fullPath);                        // 각 노드 1번만 계산
    return fullPath;
  };

  const paths = new Set<string>();
  for (const menu of menus) {                            // Time: 총 O(n)
    if (menu.use_yn === 'Y' && menu.path) {
      paths.add(getFullPath(menu));
    }
  }
  return paths;
};
DFS (트리 탐색)


export const buildMenuFullPathsDFS = (menus: MenuListItem[]): Set<string> => {
  const childrenMap = new Map<number | null, MenuListItem[]>(); // Space: O(n)
  for (const m of menus) {
    const key = m.parent_id;
    if (!childrenMap.has(key)) childrenMap.set(key, []);
    childrenMap.get(key)!.push(m);
  }

  const paths = new Set<string>();

  const dfs = (parentId: number | null, parentPath: string) => { // Stack: O(d)
    const children = childrenMap.get(parentId);
    if (!children) return;

    for (const child of children) {                      // 각 노드 정확히 1번 방문
      const currentPath = parentPath + (child.path ?? '');
      if (child.use_yn === 'Y' && child.path) {
        paths.add(currentPath);
      }
      dfs(child.id, currentPath);                        // Time: 총 O(n)
    }
  };

  dfs(null, '');
  return paths;
};

data 

[
    {
        "id": 22,
        "name": "내 계정 정보",
        "root_yn": "N",
        "parent_id": null,
        "sort_order": 1,
        "path": "/account/profile",
        "alias": "account_profile",
        "use_yn": "Y",
        "create_time": "2026-03-25T00:00:00"
    },
    {
        "id": 4,
        "name": "캐릭터 관리",
        "root_yn": "N",
        "parent_id": 1,
        "sort_order": 1,
        "path": null,
        "alias": "character_mgmt",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 21,
        "name": "서버 상태",
        "root_yn": "N",
        "parent_id": 20,
        "sort_order": 1,
        "path": "/system/server-status",
        "alias": "server_status",
        "use_yn": "Y",
        "create_time": "2026-03-25T00:00:00"
    },
    {
        "id": 7,
        "name": "캐릭터 조회",
        "root_yn": "N",
        "parent_id": 4,
        "sort_order": 1,
        "path": "/characters/search",
        "alias": "char_search",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 16,
        "name": "운영자 권한",
        "root_yn": "N",
        "parent_id": 2,
        "sort_order": 1,
        "path": "/admin/permission",
        "alias": "admin_auth",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 15,
        "name": "드랍 아이템",
        "root_yn": "N",
        "parent_id": 6,
        "sort_order": 1,
        "path": "/content/drop-table",
        "alias": "drop_table",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 1,
        "name": "인게임 관리",
        "root_yn": "Y",
        "parent_id": null,
        "sort_order": 1,
        "path": "/in-game",
        "alias": "ingame_root",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 11,
        "name": "퀘스트 설정",
        "root_yn": "N",
        "parent_id": 5,
        "sort_order": 1,
        "path": "/content/quest",
        "alias": "quest_config",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 12,
        "name": "NPC 데이터",
        "root_yn": "N",
        "parent_id": 5,
        "sort_order": 2,
        "path": "/content/npc",
        "alias": "npc_data",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 17,
        "name": "길드 데이터",
        "root_yn": "N",
        "parent_id": 2,
        "sort_order": 2,
        "path": "/community/guild",
        "alias": "guild_mgmt",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 8,
        "name": "스킬 밸런스",
        "root_yn": "N",
        "parent_id": 4,
        "sort_order": 2,
        "path": "/characters/skills",
        "alias": "skill_balance",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 5,
        "name": "월드 콘텐츠",
        "root_yn": "N",
        "parent_id": 1,
        "sort_order": 2,
        "path": null,
        "alias": "world_content",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 2,
        "name": "메타데이터",
        "root_yn": "Y",
        "parent_id": null,
        "sort_order": 2,
        "path": "/metadata",
        "alias": "meta_root",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 13,
        "name": "이벤트 트리거",
        "root_yn": "N",
        "parent_id": 5,
        "sort_order": 3,
        "path": "/content/event",
        "alias": "event_trigger",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 9,
        "name": "제재 내역",
        "root_yn": "N",
        "parent_id": 4,
        "sort_order": 3,
        "path": "/characters/ban-list",
        "alias": "ban_history",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 6,
        "name": "경제 시스템",
        "root_yn": "N",
        "parent_id": 1,
        "sort_order": 3,
        "path": null,
        "alias": "economy_system",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 18,
        "name": "아이템 도감",
        "root_yn": "N",
        "parent_id": 2,
        "sort_order": 3,
        "path": "/metadata/item-book",
        "alias": "item_dictionary",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 20,
        "name": "엔진 설정",
        "root_yn": "Y",
        "parent_id": null,
        "sort_order": 3,
        "path": "/engine/config",
        "alias": "engine_config",
        "use_yn": "Y",
        "create_time": "2026-03-25T00:00:00"
    },
    {
        "id": 10,
        "name": "보상 로그",
        "root_yn": "N",
        "parent_id": 4,
        "sort_order": 4,
        "path": "/characters/reward-log",
        "alias": "reward_log",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 14,
        "name": "던전 난이도",
        "root_yn": "N",
        "parent_id": 5,
        "sort_order": 4,
        "path": "/content/dungeon",
        "alias": "dungeon_difficulty",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    },
    {
        "id": 19,
        "name": "맵 리소스",
        "root_yn": "N",
        "parent_id": 2,
        "sort_order": 4,
        "path": "/metadata/map-asset",
        "alias": "map_resources",
        "use_yn": "Y",
        "create_time": "2026-03-16T16:56:21"
    }
]