PS 했던 블로그

시간 초과를 받는 주 원인이 무엇일까요? 많은 초보들은 이에 대해 '코드가 너무 길어서 그렇지 않을까?' 하고 생각합니다. 하지만 실상은 반대인 경우가 더 많습니다. 알고리즘 문제 풀이에서 코드의 수행 시간을 결정하는 가장 큰 요인은 일반적으로 시간 복잡도이며, 시간 복잡도를 고려하여 작성하였다면 아무리 엄청나게 긴 코드를 작성하더라도 한 번 실행된 것만 가지고 웬만한 문제에서 시간을 초과시킬 일은 없습니다. 반면에 시간 복잡도를 고려하지 않고 오로지 답만 구할 수 있도록 코드를 짧게 줄인 코드는 시간을 초과할 가능성이 높습니다. 이와 관련하여 대표적으로 흔하게 하는 실수가 바로 라이브러리 함수의 시간 복잡도를 고려하지 않고 그 기능만을 목적으로 사용하는 것입니다. 아주 편리하지만 매우 비효율적인, 대표..

제목대로, 또는 큐에서 뺀 뒤에 '이미 방문한 정점인지'를 체크해야 합니다. 그러지 않으면 트리가 아닌 이상 대부분의 경우 시간 초과나 메모리 초과를 받게 됩니다. 그 이유는 다음과 같은 예시에서 확인해볼 수 있습니다. 미로 탐색 문제에 대해, 동일한 로직의 아래 C++과 Python 3 코드를 봅시다. [C++] #include using namespace std; string arr[105]; bool vis[105][105]; int dy[]{ 1, 0, -1, 0 }; int dx[]{ 0, 1, 0, -1 }; int main() { int n, m; cin >> n >> m; for (int i = 0; i > arr[i]; queue q; q.push({ 0, 0 ..

"같은 코드를 여러 번 냈는데 왜 실행 시간이 달라지나요?" 정상입니다. 프로그램의 실행 시간은 원래 일정하지 않기 때문입니다. 똑같이 프로그램을 실행한다고 해도 그 때의 컴퓨터의 상태가 완전히 같을 수는 없습니다. 메모리의 상태가 다르고, OS가 하고 있던 일이 다르고, 백그라운드 서비스들의 상태가 다르고, CPU의 온도가 다르기 때문입니다. 또한 실행 중에도 이 상태는 얼마든지 중간에 변할 수 있고, 이로 인해 같은 코드를 실행하더라도 프로그램이 눈에 띄게 더 빠르거나 느리게 동작할 수 있습니다. 기본적으로 시간이 오래 걸리는 코드라면 이 실행 시마다의 오차는 더 커지게 됩니다. 예를 들어 평균 300ms 정도가 걸리는 코드가 ±20ms 정도의 오차를 보인다면, 평균 3초가 걸리는 코드는 ±200ms..