이분탐색의 종료조건과 경계조건, 즉 while문에 무엇이 들어가야 하는지, lo와 high를 각각 무슨 값으로 설정해야 하는지를 저를 포함해서 헷갈리시는 분들이 있는 거 같아서 한번 정리해 보려고 합니다.

본 글은 익명의 유저님께서 작성하신 글을 합의하에 제가 이어받아 옮긴 글입니다. 새롭게 바뀐 내용이 있으면 제가 지속적으로 업데이트해 나가겠습니다.

BOJ 작동 원리

채점 서버에는 한 쌍 이상의 입력 파일과 출력 파일이 있습니다.코드를 제출하면 그 코드에 입력 파일에 적힌 대로 입력하고 나타나는 출력을 출력 파일과 비교합니다. 모든 입력/출력 파일에 대해 코드가 문제 없이 올바른 출력을 내야 합니다. 여기서 "올바름"이란 것은 단순히 정답과 같은 값이 아니라 같은 출력을 의미합니다. 예를 들어 45.0을 출력해야 하는데 45나 45.00을 출력하면 오답입니다.

입출력 파일은 공개되지 않습니다. 예제는 데이터 중 극히 일부에 불과합니다. 예제는 자신의 코드가 맞을 것임을 확신하는 용도가 아니라, 입출력의 형식을 확인하고 문제의 설명을 검토하는 용도로 사용해야 합니다.

스페셜 저지가 있는 문제에는 출력이 올바른지 검사하는 채점 코드가 따로 있습니다. 그러므로 "올바른 출력"은 여러 가지가 될 수 있고, 그 중 하나만 출력하면 됩니다. 예를 들어 $10^{-2}$ 이하의 오차를 허용하는 문제라면 출력과 정답의 오차가 $10^{-2}$ 이하인지 검사하는 코드가 있습니다. 그런 문제에서 정답이 45.0이라면 45나 45.00을 출력해도 정답을 받을 수 있습니다.

• 구현을 어떻게 했는지 같은 건 채점 프로그램이 전혀 신경쓰지 않습니다. 그냥 답이 맞게 나오면 됩니다. 반대로, "틀렸습니다"가 나왔다는 건 무조건 답이 맞게 나오지 않는다는 뜻입니다.
• 줄바꿈이나 띄어쓰기 등을 마음대로 바꿔서 입력받으면 안 됩니다! 예제 형식 그대로 입력받으세요.
• 줄바꿈이나 띄어쓰기 등을 마음대로 바꿔서 출력해도 안 됩니다! 예제 형식 그대로 출력하세요. 예외적으로, (대부분의 문제에서) 각 줄의 맨 끝에 공백을 넣어도 되고 안 넣어도 되며, 출력의 맨 끝에 줄바꿈을 넣어도 되고 안 넣어도 됩니다. 맨 끝을 제외한 나머지 줄바꿈은 넣어야 합니다.
• 입력 조건을 코드에 넣을 필요는 없습니다. 예를 들어 "$3 \le N \le 5\,000$이다."라고 적혀 있으면, 이건 모든 입력 파일이 $3 \le N \le 5\,000$의 조건을 지킨다는 뜻입니다. 따라서 if (3 <= N && N <= 5000)와 같은 조건문을 넣어 별도로 검증을 하지 않으셔도 괜찮습니다.
• 입력을 다 받고 나서야 출력을 할 필요는 없습니다. 입력과 출력을 번갈아서 해도 됩니다. 근본적으로 입력 파일과 출력 파일은 분리되어 있습니다.

시간 제한은 각 파일마다 따로따로 적용됩니다. 즉 시간 제한이 1초면 첫 번째 파일에 1초, 두 번째 파일에 1초, ..., 마지막 파일에 1초 이내가 걸려야 합니다. 채점 현황에서 볼 수 있는 "시간"은 가장 오래 걸린 파일에서의 구동 시간을 나타냅니다.

메모리 제한도 마찬가지인데, 한 순간에라도 지정된 메모리를 초과하면 안 됩니다. 채점 현황에서 볼 수 있는 "메모리"는 최대 메모리 사용량을 나타냅니다.

언어에 따라 시간이나 메모리가 초과되고도 정답을 받을 수 있는데, 그 언어가 정해진 시간/메모리 보너스를 받기 때문입니다. https://www.acmicpc.net/help/language

"첫 줄에 테스트케이스의 개수 $T$가 주어진다." 또는 "입력은 여러 개의 테스트케이스로 이루어져 있다." 같은 문제는 그 $T$개의 테스트케이스가 한 파일에 들어있다는 뜻입니다. 그런데 시간과 메모리 제한은 각 파일마다 따로따로 적용된다고 했으므로 주어진 시간 안에 한 파일에 들어있는 모든 테스트케이스가 돌아가야 합니다.

• 시간 제한을 넘겼는데 맞았다고 뜬다면, 위의 "시간, 메모리 제한" 단락을 참조하세요.
• 틀렸습니다, 런타임 에러 등이 떠야 하는데 맞았다고 뜬다면, 입출력 데이터가 충분히 강력하지 않은 경우입니다. 게시판의 오타/오역/요청 카테고리에 틀려야 하는 제출 번호, 반례 데이터와 정답을 게시해 주세요.

• 그런 경우는 없습니다.
• 사실 아주 가끔씩은 있지만, 대부분은 그냥 착각입니다. 푼 사람이 많은 문제라면 특히 그렇습니다. 항상 자신의 잘못부터 의심하는 것이 바람직합니다.
• 정말로 문제가 의심되신다면, (1) 우선 해당 문제의 질문 게시판을 검색해서 잘못된 데이터가 제보된 적 있는지 확인해 보세요. 없다면, (2) 데이터의 범위를 assert문을 걸어서 확실하게 확인해 보세요. assert를 사용하지 않고 올라왔던 데이터 수정 요청은 대부분 잘못된 요청이었습니다. assert문을 걸었는데도 런타임 에러가 뜨지 않는다면 그냥 착각일 가능성이 높습니다.

너무 많아져서 아래 글로 분리했습니다. https://www.acmicpc.net/blog/view/70

Q. 파이썬으로 ○○○○번을 시간 내에 못 푸나요?

A. 파이썬이 원래 극도로 느리기 때문에 제대로 된 풀이로도 시간초과가 날 수 있습니다. 그럴 때는 PyPy로 제출하시면 웬만한 문제들은 풀 수 있습니다. 아주 어려운 문제라면 이것도 안 될 수도 있습니다.

하지만 반대로 언어 탓부터 하는 것도 바람직한 자세는 아닙니다. 알고 보니 시간 복잡도가 너무 커서 시간 초과일 수도 있고, 그 사실을 알아차리지 않은 채로 C++ 등으로 다시 짜다간 다시 시간 초과를 받고 코딩 시간을 낭비하게 됩니다. 항상 알고리즘의 논리부터 의심하는 것이 바람직합니다.

Q. 문제의 정답 비율은 어떻게 계산되나요?

A. https://www.acmicpc.net/problem/15595

Q. 문제 번호가 왜 1000부터 시작하나요?

A. https://www.acmicpc.net/board/view/86719

Q. 하스켈 언어의 지원 계획이 있나요?

A. 채점에 문제가 있어서 해결될 때까지 보류됩니다. 이 글(링크)과 이 글(링크)을 참조해 주세요.

Q. 번역은 어떻게 하나요?

A. 번역 기능이 있었으나, 오역의 문제가 많이 발생하여 중단되었습니다.

Q. 출제는 어떻게 하나요?

A. https://www.acmicpc.net/help/problem-add

추후 내용이 추가될 수 있습니다.

본 글은 익명의 유저님께서 작성하신 글을 합의하에 제가 이어받아 옮긴 글입니다. 새롭게 바뀐 내용이 있으면 제가 지속적으로 업데이트해 나가겠습니다.

원래는 BOJ 101 글에 있었던 내용인데, 쓸 내용이 너무 많아져서 독립된 글로 옮겼습니다.

• 예제는 데이터 중 극히 일부에 불과합니다. 자세한 것은 BOJ 101을 확인해 주시기 바랍니다. 예제는 자신의 코드가 맞을 것임을 확신하는 용도가 아니라, 입출력의 형식을 확인하고 문제의 설명을 검토하는 용도로 사용해야 합니다.
• 줄바꿈이나 띄어쓰기 등을 마음대로 바꿔서 입력받으면 안 되고, 마음대로 바꿔서 출력해도 안 됩니다. 반드시 주어진 형식 그대로 입력하고, 예제 출력에서 보이는 대로 출력해야 합니다.
• "n을 입력하세요" 같은 걸 출력하면 안 됩니다.
• ideone 등 온라인 컴파일러 사이트에서 여러분의 코드를 직접 돌려 볼 수 있습니다.

• 입출력이 느리면 그것때문에 시간초과가 날 수 있습니다. 이 문제(링크)를 풀어 봅시다.
• exit code가 0이 아니면 비정상적인 종료를 의미합니다. C/C++ main의 return 1, 여러 언어의 exit(1) 등으로 0이 아닌 exit code를 내면 런타임 에러입니다.
• float, double 등의 부동소수점 자료형은 나타내는 수의 범위가 넓지만, 그 범위 안에 있는 모든 수를 정확하게 나타낼 수 있는 게 절대 아닙니다. 범위도 넓은데 원하는 수를 다 표현할 수도 있고 int만큼이나 빠르기까지 하면 그건 상상의 세계에 있는 자료형이죠.
  • 같은 이유로, 부동소수점은 항상 오차를 조심해야 합니다. 가장 위험한 행동으로는 (1) 매우 작은 양수 (또는 절댓값이 매우 작은 음수)로 나누기, (2) 값이 거의 비슷한 두 수 중 어느 것이 더 큰지 판단하기, (3) 두 수가 같은지 판단하기, (4) 정수에 매우 가까운 수를 int로 바꾸기 등이 있습니다.
• '\b'는 하나의 문자일 뿐, 정말로 출력했던 문자를 도로 지우는 문자가 아닙니다. 단지 화면에 내보낼 때만 지운 것처럼 보이게 할 뿐입니다. 출력했던 문자는 지울 수 없습니다.
• 데이터의 끝에 '\n'가 들어오는 것이 원칙이지만, 꼭 지켜지는 사항은 아니며 오래된 데이터일 수록 지켜지지 않을 가능성이 높습니다. '\n'으로 입력의 끝을 검사하거나, 한 줄을 입력받고 마지막 글자를 지울 경우 문제가 생길 수 있습니다.
  • 비슷하게, 오래된 문제에는 데이터 각 줄의 끝에 공백이 하나씩 들어있을 수도 있습니다.
• 널 문자는 하나의 문자로 취급되며, 널 문자와 공백은 다릅니다. 일부 컴퓨터에서 널 문자를 출력할 때 빈 칸이 출력되는데, 실제로는 엄연히 공백과 다른 하나의 문자입니다. 그래서 널 문자를 출력하지 말아야 되는 데 / 공백을 출력해야 되는데 널 문자를 출력하면 오답입니다.
• "여러 개의 테스트케이스로 이루어져 있는" 문제에서는 각 테스트케이스마다 초기화를 합시다.
• 나눗셈에 음수가 들어갈 때 결과는 언어마다 다릅니다. C/C++처럼 0에 가까운 방향으로 반올림하는 경우도 있고, Python처럼 작아지는 방향으로 버림하는 경우도 있습니다. 마찬가지로, 언어에 따라 나머지 연산에서 음수가 나올 수도 있습니다.
• 자신이 짠 프로그램이 0-index를 사용하는지, 1-index를 사용하는지 확실하게 알도록 합시다.

• 가장 중요한 것은 직접 데이터를 만들어서 넣어 보는 것입니다. https://www.acmicpc.net/problem/14405 를 예로 들어 봅시다. 그러면 이런 입력들을 넣어 볼 수 있습니다.
  • 1. pi 하나만 넣으면? ka? chu? 한 글자만 넣으면? p? k? c? i? a? r?
  • 2. pika는 YES가 나와야 합니다. 이걸 조금 변형하면? pik? pia? pka? piak? pkia? ipka? kipa? pikaa? pikka? piika? ppika?
  • 3. kapi도 YES가 나와야 합니다. 이걸 조금 변형하면? kap? kai? api? kaip? kpai? kapii? kaapi?
  • 4. 주어진 예제를 조금 변형하면? pikap? pikpi? pipikach? pipikaphu?
  • 5. 그냥 정말로 아무거나 넣으면? abcd? pipichukachuka? pichaku? ppap? pikach?
• 입력으로 1 이상 1,000,000 이하의 정수 $N$이 주어진다면 $N = 1$, $N = 2$ 등의 최소 케이스가 잘 나오는지 확인하는 것이 좋습니다. 이런 입력이 특이 케이스가 되는 문제들이 종종 있고, 굳이 특이 케이스가 아니더라도 우리의 코드가 최소 케이스에서 틀릴 가능성은 얼마든지 있습니다. 위에서 언급한 "피카츄" 문제의 경우 p, k 등의 한 글자짜리 입력이 여기에 해당되겠죠.
  • $N = 1\,000\,000$ 같은 최대 케이스를 넣었을 때 주어진 시간 제한 안에 답이 나오는지도 확인해 볼 수 있습니다. 답이 맞는지 확인하는 건 어떨까요? 문제에 따라 답을 손으로 알아내기 힘들 수도 있는데, 적어도 말이 되는 값은 나와야겠죠? 출력이 무조건 0 이상일 수밖에 없는 문제에서 음수가 나오면 뭔가 잘못되었다는 뜻입니다.
• 매우 간단한 풀이가 있는데 시간복잡도가 너무 커서 못 쓰고, 그 대신 더 효율적인 풀이를 생각해야 하는 문제가 있습니다. 이런 문제는 다음 방법으로도 반례를 찾을 수 있습니다. 매우 간단한 풀이이면 구현하기 쉬워서 틀릴 가능성이 낮다는 점을 이용한 방법입니다.
  • 1. 매우 간단한 풀이를 작성한다.
  • 2. 랜덤으로 데이터를 만든다.
  • 3. 간단한 풀이와 틀린 풀이가 내놓는 답이 일치하는지 검사한다.
  • 4. 2-3번을 반복...
• PS에서의 런타임 에러와 디버깅 (링크)

• 배열 기반의 리스트 (C++ vector, string, Java ArrayList, String, Python list, str, ...)의 중간에 뭔가를 끼워넣거나 빼는 건 $\mathcal{O}(N)$입니다.
• 퀵소트를 직접 구현하면 $\mathcal{O}(N^2)$이 걸리는 데이터를 손쉽게 만들 수 있습니다. 그냥 내장된 정렬 함수를 쓰세요. 정렬을 직접 구현하는 것을 연습하시고자 한다면, 피벗을 랜덤으로 잡은 퀵소트를 구현하거나 힙소트, 머지소트 등 다른 $\mathcal{O}(N log N)$ 정렬 알고리즘을 구현하는 방법이 있습니다.
• 격자에서 탐색할 때 범위 체크를 반드시 합시다.
• DP를 할 때에는 메모이제이션을 합시다. 안 그러면 DP가 아닙니다.
• DFS는 절대로 최단거리를 구해 주지 않습니다. 물론 메모이제이션 없이 모든 경로를 탐색하는 DFS는 최단거리를 구해 주겠지만, 시간 초과가 날 것입니다.
• BFS는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다. BFS 문제에서 시간 초과나 메모리 초과가 나면 이것부터 의심해 보시면 됩니다.
• BFS를 할 때 큐의 크기가 제한되어 있도록 구현했다면, 그 크기는 적어도 방문할 수 있는 정점의 총 개수보다는 크게 합시다.
• 데이크스트라 알고리즘은 간선 가중치가 0 이상임을 가정합니다. 음수 간선이 있으면 답이 잘못 나오거나 지수 시간이 걸리게 됩니다. 음수 사이클이 없어도 마찬가지입니다.

• 오버플로우는 항상 조심합시다!!! 특히 "답을 $k$로 나눈 나머지를 출력한다." 종류의 문제에서 답을 통째로 다 구하고 $k$로 나누면 안 됩니다. 중간에 오버플로우가 날 수 있습니다.
• ios:sync_with_stdio(false);를 한 뒤에는 iostream과 stdio를 혼용하면 안 됩니다. iostream에 해당하는 것으로 cin, cout 등이 있고, stdio에 해당하는 것으로 printf, scanf, putchar, getchar, puts, gets 등이 있습니다.
• 지역 변수와 지역 배열은 초기화가 안 되어 있습니다.
• 전역 배열을 {1}이라고 초기화하면 첫 원소만 1이 되고 나머지는 그대로 0으로 남습니다.
• float는 너무 부정확해서 유의미한 사용이 사실상 불가능합니다. double을 씁시다.
• 위에서도 언급했지만 (음수) % (양수)는 양수가 아닙니다. 특히 A[(i - 1) % N] 같은 걸 하면 큰일납니다. 이럴 때는 (i + N - 1) % N을 하면 됩니다.
• char 배열에 길이 $N$의 문자열을 담으려면 널 문자까지 담아야 하므로 배열의 크기는 $N + 1$ 이상이어야 합니다.
• 전역배열의 크기는 넉넉하게 잡는 것을 추천드립니다. 예를 들어 "수열의 길이는 10만 이하이다."라고 해서 int A[100000]을 잡았는데 for (int i = 1; i <= 100000; i++)을 한다든지, "문자열의 길이는 10만 이하이다."라고 해서 char A[100000]을 잡았는데 널 문자때문에 사실 100001개가 필요하다든지... 그래서 [100055]처럼 실제 최대값보다 조금 많이 잡으면 인덱싱 오류가 날 가능성이 줄어듭니다.
• 채점 환경에서 포인터의 크기는 8바이트입니다. sizeof를 권장합니다.
• strlen은 $\mathcal{O}(N)$입니다. 따라서 for(int i = 0; i < strlen(s); i++)은 좋지 않습니다. s의 크기가 변하지 않는다면 strlen(s)를 미리 구해둔 다음 그 값으로 for 루프를 돌립시다.
• memset은 0과 -1만 가능합니다. https://www.acmicpc.net/board/view/23217#comment-40375
• strcmp는 -1, 0, 1이 아니라 음의 정수, 0, 양의 정수를 반환합니다.
• atoi에는 널 문자로 끝나는 문자열을 넘겨줘야지, char형 하나의 주소를 넘겨주면 안 됩니다. 참고로 숫자 c 하나를 int로 바꾸려면 c - '0'을 하면 됩니다.
• 반환형이 있는 함수를 짤 때에는 반드시 모든 분기점에서 무언가를 반환하도록 합시다. 특히 반환하지 않고 함수가 끝나는 것은 undefined behavior이며, 현재 BOJ의 컴파일러는 이 경우에 런타임 에러를 많이 띄우고 있습니다.
• range-based for는 C++11에서 추가된 기능입니다. C++98로 제출하면 안 됩니다.
• A[x] = x++;는 매우 위험합니다. 적어도 C++14까지는 undefined behavior였습니다. (C++17에서의 동작은 잘 아시는 분이 제보 바랍니다.)
• a <= b <= c는 (a <= b) <= c로 계산됩니다. "b가 a 이상, c 이하임"을 나타내려면 a <= b && b <= c라고 해야 합니다.
• scanf("%d", &a)를 했는데 EOF를 만나면 a가 0이나 EOF가 되는 게 아니라 저 함수 자체가 EOF를 반환합니다.
• fflush(stdin)은 표준이 아닙니다. rewind(stdin)도 표준이 아닙니다. fflush는 출력 스트림만 비울 수 있습니다.
• itoa는 표준이 아닙니다. 그 대신 sprintf를 쓰세요.

• 위의 C/C++ 내용 중 다수가 Java에도 해당됩니다.
• package boj; 같은 건 모두 지우고 제출해야 하며, 클래스 이름은 Main이어야 합니다.
• Scanner는 하나만 만드세요.
• LinkedList의 $x$번째 원소 찾기는 $\mathcal{O}(x)$입니다.
• Integer 등 wrapper class의 객체끼리는 == 으로 비교하면 안 되고 equals 메서드로 비교해야 합니다.
• 원인은 확실치 않지만 Scanner는 메모리를 많이 사용하는 것으로 보입니다. Scanner를 사용하는 것만으로도 메모리 초과가 발생할 수 있습니다. 이 문제(링크)에서 보았듯이 느린 입력이기도 하니, 가능하면 BufferedReader를 사용하는 것이 좋습니다.

• BOJ는 numpy 등 외장모듈을 지원하지 않습니다. (사실 모든 언어가 그렇습니다.)
• 풀이가 분명히 맞고 시간복잡도도 충분히 작은데 시간 초과가 난다면 언어를 PyPy로 설정하고 제출하면 됩니다. 파이썬은 원래 편리성과 속도를 맞바꾼 언어이기 때문에, 맞아야 될 풀이가 시간 초과더라도 이상할 게 전혀 없습니다.
• 두 수를 입력받고 나서 비교할 때는 반드시 int로 변환을 합시다. 문자열의 비교는 사전 순 비교이기 때문에, 3은 10보다 작지만 "3"은 "10"보다 큽니다.
• is 키워드는 두 대상의 값이 같은지가 아니라 완전히 같은 대상을 가리키는지를 비교합니다. BOJ에서 이걸 쓸 일은 거의 없습니다. 같은 "hello"더라도 따로 정의하면 다른 대상이 됩니다. 이걸 쓰면 디버깅하기도 힘든 게, -5 이상 255 이하의 int는 미리 만들어 놓고 정의할 때마다 가져다 쓰기 때문에, 딱 그 범위까지는 is와 ==가 똑같은 동작을 합니다. 그래서 손으로 반례를 찾으려고 하면 찾아지지 않습니다.
• list.pop(0), list.index, list.insert, list.count, x in list, list[:-1] 등은 다 $\mathcal{O}(N)$입니다. 이외에도 $\mathcal{O}(N)$이 걸리는 list 연산이 굉장히 많습니다. https://wiki.python.org/moin/TimeComplexity
• 위의 이유로, list를 큐 또는 덱으로 사용하면 절대, 절대, 절대, 절대, 절대 안 됩니다!! 반드시 collections.deque를 써야 합니다.
• 아니요, queue.Queue도 안 됩니다. 이건 멀티스레딩을 위해 만들어진 큐이고 매우 느립니다.
• 파이썬의 재귀 깊이는 기본적으로 최대 1,000입니다. sys.setrecursionlimit으로 이 깊이를 조절할 수 있습니다.
• 두 개의 int를 나누면 float이 됩니다. int(a / b) 말고 a // b를 써야 합니다. 맨 위의 "부동소수점 자료형은 나타내는 수의 범위가 넓지만 ..."을 읽어보세요.
• 문자열 s와 문자 c에 대해 s + c의 시간복잡도는 $\mathcal{O}(\mathrm{len}(S))$입니다. 예전에는 CPython에서 $\mathcal{O}(1)$였는데 특정 버전부터 느려진 것 같습니다. 자세한 정보를 찾는 대로 추가하겠습니다...

일반 Python에는 해당되지 않는 사항입니다.

• 사실 PyPy가 시간 초과더라도 이상할 건 없습니다. 쉬운 문제들은 거의 다 PyPy로 충분히 풀리지만, solved.ac 플래티넘 정도의 문제부터는 조금씩 위험해지기 시작합니다. 상황에 맞는 언어를 사용하도록 합시다.
• PyPy의 재귀 깊이는 파이썬과 달리 딱 정해 놓은 제한이 없습니다. 하지만 10만 단위로 너무 깊이 들어가면 스택 오버플로가 나고, 그 제한은 파이썬보다 낮습니다. 또한 PyPy는 재귀에 굉장히 약합니다.
• Decimal은 PyPy에서 더 느립니다.
• print가 sys.stdout.write보다 많은 메모리를 차지합니다. 구체적으로, print를 많이 사용할 수록 메모리도 많이 사용됩니다. 2020년 8월 9일 현재 Atcoder에서도 같은 현상이 나는 것으로 확인했습니다.
• sys.setrecursionlimit에서 설정해 놓은 재귀 깊이가 클 수록 메모리 사용량도 큽니다. 2020년 8월 9일 기준으로 Codeforces에서도 같은 현상이 나는 것으로 확인했습니다.

추가해야 할 내용을 제보받으면 추가하겠습니다.

안녕하세요. 단계별로 풀어보기 관리자 @jhnah917입니다. 최근 변경 내역과 이후 계획에 대해 안내해 드립니다.

• 컨벡스 헐 -> 기하 3
• MCMF -> 네트워크 플로우 2
• 더 어려운 수학 -> 수학 2

• 해 구성하기
• 인터랙티브와 투 스텝 1
• 유니온 파인드 2
• 스프라그 그런디 정리
• 트리와 쿼리
  • HLD, 센트로이드, 트리 압축
• 인터랙티브와 투 스텝 2
• 평방 분할
• 네트워크 플로우 3
  • 딜워스 정리, 게임 이론, 서큘레이션, Gomory-Hu 트리, 모델링 연습
• 네트워크 플로우 4
  • 일반적인 유량 알고리즘으로 해결할 수 없는 문제들
• 동적 계획법 최적화 2
  • 키타마사법, 히르쉬버그, 슬로프 트릭, 에일리언 트릭

자연수의 곱, 합성곱을 위한 FFT를 설명하는 다른 블로그를 찾아가 보면 보통 학부생 수준의 배경지식을 요구하거나 구현만 알려주는 곳이 많습니다. 자세하게 증명하는 한국어 글이 없어서 되게 힘들었는데, 여러분은 힘들게 찾아보지 않았으면 해서 글을 써 보았습니다.

이 글은 FFT의 구현이 아니라 DFT, FFT를 이해하는 데 초점을 둡니다. 코드에 대한 설명은 하지 않습니다.

증명을 이해하기 위해선 아래의 배경지식이 필요합니다.

• 오일러 공식
• 삼각함수 (일반각에 대한 성질)
• 등비수열의 합

---------미리 보기 방지-----------

---------미리 보기 방지-----------

---------미리 보기 방지-----------

가끔 "같은 프로그램을 Python 3 으로 제출하면 시간 초과를 받는데, Pypy3 으로 제출하면 맞았습니다를 받습니다. 왜 그런가요?" 같은 질문을 보게 됩니다. 이 글에서는 이런 종류의 질문에 대한 답변을 해 보려고 합니다.

Python 3 은 언어 명세입니다. 프로그램의 문법을 정의하고, 각각의 문장이 가진 의미 (= 문장을 실행하면 달라지는 변화)를 정합니다. 이렇게 Python 3 언어 명세를 정한 사람들은 그 언어 명세를 따르는 구현체 또한 제작하여 언어 명세와 같이 공개/배포합니다.

그 뒤, 몇몇 사람들은 배포된 Python 3 의 언어 명세를 이용하여 별도의 구현체를 만들기도 합니다. Pypy3 이나 IronPython, Jython 등이 여기에 해당합니다.

알고리즘 공부를 시작할 때 맨 처음 만나는 개념 중 시간, 공간 복잡도가 있습니다. 안타깝게도, 이는 오개념이 가장 많이 퍼진 주제이기도 합니다. 여러 오개념이 있지만 이 글에서는...

"빅-Ω 표기법은 최선의 경우를 다룰 때 사용한다. 빅-Ө 표기법은 평균의 경우를 다룰 때 사용한다. 빅-O 표기법은 최악의 경우를 다룰 때 사용한다."

...라는 오개념을 다룹니다. 이 주장은 각종 블로그 글은 물론, 이름 있는 출처에도 가끔씩 나오며 심지어 책으로도 나왔습니다.

1. 어둠의 아이콘

   백준 크래딧을 찾으면 된다.

2. 어둠의 초록색 입체 그리드

   solved.ac 테마를 뭘로 바꿔볼까?

3. 팽귄과 마작을

   1811?번을 풀면 얻을 수 있습니다! p.s 이 작성자는 얻는 방법은 알지만 어려워서 풀지 못했다. 그럼 어떻게 알았지? 그건 비밀!

https://www.acmicpc.net/problem/31442

에디토리얼과 결이 다른 풀이가 있어 공유합니다.

처음에 $1$이 $N$개이므로, 최소 $N - 1$번 작업을 수행해야 $N$이 만들어집니다. 한편 처음 $A$의 길이에서 작업의 가능한 횟수가 최대 $N - 1$번이므로, 작업을 정확히 $N - 1$번 하는 경우만 고려해도 됩니다. 그러면 문제에서 원하는 상황은 매 작업에서 $x, y \geq 1$, $z = 0$인 것과 동치임을 보일 수 있습니다.