https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 처음에 어렵게 생각해서 kmp로 풀어야하나 싶었지만 그러면 약 4000 * 4000 개 경우에 대해 4000 + 4000번의 kmp 알고리즘을 수행해야하기 때문에 (kmp : O(n+m)) 시간초과일거라 생각했지만 제출해보니 역시 시간초과였습니다. 하지만 dp로 쉽게 풀 수 있었습니다. dp[m][n] 을 문자열 s1, s2의 m, n 번째 문자가 일치할 때 최대 길이로 잡으면 결국 이..
https://www.acmicpc.net/problem/6487 6487번: 두 직선의 교차 여부 두 개의 직선을 나타내는 4개의 점이 입력으로 주어질 때, 두 직선이 만나는지를 확인하는 프로그램을 작성하시오. www.acmicpc.net 그냥 단순히 두 직선의 교차 여부와 교점만을 구하면 됩니다. 외적을 이용하면 직선의 교점을 뭔가 더 쉽게 계산할 수 있을 거 같은데 그냥 케이스 나눠서 계산시켰습니다. 일치하는 직선이거나 평행한 직선의 여부는 두 직선의 다른 점의 방향 벡터와 기존 방향 벡터의 외적을 다시 구해 일치여부를 확인하면 됩니다. 코드는 다음과 같습니다. #include using namespace std; int N; double x1, y1; double x2, y2; double x3,..
https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 예전에 풀었었지만 틀렸었던 문제인데 이번에도 한 번 틀렸습니다. (경계 나누는 부분에 겹치는 부분 있어서 찾느라 시간 다 보냈다.... 예전에는 문제 이해를 잘못해서 틀렸었던 것 같기도?) 문제 자체는 어렵지 않습니다. 문제에 주어진 조건대로 구역을 나누어 최대 인구와 최소 인구의 차이가 최소가 되도록 하면 됩니다. 맵의 전체 최대 크기가 20x20 이고, 구역 나누는 길이는 최대 1x1 ~ 19x1 ..
https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 오랜만에 푸는 거라 간단한 문제로 풀어보았습니다. A와 B를 비교할 때 A에 x2 또는 A + "1" 을 하여 B를 몇 번만에 만들 수 있는 지 구하는 문제입니다. 간단하게 bfs를 이용하여 풀었습니다. A를 x2, +"1" 2가지에 대해 계속 탐색하면서, B와 일치하는 경우가 처음 나오면 그 경우가 답입니다. x2, +"1" 을 하여도 B보다 작은 경우, 계속 탐색을 이어가고, 그렇지 않으면 탐색을 거기서는 멈춥니다. 코드는 다음과 같습니다. #include #include #include #include #includ..
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 뭔가 쉬울 거 같으면서도 될 거 같은 경우가 많았던 문제입니다. 저는 우선순위 큐를 이용해 풀었습니다. 먼저 각 입력으로 들어오는 값들을 정렬하고 (20만 개니까 n log n 인 걸로) 정렬 시 시작 시간이 빠른 순으로 정렬합니다. 그리고 우선순위 큐는 오름차순으로 세팅합니다. 우선순위 큐에 들어 가는 값은 각 수업이 끝나는 시간입니다. 이렇게 하는 이유는 우선 순위 큐의 top 값이 결국 가장 빨리 끝나는 시간을 의미하며, 시작 시간이 빠른..