PS 했던 블로그

메모이제이션은 계산 결과가 될 수 없는 값으로 해야 합니다.

재귀로 작성한 다이나믹 프로그래밍에서 한 번 계산한 결과를 기록해 두고 같은 상태에 재방문했을 때 재계산을 하지 않고 기록해 둔 값을 바로 반환하는 메모이제이션은 필수적인 기법 중 하나입니다. 여기에서 중요한 것은 코드가 이미 계산했던 결과인지 여부를 판단할 수 있어야 한다는 것입니다. 이 말만 들으면 별로 특별할 것이 없어 보이는데, 실제로 재귀 DP에서 이 부분은 매우 자주 실수하고 시간 초과를 받게 되는 원인입니다. 예를 들어 11048 - 이동하기 문제에서 다음과 같은 코드를 작성할 수 있습니다.#include using namespace std;int n, m;int a[1005][1005];int dp[1005][1005];int f(int r, int c){ int &ret = dp[r..

참고: 도움이 필요한 당신에게BOJ에서 틀린 코드에 대한 도움을 받고 싶을 때 기준입니다. 이런 글이 길어지면 읽기 피곤하니, 짧게 가겠습니다.질문을 올리기 전에조금만 더 고민해 보세요. 디버깅 과정도 엄연히 문제 풀이 과정의 일부이고, 아주 중요한 능력입니다. 오답을 받자마자 고민 없이 곧바로 질문글을 작성하는 것이 습관이 되면 결국 디버깅 능력은 기를 수가 없습니다.예제들을 다시 한 번 넣어보세요. 반례는 보통 멀리 있지 않습니다. 한 글자 수정할 때마다 예제가 나오는지 여부가 매번 바뀌는 건 매우 자연스러운 현상이기 때문에, 다른 곳에서 반례를 찾기 전에 예제를 일단 전부 다시 넣어보는 것이 좋습니다.질문 게시판을 먼저 확인해 보세요. 푼 사람이 많은 문제들의 경우 질문 게시판에 이미 수백 개의 글..

이번 글에는 조금 다른 주제를 가져와 보았습니다. 몇 번에 걸쳐 Codeforces에 관련된 글들을 써보려고 하고, 이 글은 그 중 첫 번째입니다. Rated 라운드의 종류Rated 라운드는 참가자들의 레이팅에 변동을 주는 라운드로, 라운드 종류마다 이 영향을 받는 참가자들의 레이팅 범위가 다릅니다. 실력 수준에 적절하게 맞추어 구성된 문제 셋에서만 경쟁을 하도록 디비전이 여럿으로 나뉘어 있습니다. 우선 전체 목록을 정리하면 다음과 같습니다.DivisionRatedFormatTrusted Participant문제 수비고Div. 1 + Div. 2전원일반 8-9일반적으로 스폰서 라운드Div. 1>= 1900일반 5-7Div. 2와 동시 개최Div. 2 (with Div. 1)일반 5-7Div. 1과 동시 ..

BOJ에서는 몇 년 전에 아주 편리한 기능을 업데이트했습니다. 바로 런타임 에러의 이유를 찾아주는 기능입니다. 모든 종류의 에러를 다 잡아주지는 못하지만, 흔하게 발생하는 많은 종류의 에러들을, 인터프리터 언어의 예외는 바로 잡아주고, 컴파일 언어의 에러는 디버깅 기능을 이용하여 최대한 에러의 원인을 찾아주는 방향으로 동작합니다. (물론, undefined behavior는 디버거조차도 속일 수 있습니다!) 런타임 에러가 발생했을 때 '런타임 에러'라고 쓰인 곳을 클릭하면 도움말 페이지로 이동하는데, 이곳에서 각 에러 종류에 대한 설명과 발생하는 주 원인들을 볼 수 있습니다. 자료가 풍부하지는 않지만, 적어도 초보들이 흔히 실수하는 부분에 대한 설명은 웬만하면 찾을 수 있는 정도는 됩니다. 런타임 에러의..

이 글은 질문보다는 수정 요청글로 자주 보는 내용에 대한 매크로(?) 답변용입니다. 문제들 중에는 다음과 같은 조건을 가진 것이 많습니다. 입력으로 그래프가 주어지는데, 정점의 개수가 $1 \le N \le 100,000$개, 간선의 개수가 $1 \le M \le 200,000$개이고, 간선의 양 끝점은 서로 다르며 중복된 간선이 없다고 합니다. 그런데 여기서 의문이 듭니다. 정점의 개수가 1개 이상이라고 하는데, 정점이 1개이면 간선은 하나도 못 주어지지 않나요? 그렇다면 정점도 1개 이상이고 간선도 1개 이상이라는 조건이 잘못된 것 아닌가요? 하지만 조건은 이렇게 따로 따로 분리해놓고 생각해야 하는 것이 아닙니다. 다음과 같은 예시를 보겠습니다. "입력으로 $1$ 이상 $1,000,000$ 이하의 정..

알고리즘 문제는 일반적으로 어떠한 입력이 주어졌을 때, 그에 대한 올바른 정답을 출력하는 것으로 구성됩니다. 대부분의 문제에는 이러한 입력이 어떤 형식으로 주어지고 출력 형식이 어떻게 되어야 하는지에 대한 힌트를 주기 위해, 그리고 문제 이해를 돕고 몇 가지의 간단한 테스트를 해볼 수 있도록 하나 이상의 예제를 제공합니다. 여기서 중요한 부분이 있습니다. 굵은 글씨로 강조한 것처럼, 예제는 언제까지나 문제 풀이에 대한 힌트를 주고 몇 가지의 간단한 테스트용 예시를 제공할 뿐, 절대로 이들을 통과하기 위한 코드를 작성하라는 의미로 주는 것이 아닙니다. 그러면 문제를 풀 때에는 어디를 목표로 봐야 할까요? 바로 문제의 조건입니다. 문제의 조건이라는 것은 시간/메모리 제한, 주어지는 수의 최소/최대 범위, 문..

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

제목대로, 또는 큐에서 뺀 뒤에 '이미 방문한 정점인지'를 체크해야 합니다. 그러지 않으면 트리가 아닌 이상 대부분의 경우 시간 초과나 메모리 초과를 받게 됩니다. 그 이유는 다음과 같은 예시에서 확인해볼 수 있습니다. 미로 탐색 문제에 대해, 동일한 로직의 아래 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..

1. 입력과 출력의 순서는 상관이 없습니다. 문제를 풀 때에는 오로지 출력한 전체 내용이 정답과 같기만 하면 됩니다. 여러 테스트 케이스 각각에 대해 답을 출력하는 문제라고 하더라도 반드시 한 케이스를 입력받은 후 답을 출력하고 다음 케이스를 입력받아야 하는 것은 아닙니다. 모든 케이스를 전부 입력받고 답을 나중에 몰아서 출력해도 상관 없고, 입력을 받던 도중에 답을 출력해도 되고, 입력을 받기 전에 답을 출력해도 되며 (답을 알 수 있다면), 입력을 아예 안 받고 답을 출력해도 됩니다. 2. 입력과 출력이 화면에 섞여나와도 문제 없습니다. 보통 프로그램을 테스트할 때에는 콘솔에서 실행하고, 이 콘솔 화면에서 입력과 출력이 함께 이루어지기 때문에 섞여나오는 것이 정답에 영향을 주지 않을까 걱정하는 분들도..