0. 18년 2학기에 GPU 프로그래밍을 배워서, 이참에 kudeki-chain도 풀어봤습니다. GTX 1060으로, 약 16시간 정도 돌려서 풀었습니다. 최적화를 덜 했기 때문에 더 빨라질 여지가 있긴 합니다. sha1을 GPU로 옮기는 것이 꽤나 귀찮았는데, 코딩을 오랫만에 해서 그런지 실수가 꽤 많아 오래 걸렸던 것 같습니다. 제 개같은 틀린 코드를 디버깅해준 cubelover에게 감사의 말을 전하며 시작하겠습니다. 1. kudeki-chain 문제를 한 줄로 요약하면 다음과 같습니다. "sha1 해시값의 앞 n자리가 0이 되는 (커밋)메세지를 찾아라." n은 푼 사람이 생길수록 1씩 늘어나서, 제가 문제를 풀 때는 n이 11과 12였습니다. (현재 n이 12인 경우까지 해결하였기 때문에 n=12를..
0. 서론 실수 자료형을 사용하는 이진탐색은 오차때문에 틀릴 수 있습니다. 또한, 정확한 분수를 구해야 하는 문제의 경우는 실수 자료형을 쓸 수도 없습니다. 이런 경우 사용할 수 있는 방법으로는, 실수 대신 분수로 이진탐색을 하는 것입니다. (단, 분모의 상한이 확실하게 존재해야 합니다. 분모나 분자의 상한을 모른다면 답을 구할 수 없겠죠.) 증명은 정수론 학부과정에 포함되지만, 여기서는 다루지 않고 직관적으로 가능하다는 것으로 넘어가겠습니다. 실무에서는 딱히 중요하지 않을 것 같고, PS로도 자주 나오는 테크닉은 아닙니다. 그리고 코드도 실수 이진탐색보다 훨씬 더 길고 복잡합니다. 하지만 분수로 이진탐색이 된다는 것은 꽤 좋은 도구라고 생각하기 때문에 배우면 언젠가는 도움이 될 것 같습니다. 그리고, ..
0. 문제를 풀 때는 다른 문제로 바꿔서 푸는 경우가 많이 있습니다. 미로 최단거리를 그래프로 바꿔서 bfs로 푸는 것이 그 예시입니다. 하지만 문제를 바꿔서 풀 때는 조심해야 합니다. 문제를 바꾸는 과정에서 정보 손실이 일어날 수 있고, 일부 만족해야 하는 성질이 사라져 못푸는 문제가 되어버릴 수 있습니다. UCPC F 문제로 나온 parentheses recover의 풀이를 설명하면서, N^3 풀이와 N^2 풀이의 모델링에 나타나는 차이를 설명해 볼 것입니다. (스포 방지선) 1. 가능-불가능 여부 확인 문제를 풀기 위해서는 먼저 괄호 문자열 S, T가 주어졌을 때 조건을 만족하는지 알 수 있어야 합니다. (그리고 일반적으로 풀이를 이런 단순한 문제에서 시작하는 것은 매우 좋은 습관입니다.) 이 문제..