알고리즘 검색 결과

해당 글 75건
백준 시철이가 사랑한 수식을 브루트 포스로 검수한 썰

어느덧 500번째 글입니다. 그냥 정보글은 시시하니, 대회 검수 썰을 풀어보도록 하겠습니다. SUAPC를 검수하면서 신경을 썼던 것 중 하나는, 대회에 출제된 20940번 문제였습니다. 대회에 출제된 문제 중에 난이도가 높은 그룹에 속할 것이라고 예상했고, 실제로 그렇게 되었습니다. 이 문제를 검수할 때 세웠던 원칙 중 하나는 브루트 포스로 검증을 해 볼만한 사이즈가 되면, 검증을 해 보자는 것이였습니다. 100만이면 모르겠지만, 50만이면 해 볼 만 했습니다. 잘 돌리면 1시간 정도에 해결을 할 수 있었기 때문입니다. 이 문제의 초기 조건은 N은 [1, 50만], K는 10^9+7이였습니다. 브루트 포스로 돌릴 만 합니다. 그런데, 이걸 그냥 브루트 포스로 돌리기에는? N이 대충 50만. 50만의 제곱..
알고리즘/ps 2021. 5. 21. 04:02
기하 문제를 다룰 때 잘 써먹게 되는 radian degree 변환을 알아봅시다.

가끔 기하 문제를 다루다 보면, 각도를 알아야 하는 경우가 있습니다. 혹은 주어진 각도를 가지고 무엇인가를 계산하거나. 그걸 하기 위해서는 라디안과 degree를 알아야 해요. 간단하게 알아보도록 하겠습니다. 먼저, python이나 java에서 제공되는 삼각 함수들에 대해 알아봅시다. cos을 예로 들어보겠습니다. 설명을 보시면, Params가 an angle, in radians로 되어 있습니다. 파이썬의 cos도 마찬가지입니다. measured in radians가 들어가 있습니다. 60을 Math.cos의 인자로 넣어봅시다. 그러면, -0.95241298041이 나오는데요. 우리가 알고 있는 cos60도는 0.5인데, 이것과 다른 수치가 나와 버립니다. 이는 Math.cos에 들어가는 것이 degr..
알고리즘/이론 2021. 5. 16. 02:15
왜 위상 정렬을 이용하면 그래프 사이클이 있는지 판단할 수 있을까요?

그래프에 사이클이 있는지 없는지 판단하는 방법 중 하나는 위상 정렬을 이용하는 것입니다. 어떻게 이용한다는 것일까요? 방향성이 있는 그래프에서, indegree가 0인 게 하나도 없다면 사이클이 있다고 판단합니다. 물론, indegree가 0인 노드가 있는데 사이클이 있는 경우도 있습니다만, 이건 글의 말미에 잠깐 다루겠습니다. 먼저, 아래와 같이 조건을 제한해 보겠습니다. 방향성이 있는 그래프에서 아래 조건이 성립합니다. 이 경우, indegree 값이 0인 노드가 존재하지 않는 그래프에 대해서 판단하는 것 보다는 조금이나마 더 쉽습니다. 사이클이란, i에서 i로 가는 경로를 의미합니다. 제한된 조건을 만족하는 노드 갯수가 n인 그래프를 생각해 봅시다. 일단 indegree 값이 1이므로, 나가는 것이..
알고리즘/ps 2021. 5. 3. 06:45
트리 dp : 스크루지 민호 문제로 간단한 것만 풀어 봅시다.

tree dp는 최근에 코테에 나왔습니다. 그래서 트리 dp 2 문제를 준비해 보았습니다. 스크루지 민호 시리즈는 이들을 연습하기 좋은 셋트이기 때문입니다. 트리 탐색이나, dfs에 대한 기본적인 이해가 있다고 가정하고 진행하겠습니다. 먼저, 이 문제부터 보겠습니다. 왜 1부터 안 푸냐. 사실 해당 방법으로 풀기는 2가 1보다는 쉽기 때문입니다. 트리가 이렇게 있어요. 문제 조건을 잘 보시면, 양방향 간선에 연결되어 있는 도시 2개 중에 최소 하나 이상은 경찰서가 있어야 함을 알 수 있어요. 그러면 현재 cur에 경찰서를 세운 경우와 그렇지 않은 경우로 나눌 수 있음을 알 수 있어요. 먼저, cur에 경찰서를 세우지 않은 경우를 생각해 봅시다. 그러면, 자식 도시들은 모두 경찰서를 세워야 합니다. 만약에..
알고리즘/ps 2021. 4. 25. 20:24
백준 배열 돌리기 5 : 전략적인 브루트 포스로 풀어봅시다.

배열 돌리기 5는 solved 난이도로 골드 1인 문제입니다. 200만개의 쿼리를 브루트 포스하게 실행시키면, 시간초과가 나는 것은 당연해 보입니다. 높이가 100, 너비가 100인 배열을 어떻게 압축을 시키면 좋을까요? 문제가 되는 것은 5번, 6번임을 알 수 있습니다. 가로로 반, 세로로 반을 나눠서 처리해야 하기 때문입니다. 사실 그것만 없었다면, 그냥 시점만 이동해서 풀 수 있었을 겁니다. 일단, 제 풀이는 브루트 포스입니다. 그런데, 100 by 100 전체를 브루트 포스를 하지 않습니다. 데이터를 압축하는 것이 목표입니다. 어떻게 잘 압축을 할까요? 배열 S가 아래와 같이 있다고 해 보겠습니다. 5, 6번 연산 때문에 이렇게 나누었다는 것을 눈치채셨을 겁니다. 이 4개의 영역 중에, 모서리 부..
알고리즘/ps 2021. 4. 4. 03:29