Javascript에서 그래프 탐색 시간을 최소화 하는 방법은 어떤게 있을까요?

Question

오늘 아침에 코딩테스트를 응시하고 왔습니다.무난한 그래프 문제였고, 늘 풀던대로 풀어서 정확성은 100점을 기록했으나효율성을 절반 이상 날려먹어버려 만점 획득에 실패하고 말았습니다....문제는 디렉터리 절대 경로의 길이 중 가장 긴 것을 구하는 문제였습니다. 단방향 그래프의 가중치의 합의 최대를 구하는 문제와 같은 맥락으로 보시면 될 것 같습니다.심지어 한 노드는 하나의 부모 노드/자식 노드를 가져서 난이도도 낮은 편이었습니다.다만 노드의 개수가 2에서 10만으로 꽤 컸고, 가중치가 string으로 주어져 (디렉터리 이름) 아마 시간 복잡도가 매우 빡빡했을것이라 생각합니다.제가 시도했던 방법들은BFS - 시간초과DFS (재귀) - 런타임 에러(Maximum call stack으로 추정됩니다)DFS (스택) - 시간초과DP - 실패이정도인데, 노드 개수가 많아 반복을 많이 해야 할 때 시간초과가 발생했을 것으로 짐작하고 있습니다.(한쪽에는 가중치가 1인 노드가 99999개, 다른 쪽에는 가중치가 100000인 노드가 1개 있는 구조 등)시간 초과를 잡기 위해서도 다양한 방법을 적용해 봤습니다.queue, stack에서 아이템을 가져올 때, shift(), pop() 대신 index를 증가시키는 방법 사용const queue = [start]; //기존에 사용하던 방식 while(queue.length > 0) { const node = queue.shift(); } //시도한 방식 let idx = 0; while(queue.length > idx){ const node = queue[idx++]; }안타깝게도 20~30ms 정도의 시간 단축 효과는 있었지만 시간 초과는 여전했습니다.가중치(string)을 length로 변환시켜 연산을 줄임 -> 큰 성능 개선은 없었습니다//기존 방식 const costs = ['abcd', 'efg', 'hijk']; //시도한 방식 const costs = ['abcd', 'efg', 'hijk'].map(str => str.length);그래프의 연결 관계를 배열이 아닌 객체(map) 형태로 저장const n = 5 const relation = [[1,2], [2,3], [1,4], [2, 5]] //기존 방식 const graph = Array.from({length: n + 1}, () => []) for(let [p, c] of relation){ graph[p].push(c) } //시도한 방식 const graph ={} for(let [p, c] of relation){ if(!graph[p]) graph[p] = [] graph[p].push(c) }역시나 10~20ms 정도의 성능 개선은 있었지만 문제 해결에는 큰 도움이 되진 않았습니다.결국 시간 초과를 잡지 못한 채로 코딩테스트는 끝났지만, 나중에 또 어딘가에서 쓰일 수도 있고, 저를 고민하게 했던 이 문제에 대해서 깊게 탐구해보고 싶어 질문을 올려봅니다!여러 의견 및 조언 해주시면 감사하겠습니다!!!

캐티 · Answer

수학적으로 먼가 잘못되었지 않았겠나요. 아무 알고리즘이나 넣어보는 것도 방법이겠지만 정확한 계산 결과가 일반적으로 좋겠쩌. 주어진 문제를 알아낸다면 적절한 알고리즘을 구현할 수 있을 것이어요.

DaSA · Answer

노드가 10만이면 일반적인 그래프탐색으로는 실패하라고 의도한거같은데요단순 BFS,DFS 문제가 아닌걸로 느껴집니다해서 자료형 메서드 차이로 인한 실패는 아닌것 같습니다 다만JS에서 배열은 deque라서 shift()보다는 pop()이 훨씬 빠릅니다 stack 연산이라

Javascript에서 그래프 탐색 시간을 최소화 하는 방법은 어떤게 있을까요?

2개의 답변

Q&A 목록