'Algorithm' 카테고리의 글 목록 (10 Page)

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

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

백준[2213] 트리의 독립집합

2021. 6. 24. 11:31 Algorithm/BOJ

풀이 방법 이 문제는 트리에서의 dp문제 이다. 저는 맞왜틀을 외치다 여기 를 참고했습니다. 우선 dfs를 이용하여 임의의 루트를 정하여 그 트리의 경로를 저장합니다. dp정의는 dp[현재 노드][현재 노드를 포함하는가 여부]로 정의하고, 만약 현재 노드를 포함한다면 자식 노드는 포함 할 수 없고, 포함하지 않는다면 자식노드를 포함하든 안하든 상관이 없다. 포함하는 경로 추적은 루트 노드부터 시작해서 dfs를 돌며 dpf를 돌때 저장한 배열의 값이 true인 경우를 ans배열에 저장한다. 코드 #include #include #include using namespace std; int cost[10004], dp[10004][2], check[10004], res; vector v, tree; vecto..

티스토리툴바