'알고리즘' 태그의 글 목록 (3 Page)

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]..

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

백준[2887] 행성터널

2021. 6. 22. 21:17 Algorithm/BOJ

풀이 방법 모든 간선에 대해 크루스칼 알고리즘을 이용하면 간선의 개수가 N * (N - 1) / 2이기 때문에 메모리 초과가 발생한다. 그렇기 때문에 모든 간선에 대해 크루스칼 알고리즘을 적용하는 것이 아닌 x로 정렬하여 인접한 노드들 끼리의 간선, y로 정렬한 간선, z로 정렬한 간선들로만 크루스칼 알고리즘을 적용한다. 코드 #include #include #include #include using namespace std; using pii = pair; using piii = pair; struct T { int x, y, z, idx; }; priority_queue pq; int N, ans, cnt; T arr[100005]; int par[100005]; bool compare(T a, T ..

백준[4386] 별자리 만들기

2021. 6. 22. 00:39 Algorithm/BOJ

풀이 방법 최소 신장 트리(MST)를 구하는 문제이다. MST는 prim 알고리즘과 kruskal 알고리즘을 통해 구할 수 있다. 이 풀이는 prim 알고리즘을 이용했다. cf) prim 알고리즘을 모른다면 여기를 참고하세요 코드 #include #include #include using namespace std; using pdd = pair; using pdi = pair; pdd arr[102]; bool visited[102]; priority_queue pq; // 최소 힙 int N; double ans; //점과 점 사이의 거리 double dist(pdd a, pdd b) { return sqrt((a.first - b.first) * (a.first - b.first) + (a.secon..

티스토리툴바