개발/자료구조1 Javascript로 큐 Queue 구현하기 서론 큐는 선입선출인 자료구조로 원소를 넣고(enqueue) 빼는(dequeue) 동작을 O(1)의 시간복잡도로 수행할 수 있습니다. javascript의 Array 자료구조를 사용하면 큐에 원소를 넣고 빼는 동작을 수행할 수 있습니다. push 메서드를 통해 원소를 맨 뒤에 넣을 수 있고 shift 메서드를 통해 맨 앞의 원소를 뺄 수 있습니다. 하지만 shift 메서드는 O(1)의 시간복잡도로 수행되지 않습니다. (이유를 자세히 찾아보지는 않았지만 맨 앞의 원소를 뺀 후에 나머지 원소들을 한칸씩 땡겨오는 작업이 필요해서 라고 추측됩니다.) 그래서 큐가 필요한 알고리즘 문제를 풀 때 Array를 사용하면 시간초과가 나거나 오래걸리는 것을 볼 수 있습니다. 배열에 10만개의 원소를 넣고 빼는 간단한 테스.. 2022. 9. 28. 이전 1 다음
