매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다.
완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요.
며칠간 푼 문제 중에서 기억나는 문제는 두 개 밖에 없네요. 그래서 따로 안 적었습니다.
- 30878번: 약속 시간
- 기하적 확률로 접근하는 문제입니다.
- 중학교 때 수학 동아리에서 비슷한 문제를 어떤 선배가 발표했던 기억이 나는데, 그때는 적분을 몰라서 대충 이해 못하고 넘어갔던 걸로 기억합니다.
- 유명한 문제 중에는 뷔퐁의 바늘 문제였나? 그런 고전 수학 퍼즐들이 있는데 찾아보면 좋을 것 같습니다.
- 저는 그래프 그리고 적분해서 어케 식을 냈는데, 안 맞길래 상수를 좀 고치니까 나와서 믿음의 제출로 맞혔습니다.
- 30879번: 저녁 뭐 먹지?
- 버그를 못 잡아서 대회 중에 맞히지 못했습니다. 많이 아쉽습니다.
- SCC 템플릿의 문제라고 단정짓고 디버깅했지만, 문제가 거기가 아니었고 -i와 +i가 같은 SCC에 속하는지 확인하는 작업을 그냥 쭉 돌렸더니 -0와 +0 체크가 들어가버려서 문제가 되었던 겁니다.
- 아무튼, 꽤 좋은 경험이었던 게 2-SAT를 모르고 있었는데 AC-(버그×1)까지 다 짰다는 겁니다.
- 무향으로 논리에 대해 그래프 모델링으로 접근하는 문제들은 두세개 풀어봤었고, 이게 무향으로서 온전히 상태를 표현할 수 없다는 점에서 고민하니까 SCC를 써야되겠다는 식으로의 흐름은 자연스러웠던 것 같습니다.
- 다만 online SCC 같은게 있나, 하는 고민을 오래 했는데 생각해보니 Yes....Yes / No...No 꼴이라 이진 탐색으로 경계만 찾아주면 된다는 접근이 좀 늦어서 아쉬웠습니다.
Bytecomputer
- 열심히 고민을 해봤지만, AC 받을 확신이 드는 풀이가 안 나오길래 해설을 깠습니다.
- 읽어도 잘 모르겠어서 그냥 넘기기로 했습니다.
- 말씀중에 죄송하지만 이 문제 절대 P4 아닙니다
Perfect Quadrants
- 코딩이 전부인 문제.
- 코딩을 연습하기 위해 잡아보았습니다.
- 역시 코딩은 어렵습니다.
- 반열린 구간 / 디테일한 예외 처리 / 적절한 자료구조 ...
- 저는 세그트리를 갖고 잘 풀었네요.
- #좌표압축 & *p2..p1 정도를 잡고 연습해보는건 어떨까 싶은 생각이 듭니다.
