재원블로그 재원블로그

이 문제는 문자열, 구현 문제이다. 주요 포인트는 대소문자 구별 X, 알파벳을 제외한 모든 문자가 구분자가 되는 단어들 파싱, 내 링크 및 외부 링크 찾기이다. 대소문자 구별을 하지 않는 방법은 전부 대문자나 소문자로 바꿔놓는 것이다. 이는 간단하게 구현할 수 있다. 알파벳을 제외한 모든 문자가 구분자가 되는 단어들을 파싱하기 위해 for문을 돌리면서 'a'

이 문제는 완전 탐색으로 풀 수 있다. 이 문제를 정말 그대로 구현하면 24 * 60 * 60 * 1000 * 1000 = 86,400,000,000 번의 연산이 필요하여 시간 초과가 난다. 로그 배열의 최대 크기는 2,000 이므로, O(N^2) 이하의 알고리즘을 구현하면 시간 초과가 나지 않는다. 그래서 각 로그에 대해 루프를 돌면서 다른 로그들을 순회하는 방식의 알고리즘을 생각했다. 1초의 인터벌을 가지는 구간은 총 4개가 나올 수 있는데, start 왼쪽, start 오른쪽, end 왼쪽, end 오른쪽 이다. 그래서 각 로그마다 해당 4개의 구간을 설정하여 다른 로그들이 이 안에 들어올 경우 각각에 대해 1을 더해주고, 마지막에 네 개 중 가장 개수가 많은 것을 저장하는 방식으로 정답을 맞출 수..

이 문제는 백트래킹을 이용해서 풀었다. 이 문제에서 핵심은 각 행과 열이 최대 한 번씩만 뒤집는 경우로 제한하는 것과 뒤집는 순서가 바뀌어도 결과가 같다는 것이다. 우선 아래의 숫자에서 2행 -> 1열 을 뒤집고, 같은 숫자에서 1열 -> 2행을 뒤집으면 같은 결과가 나온다. 1011110111 0101010101 10001->2행10001 0100101001 1010110101 1열1열 0011100111 1101000101 00001->2행00001 1100111001 0010100101 이를 파악함으로써 뒤바뀐 순서를 다시 탐색하지 않도록 count를 두어 순서를 강제함으로써 속도를 높일 수 있다. 두 번째로 같은 행, 열을 2번 뒤집으면 원래 모양이 나오기 때문에 딱 1번만 뒤집는 경우로 최대 뒤..

이 문제는 다이나믹 프로그래밍으로 풀었다. 이 문제는 싱글, 더블, 트리플, 불 네 가지의 점수를 파악하고 그 중 겹치는 것이 있으면 싱글, 불로 카운팅하는 것이 중요하다. 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 ... 이런..