'PS' 태그의 글 목록 (2 Page)

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

백준[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

백준[20149] 선분 교차 3

2021. 6. 29. 23:12 Algorithm/BOJ

풀이 이 문제는 선행 문제인 선분교차 2 이 문제를 풀었다면 어렵지 않다. 이 문제를 모른다면 여기를 참고하자. 위의 문제를 이해했다고 가정하고 설명하겠다. 이 문제는 선분 교차 2에서 교점의 좌표만 추가로 구하면 된다. 교점의 좌표는 두 점으로부터 직선의 방정식 두 개를 구한 후 연립하면 된다. 이때 직선이 y축과 평행할 때를 조심해야 한다. 나는 이 것을 간과해 맞왜틀을 외치다 질문검색을 들어가 봤다. 코드 #include #include #define x first #define y second using namespace std; using ll = long long; using pll = pair; ll ccw(pll a, pll b, pll c) { ll ret = a.x * b.y + b.x..

백준[1949] 우수마을

2021. 6. 29. 18:10 Algorithm/BOJ

풀이 방법 이 문제는 트리 + dp를 이용하는 문제이다. dp는 dp[현재 노드 번호][현재 노드가 우수인지 아닌지 여부]로 정의한다. 2번 조건에 의해 현재 노드가 우수 마을이면 항상 다음 노드는 우수 마을이 아니고, 우수마을이 아니라면 다음 노드는 우수마을일수도 있고 아닐 수도 있다. 3번 조건은 1번 조건에 의해 자연스럽게 만족된다. 우수x -> 우수x -> 우수x 이런식으로 계속해서 될 수 있다고 착각을 하여 시간을 많이 뺏겼다. 하지만 우수x -> 우수x -> 우수x 이 상황은 항상 올 수 없다. 왜냐하면 우수x -> 우수x -> 우수x 이 상황보다 우수x -> 우수 -> 우수x 이 상황이 항상 더 크기 때문에 최댓값을 유지하기 위해서는 우수x가 계속해서 올 수 없다. 코드 #include #i..

백준[2533] 사회망 서비스(SNS)

2021. 6. 24. 13:26 Algorithm/BOJ

풀이 방법 이 문제는 트리에서 dp를 이용하는 문제이다. dp[현재 노드][현재 노드가 얼리어답터인가 여부]로 dp테이블을 만들고 현재 노드가 얼리어답터가 아니라면 자식노드는 항상 얼리어답터이고, 얼리어답터라면 얼리어답터일수도, 아닐수도 있다. 이 문제는 이 문제 와 매우 비슷하여 쉽게 해결하였다. 코드 #include using namespace std; vector v, tree; int dp[1000006][2]; bool visited[1000006]; //단방향 그래프로 바꾼다 void dfs(int cur) { if (visited[cur]) return; visited[cur] = true; for (auto nxt : v[cur]) { if (!visited[nxt]) { tree[cur]..

티스토리툴바