재원블로그 재원블로그

이 문제는 다이나믹 프로그래밍으로 풀었다. 이 문제는 싱글, 더블, 트리플, 불 네 가지의 점수를 파악하고 그 중 겹치는 것이 있으면 싱글, 불로 카운팅하는 것이 중요하다. 2의 경우 2 싱글일 수도 있지만, 1 더블일 수도 있다. 이 경우 2 싱글로 판단하도록 하는 것이다. 시간 복잡도의 경우 100,000 * 43 = 4,300,000 이므로 충분히 1초 안에 풀 수 있다. 다이나믹 프로그래밍에서 바텀업 방식이 탑다운 방식보다 확실히 빠른 것 같다. 또한 가끔 바텀업으로 생각하는게 더 쉬운 경우도 있었다. dp 문제를 풀 때 항상 탑다운으로 생각했는데, 바텀업으로도 생각해봐야할 것 같다. #include #include #include #include using namespace std; #defin..

이 문제는 dfs를 이용해서 풀었다. 이 문제에서 가장 핵심은 해당 그래프가 트리라는 것이다. 하나는 +1, 하나는 -1 이라는 것은 -1되는 쪽에서 +1되는 쪽으로 1을 준다라고 생각하면 쉽게 문제가 풀린다. 주의할 점은 단순히 a를 순회하면서 합이 0이 되지 않았다고 바로 -1을 리턴하는 경우 정답이 나오지 않는다는 것이다. dfs 결과를 통해 총 합이 0이 되지 않을 때 -1을 리턴해야 정답이 나온다. #include #include #include #include #include #include using namespace std; #define NODE_MAX 300000 #define INF 10000000000000000ll typedef long long LL; vector edges[NO..

이 문제는 다이나믹 프로그래밍을 이용해서 풀었다. 처음에는 다익스트라를 이용해서 문제를 풀었다. 다 맞혔으나 효율성 3번만 계속 시간 초과가 나왔다. 아직도 이유는 잘 모르겠다.. #include #include #include #include using namespace std; #define MAX 500 #define INF 1000000000 int dist[MAX + 1][MAX + 1]; vector problems; int maxAlgo = -1; int maxCoding = -1; void init() { for (int y = 0; y = maxAlgo && coding >= maxCoding) { return presentCost; } // increase algo if (algo < ..

이 문제는 수학, map을 이용해서 풀었다. 최대 1,000개의 line 중 2개를 선택하므로 10C2 = 499,500 번의 연산으로 짝을 지어줄 수 있다. 각 짝에 대해서 Ax + By + E = 0, Cx + Dy + F = 0 에 대한 교점 수식이 주어진다. 여기서 핵심은 어떻게 정수가 아닌 소수인지를 판단하는 것인데, 나는 나누어떨어지지 않으면 소수라고 판정하는 방식으로 구현했다. calculate() 는 연산만 수행하므로 O(1) 이기 때문에 시간 안에 풀 수 있다. 그러나 주의할 점은 NO_MEET로 놓은 숫자가 생각보다 많이 커야 한다는 것이다. 1e15 정도로 커야 문제가 풀리게 된다. 또한 int 자료형으로는 100,000 * 100,000 = 100억의 숫자를 담을 수 없으므로 lon..

이 문제는 이분 탐색을 이용해서 풀었다. 이 문제를 어렵게 만드는 요인은 마지막 작업이 들어가는 코어의 번호를 찾는 것이다. 일단 n이 core의 size보다 작거나 같으면 0시간 후일 때, 즉 아직 시작하지 않았을 때 코어에 모두 들어가게 되므로 base case에 해당한다. n이 core의 size보다 클 때부터 문제가 시작된다. 우선 처음에 모든 코어에 작업이 들어가므로 코어의 수만큼 n에서 빼준다. 그 다음 시간에 대해서 이분 탐색을 수행한다. 이 이분 탐색의 목적은 우리가 찾고자 하는 작업이 들어가지는 최소의 시간을 찾기 위함이다. 즉, lower bound를 찾는 것과 동일하다. 해당 시간을 찾았으면, 이전 시간의 배열을 구해 해당 시간 배열과 빼준다. 그러면 1 0 1 0 1 1 ... 이런..

이 문제는 스택, 문자열을 이용한 그리디로 풀었다. 처음에는 이 문제에 kmp 알고리즘을 적용해봤다. 일부 테스트 케이스는 맞췄으나, 나머지에서 시간 초과가 났다. 다른 방법을 찾을 수 없어 검색을 통해 그리디 알고리즘을 사용한다는 사실을 발견했다. 만약 "110" 을 제외한 나머지 부분에 0이 하나도 없다면, 앞에 "110" 들을 나란히 붙여주는 것이 가장 숫자가 작다. 0이 하나라도 있다면 마지막 0 뒤에 110을 채워 넣어야 그 뒤에 있는 1들이 뒤로 밀려나면서 숫자가 작아지게 된다. 이를 그대로 구현하면 시간 초과 없이 정답이 나온다. #include #include #include #include using namespace std; int findLastZero(string str) { int..

이 문제는 다익스트라 알고리즘을 이용해서 풀었다. 처음에는 출발지들에 대해 루프를 돌면서 산봉우리들에 대해 루프를 돌고, 해당 출발지, 산봉우리 쌍에 대해 다익스트라 알고리즘을 사용했다. 그러나 이 방법으로는 당연히 시간 초과가 난다. 다른 방법으로 처음 다익스트라 알고리즘을 시작할 때, 우선순위 큐에 모든 출발지를 넣고 각 노드가 SUMMIT을 만나면 종료하도록 구현하는 것이다. 이 방법을 사용하면 한 번의 다익스트라 호출로 산봉우리들로 가는 최단 거리를 알 수 있다. #include #include #include #include #include using namespace std; struct compare { bool operator() (pair& left, pair& right) { retur..

이 문제는 원형 탐색, 순열을 이용한 완전 탐색을 이용해서 문제를 풀었다. 이 문제에서 핵심은 시계, 반시계 방향으로 두 가지 탐색을 하는 것이 아닌, 시계 방향 하나로만 탐색해도 전체 가짓수를 셀수 있다는 것이다. 또한 dist가 큰 사람부터 사용하는 것이 더 적게 지우는데 유리하다는 것이다. 이 두가지를 이용해서 문제를 풀었으나, 13번 테스트 케이스만 시간 초과가 났다. 검색을 통해 순열을 이용해서 부분 배열에 대한 순서쌍을 모두 탐색하는 방식으로 문제를 푸는 것을 확인했다. 내가 이전에 풀었던 방식으로는 아마 중복된 경우를 같이 카운트해서 시간 초과가 났을 확률이 높다고 생각했다. Java에는 순열 표준 라이브러리가 없어서 아쉬웠다. 그래서 C++로 풀었다. #include #include #in..