mangu

2021. 7. 10. 20:13 Algorithm/BOJ

풀이 위상 정렬을 이용하여 풀이할 수 있다. 코드 #include #include #include using namespace std; int cnt[32003]; int main() { int N, M; scanf("%d %d", &N, &M); vector v(N + 1); while (M--) { int a, b; scanf("%d %d", &a, &b); v[a].push_back(b); cnt[b]++; } queue q; for (int i = 1; i

백준[1305] 광고

2021. 7. 10. 19:42 Algorithm/BOJ

풀이 kmp의 실패 함수를 이용하여 풀이할 수 있다. 전체 문자열 길이를 L, 실패함수 배열을 pi (pi는 0 인덱스부터 시작)라 하면 L - pi[L-1]로 문제의 정답을 구할 수 있다. abcdab라는 문자열이 있을 때 pi[L-1]은 2이고 이 수는 반복되는 패턴 문자열인 abcd가 끝나고, 패턴 문자열 앞부분 ab 2 글자가 패턴 문자열에 붙은 거라고 볼 수 있다. 코드 #include char s[1000006]; int pi[1000006], L; int main() { scanf("%d %s", &L, s); int j = 0; for (int i = 1; i 0 && s[i] != s[j]) j = pi[j - 1]; if (s[i] == s[j]..

백준[4354] 문자열 제곱

2021. 7. 9. 15:20 Algorithm/BOJ

풀이 해쉬를 이용하여 풀이할 수 있습니다. abababab라는 문자열이 있다면 이것을 ab/ab/ab/ab -> ABCD라고 표현하자. 만약 ABC와 BCD가 같다면 A = B, B = C, C = D라고 할 수 있고, 이때 A의 4 제곱이라고 할 수 있다. 이 ABC와 BCD가 같은지 확인할 때 해쉬를 이용한다. 이 해쉬코드 값을 빠르게 구하기 위해서는 미리 부분 해쉬 값을 구해 놓는다. phash[i]는 0~i까지의 해쉬값이다. 또한 부분 문자열이 될 수 있는 길이의 후보는 전체 문자열의 길이의 약수들이기 때문에 약수들만 확인한다. 코드 #include #include #include using namespace std; using ll = long long; const ll MOD = 1e9 + 3..

백준[3033] 가장 긴 문자열

2021. 7. 8. 01:49 Algorithm/BOJ

풀이 라빈 카프 알고리즘을 이용하여 풀이할 수 있다. 라빈 카프를 이용하기 위해서는 패턴 문자열의 길이를 알아야 한다. 이것은 길이가 k인 문자열이 2번 반복된다면 항상 길이가 k보다 작은 문자열이 최소한 2번 이상 반복된다는 성질을 이용한다. ex) abcabc에서 abc가 2번 반복된다면 abc의 부분 문자열일 ab도 항상 2번 이상 반복된다. 이 성질을 이용하여 길이를 이분 탐색으로 결정을 한다. 코드 #include #include using namespace std; const int mod = 1e5 + 3; int Mod(long long n) { if (n >= 0) return n % mod; else return ((-n / mod + 1) * mod + n) % mod; } int m..

백준[1786] 찾기

2021. 7. 6. 18:13 Algorithm/BOJ

풀이 kmp알고리즘을 이용하여 풀 수 있다. kmp를 학교 자료구조 시간에 배웠는데 실패 함수 부분이 이해가 안 되어 포기했는데 다시 천천히 생각하니 이해할 수 있었다. 실패 함수도 kmp의 로직과 비슷하게 앞에서 비교한 것을 다시 비교하지 않고 재사용한다. 이해가 안된다면, abacabaac 이 예제로 실패 함수가 어떻게 돌아가는지 생각해보자. 코드 코드는 여기를 참고했다. #include #include #include #include using namespace std; vector getPi(string p) { int m = p.size(), j = 0; vector pi(m, 0); for (int i = 1; i 0 && p[i] != p[j]) j ..

백준[2482] 색상환

2021. 7. 5. 15:47 Algorithm/BOJ

풀이 이 문제는 dp를 이용하여 해결할 수 있다. dp[N][K] = dp[N-2][K-1] + dp[N-1][K] (N: 현재 보고 있는 색, K: 현재까지 선택한 수)로 구할 수 있다. 나는 풀고 나서 왜 맞았는지 잘 모르겠어서 구글링하다가 여기를 발견했는데 정리를 너무 잘 해놓으셨다. 코드 #include using namespace std; int dp[1003][1003]; int n, k; const int mod = 1e9 + 3; int dpf(int cur, int cnt) { int &ret = dp[cur][cnt]; //cnt가 1이면 남은 것중에 아무거나 하나만 칠하면 됨 if (cnt == 1) return cur; //cur이 2 * cnt보다 작으면 인접하는 경우가 무조건 한..

백준[17404] RGB거리 2

2021. 7. 4. 22:23 Algorithm/BOJ

풀이 이 문제는 RGB거리와 똑같이 dp문제지만 이 문제는 마지막 집과 1번 집이 연결되어 있다. 그렇기 때문에 첫 번째 집을 고정시켜 n번째에 첫 번째 색과 같은 경우를 배제시켜야 한다. dp[i][j] = i - 1에서 현재 색이 아닌 경우의 최소 + arr[i][j] (i : 현재 위치, j : 현재 색) 코드 #include #include using namespace std; int arr[1002][3]; int dp[1002][3]; int main() { int n; scanf("%d", &n); for (int i = 1; i

백준[1086] 박성원

2021. 7. 4. 21:09 Algorithm/BOJ

풀이 dp와 비트마스크를 이용하여 풀 수 있다. dp[나머지][현재 상태] = 현재 상태일 때 나머지 입력받는 수가 최대 50자리로 매우 큰 숫자이기 때문에 string으로 입력을 받고 큰 수의 나머지 값을 구해 저장해둬야 한다. (새로운 나머지) = (새로운 수) % k = ((이전 나머지) * 10 ^ (이전 수 길이) + (추가될 수)) % k = (이전 나머지) * 10 ^ (이전 수 길이) % k + (추가 될 수) % k이기 때문에 10^n % k의 값을 미리 구해놓는다. 이 부분은 아이디어가 생각나지 않아서 여기를 참고했다. 값의 출력은 기약 분수로 해야 하기 때문에 p, q의 최대 공약수를 구하여 p, q에 각각 나눴다. 나는 처음에 dp정의를 dp[현재 노드][나머지][현재 상태]로 정의..

백준[2098] 외판원 순회

2021. 7. 3. 17:43 Algorithm/BOJ

문제 링크 http://icpc.me/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 TSP(Traveling saleperson)라고 불리는 웰노운 문제다. 비트마스크와 dp를 이용하여 문제를 풀 수 있다. dp 정의는 dp[n][state] = 1부터 시작하여 state에 있는 점을 모두 지나 n번 노드까지 올 때 필요한 최소 비용으로 할 수 있다. 어느 정점에서 시작하던 사이클을 돌기 때문에 시작 정점은 고려할 필요가 없다. 나는 마지막 노드에서 0번..

백준 [1311] 할 일 정하기 1

2021. 7. 3. 15:21 Algorithm/BOJ

풀이 dp[현재 사람][이전까지 수행한 일의 상태] = 현재 일의 상태까지의 최솟값 이 문제는 비트마스크와 dp를 이용하여 풀이할 수 있다. 이전까지 수행한 일의 상태를 0011 -> 1, 2번이 일을 한 상태와 같이 비트를 이용하여 상태를 표시한다. 코드 #include #include int d[22][22]; int dp[22][1 b ? b : a; } int dpf(int cur, int state) { int &ret = dp[cur][state]; //모든 일을 한 상황 ex) n = 3일때 1000 - 1 = 0111 if (state == (1

백준[11723] 집합

2021. 7. 3. 14:03 Algorithm/BOJ

풀이 집합을 아래와 같이 비트로 표현 할 수 있다. {1, 2, 3, 4, 5} -> 11111 {2, 3, 4, 5} -> 11110 {1, 3, 5} -> 10101 i 번째 비트만 1로 바꾸기 == or 연산 set = set | (1 0010 i 번째 비트만 0로 바꾸기 == and 연산 set = set & ~(1 1111 & 1101 -> 1101 i 번째 비트만 뒤집기 == xor 연산 set = set ^ (1 1101 i 번째 비트가 1인지 0인지 확인 set & 1 0100 -> 결과값 != 0 -> i번째 비트가 1 코드 #include #include using namespace std; int main() { int M; scanf("%d", &M); int set = 0; whi..

백준[1069] 집으로

2021. 7. 1. 17:39 Algorithm/BOJ

풀이 이 문제는 별다른 알고리즘 사용없이 모든 케이스를 잘 생각해야하는 문제다. 케이스는 5가지가 있다. 1. 그냥 걸어가는 경우 2. 점프하고 남은 거리 걷는 경우 3. (0, 0)을 넘어서까지 한번 더 점프하고 뒤로 걷는 경우 4. 방향을 꺾어서 j + 1 번 점프하는 경우 5. 점프만 두번 하는 경우 코드 #include #include #include using namespace std; int main() { int x, y, d, t; scanf("%d %d %d %d", &x, &y, &d, &t); double dist = sqrt(x * x + y * y); int jump = dist / d; double remain = dist - jump * d; //그냥 걷는 경우, 점프 하고 남..

백준[7869] 두 원

2021. 6. 30. 21:08 Algorithm/BOJ

풀이 위의 그림과 같이 두 원의 겹친부분 넓이는 부채꼴의 넓이 - 삼각형의 넓이로 구할 수 있다. θ값은 코사인법칙으로 구할 수 있다 코드 #include #include #include using namespace std; double sqare(double a) { return a * a; } int main() { double x1, y1, r1, x2, y2, r2; scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &r1, &x2, &y2, &r2); if (r1 = r1 + ..

백준[2162] 선분 그룹

2021. 6. 30. 20:19 Algorithm/BOJ

풀이 이 문제는 ccw와 union find를 이용하여 해결 할 수 있다. 두 직선이 교차되었는지 판별은 선분 교차2와 동일하다. 모든 선분들에 대해 서로 교차되었는지 판변하고 교차되었다면 union을 한다. ccw의 리턴값을 1 -1 0이 아닌 원래 값으로 리턴하여, check함수에서 두 값을 곱할 시 오버플로우가 발생할 것을 예상하지 못하고 맞왜틀을 외쳤다. 조심하도록 하자. 코드 #include #include #define x first #define y second using namespace std; using pii = pair; pii a[3003], b[3003]; int par[3003], member_size[3003]; int ccw(pii a, pii b, pii c) { int ..

백준[17387] 선분 교차 2

2021. 6. 30. 20:11 Algorithm/BOJ

풀이 선분의 교차는 ccw의 값으로 구한다. ccw를 모른다면 여기를 참고하자. 직선이 교차하기 위해서는 abc abd의 ccw값의 부호가 다르고, cda cdb의 값의 부호도 달라야한다. 직선이 겹치는 경우는 항상 a b) swap(a, b); if (c > d) swap(c, d); return a

티스토리툴바