'알고리즘' 태그의 글 목록

2021. 8. 25. 15:29 Algorithm/BOJ

문제 링크 http://icpc.me/2836 2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 풀이 스위핑을 이용하여 풀이할 수 있다. a에서 태워 b에서 내려준다고 할 때, 상근이가 무조건 M에 도달해야 하기 때문에 a b인 상황에서 언제 되돌아가서 내려줄건지 고려를 잘해야 한다. 최단 경로로 가기 위해서는 같은 경로를 여러 번 돌아가면 안 된다. 그렇기 때문에 a -> b와 c -> d로 가는 두 경로가 만약 겹친다면 한 번에 움직여야 한다. 코드 ..

백준[5419] 북서풍

2021. 8. 20. 19:17 Algorithm/BOJ

문제 링크 http://icpc.me/5419 5419번: 북서풍 각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다. www.acmicpc.net 풀이 스위핑과 세그먼트 트리를 이용하여 풀이할 수 있다. y좌표를 좌표압축을 한 후에 x좌표 기준 오름차순 정렬하고 만약 x좌표가 같다면 y좌표가 큰 순으로 정렬한다. k번째 점과 쌍이 될 수 있는 점의 수는 x좌표가 k보다 작고, y좌표는 k보다 크거나 같은 점의 수이다. 이때 이 점들을 전탐색하면 O(N^2)으로 시간이 터져버린다. 그렇기 때문에 k번째 점과 쌍이 될 수 있는 점의 수를 세그먼트 트리를 이용하여 시간을 줄여줘야 한다. k의 y좌표 ~ 범위 끝까지의 수를 가져오면 빠르게 수를 구할 수 있다. 세그먼트 트리를 ..

백준[2170] 선 긋기

2021. 8. 20. 15:37 Algorithm/BOJ

문제 링크 http://icpc.me/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 풀이 스위핑 알고리즘을 이용하여 풀이 할 수 있다. 여기에 다른분이 잘 정리 해놨다. 수를 x좌표 기준으로 오름차순으로 정렬한 후 범위가 겹친다면 범위를 점차 늘려나가고, 겹치지 않을 때 그동안 늘려온 범위의 값을 더하며 새로운 범위를 시작한다. 코드 #include #include using namespace std; using pii = pair; pii arr[1000006]; in..

백준[1168] 요세푸스 문제 2

2021. 8. 19. 18:01 Algorithm/BOJ

문제 링크 http://icpc.me/1168 1168번: 요세푸스 문제 2 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) www.acmicpc.net 풀이 이 문제를 응용하여 풀 수 있는 문제다. x = k라 할 때 처음엔 x번째 수를 제거하고 그다음은, x + k-1번째 수를 제거하고 다음은 x + 2*(k-1) 번째를 제거는 과정을 계속해서 반복한다. 이때 x + i(k - 1)이 남은 수의 개수보다 크다면 x + i(k-1) % (남은 수의 개수)를 취한다. 하지만 그 값이 0이 되면 안 되기 때문에 남은 수의 개수로 나누어 떨어질 때는 x = (남은 수의 개수)로 만든다. cf) 나는 출력 형식을 제대로 보지 않아서 시간을 약간 날렸다. 출..

백준[16975] 수열과 쿼리 21

2021. 8. 16. 17:35 Algorithm/BOJ

문제 링크 http://icpc.me/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 풀이 1 세그먼트 트리의 구간 업데이트를 하는 lazy propagation을 이용하여 풀이할 수 있다. lazy propagation에 대한 자세한 설명은 여기와 여기를 참고해라. 풀이 2 lazy propogation을 사용하지 않고, 세그먼트 트리만을 이용하여 풀이할 수도 있다. 아래 그림과 같이 업데이트하는 방식과 쿼리를 리턴하는 방식을 기존과 반대로 하면 구간 업데이트에 대해 O(logN)에 처리할..

백준[3648] 아이돌

2021. 8. 6. 10:16 Algorithm/BOJ

문제 링크 http://icpc.me/3648 풀이 SCC를 응용한 2-SAT으로 문제를 해결할 수 있다. 2-SAT을 모른다면 BOJ 2-SAT - 3를 참고해라. 코드 #include #include #include #include using namespace std; vector v, rev; stack s; bool visited[2003]; int scc[2003], idx, n, m; inline int T(int x) { return x

백준[5557] 1학년

2021. 8. 4. 23:32 Algorithm/BOJ

문제 링크 http://icpc.me/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 dp를 이용하여 해결할 수 있다. dp[i][j] : j번째 숫자까지 봤을 때 숫자 i를 만들 수 있는 최댓값으로 정의할 수 있다. 코드 #include using ll = long long; ll dp[22][102], arr[102], n; ll dpf(ll cur, ll idx) { if (cur 20) return 0; ll &ret = dp[cur][idx]; if (re..

백준[2225] 합분해

2021. 8. 4. 22:49 Algorithm/BOJ

문제 링크 http://icpc.me/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 dp를 이용하여 풀이할 수 있다. dp [남은 수][뺄 수 있는 횟수]로 정의할 수 있다. 코드 #include using ll = long long; ll dp[202][202], N, K; const ll mod = 1e9; ll dpf(ll n, ll k) { ll &ret = dp[k][n]; if (ret) return ret; // 남은 수와 뺄 수 있는 횟수가 0일때 1리턴 if (!n && !k) return 1; // 뺄 수 있는 횟수는 끝났는데 수가 남아있을 때 0리턴 if (n && !k) return 0; for (..

백준[1915] 가장 큰 정사각형

2021. 8. 4. 19:18 Algorithm/BOJ

문제 링크 http://icpc.me/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 dp로 해결할 수 있다. dp 점화식은 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]), (i, j는 배열 인덱스)로 정의할 수 있다. 위의 그림과 같은 예제가 있을 때 (2, 2) 인덱스에서 한 변의 길이가 2인 정사각형이 만들어지기 위해서는 왼쪽, 위, 왼쪽 위 가 모두 1이어야 한다. 이 말을 바꿔 말하면 min(dp[1][1], dp[1][2], dp[2][1]) + 1 == 1 이어야 한다. (5, 5)에서 한 ..

백준[2602] 돌다리 건너기

2021. 8. 3. 13:13 Algorithm/BOJ

문제 링크 http://icpc.me/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 풀이 dp를 이용하여 풀이할 수 있다. dp는 dp[악마다리 or 천사다리][몇 번째 패턴 문자까지 발견][몇 번째 돌다리까지 갔나]로 정의할 수 있다. 코드 #include #include using namespace std; int dp[2][22][100]; string pat, a, b; int dpf(int up_down, int pat_num, int cur_num) { int &ret = dp[up_down][pa..

백준 [11280] 2-SAT - 3

2021. 8. 2. 22:38 Algorithm/BOJ

문제 링크 http://icpc.me/11280 11280번: 2-SAT - 3 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 풀이 이 문제는 SCC를 구하기 위해 코사라주 알고리즘을 이용한다. (xi V xj)가 항상 참이기 위해서는 xi 가 거짓이라면 xj는 항상 참이어야 한다. 또한 반대로 xj 가 거짓이라면 xi는 항상 참이어야 한다. 그렇기 때문에 not(xi) -> xj와 not(xj) -> xi 간선을 만든다. 이것은 위의 설명을 그래프로 나타낸 것이다. 이때 한 ..

백준[4013] ATM

2021. 7. 30. 16:28 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/4013 풀이 SCC, 유니온 파인드, 위상 정렬, dp를 이용하여 풀이하였다. 다 푼 후에 다른 사람의 코드를 보고 깨달았지만, 유니온 파인드는 굳이 사용하지 않아도 된다. 출발지점부터 순회하며 dp를 돌리면 될 것 같지만 사이클이 존재하기 때문에 그럴 수 없다. 그렇기 때문에 사이클이 없는 방향 그래프로 바꿔줘야 한다. 사이클을 제거하기 위해 SCC를 사용한다. 아래 코드는 코사라주 알고리즘을 이용하였다. 구해진 SCC를 이용하여 사이클을 하나의 큰 노드로 합친다. 나는 이때 유니온 파인드를 사용하였다. 하지만 이미 SCC들을 모두 구했기 때문에 이미 합쳐져 있는 상태여서 유니온 파인드를 사용하지 않아도 된다. scc vector의 ..

백준[3977] 축구 전술

2021. 7. 29. 00:26 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/3977 풀이 이 문제는 코사라주 알고리즘을 이용하여 SCC를 구해서 풀 수 있다. 백준 4196 도미노 와 매우 비슷하다. 도미노 문제와 동일하게 dfs를 돌리며 방문할 노드가 없을 때 스택에 추가하면 stack의 top에는 가장 많은 곳을 갈 수 있는 노드가 위치하게 된다. 그렇기 때문에 stack의 top에 있는 노드를 시작으로 다시 dfs를 돌려 모든 노드를 방문할 수 있는지 판별하고, 만약 모두 방문할 수 있다면 top에 있는 노드의 SCC를 출력하고 그렇지 않다면 Confused를 출력한다. 코드 #include #include #include #include #include using namespace std; vector ..

백준[4196] 도미노

2021. 7. 28. 18:27 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 풀이 이 문제는 SCC를 이용하여 풀 수 있다. 처음에 이 문제를 보고 아무 점에서나 dfs를 돌려서 dfs를 몇 번 돌리나 카운팅 하면 될 것이라고 생각했다. 하지만 1 -> 2 -> 3 -> 4가 있을 때 1번에서 dfs가 시작하면 문제가 없지만 2, 3, 4번에서 dfs가 시작하면 1번은 처리가 되지 않는다. 그렇기 때문에 SCC를 활용해야한다. 코사라주 알고리즘을 이용하면 stack의 최상단에는..

백준[2150] Strongly Connected Compoment

2021. 7. 28. 14:44 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/2150 풀이 이 문제는 SCC를 구하는 문제이다. 나는 코사라주 알고리즘(Kosaraju's algorithm)을 이용하여 SCC를 구했다. 코사라주 알고리즘은 우선 방향 그래프와 역방향 그래프를 dfs로 탐색하며 진행된다. 1. 방향 그래프를 dfs로 탐색하며 더 이상 갈 수 있는 곳이 없을 때 stack에 push 한다. -이 과정을 모든 정점에 대해 dfs를 진행할 때까지 반복한다. 2. 역방향 그래프를 stack의 top부터 순회하며 이때 만나는 노드들이 SCC다. -이때 top에 있는 정점이 이미 방문한 정점이라면 pop을 한다. https://stonejjun.tistory.com/113 증명은 이 글을 참고하자. 코드 #i..

티스토리툴바