알고리즘
-
다익스트라 알고리즘은 이렇게 쓰는 게 맞다!알고리즘 2023. 8. 18. 02:22
최단 경로 알고리즘 문제를 풀기 위해, 처음 다익스트라 알고리즘을 공부하면서 너무 헷갈렸다. 개념 자체는 우선순위 큐를 사용한 BFS이기 때문에 하나도 어렵지 않다. 근데 왜 헷갈렸느냐? 인터넷에는 수많은 버전의 제각기 다른 다익스트라 알고리즘들이 있었다. 알고리즘 문제를 푼 사람들의 코드를 보면, 다들 다익스트라의 개념은 맞지만 조금씩 다르게 구현해서 쓰고 있었다. 그 중에는 쓸데없이 성능상 저하가 있는 코드도 있었고, 이런 특수한 케이스에서는 틀릴 것 같은데? 싶은 코드도 있었다. 따라서 나는 알고리즘 문제를 풀기에 가장 "적합한" 다익스트라 알고리즘의 코드를 만들었다. (내 머리에서 가장 적합하다고 생각한 것이기 때문에, 이보다 더 좋은 구현이 있을 수도 있지만) 다음 블록에 내 다익스트라 알고리즘..
-
C++ for vs for_each 반복문 속도 비교알고리즘 2023. 7. 25. 21:49
알고리즘 공부를 하면서, 보통 시간제한 1초 이하로 주어진 문제들은 반복문을 1억번 이하로 순회할 수 있다. 순서대로 순회하는 일이 필요할 때 보통 배열을 사용하게 되고, 배열을 순회할 때 C++11 이상부터는 다양한 방법을 제공한다. 그 중에는 내가 좋아하는 for_each 메쏘드도 있고, 간편한 문법을 제공하는 range-based for 문도 있다. 시간 복잡도는 코더의 역량으로 최대한 최적화 하면 되는 문제인데, 어떤 방법을 사용하여 배열을 순회할 때 최대한 시간적 이득을 볼 수 있을까? 3가지 배열 순회 방법의 속도 비교 이제부터 비교해보겠다. 전통적인 for 문 (for int i = 0; i < n; ++i) {} for_each 문 (arr.begin(), arr.end(), [](elem..