백준[17413] 단어 뒤집기 2
2021. 9. 6. 20:43
Algorithm/BOJ
문제 링크 http://icpc.me/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 풀이 스택을 이용하여 풀이할 수 있다. 문자열을 처음부터 읽으면서 아무것도 만나지 않았을 때는 stack에 담다가
백준 [2494] 숫자 맞추기
2021. 9. 5. 17:24
Algorithm/BOJ
문제 링크 http://icpc.me/2494 2494번: 숫자 맞추기 아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10 www.acmicpc.net 풀이 dp를 역추적하는 문제다. 백준 13392 방법을 출력하지 않는 숫자 맞추기 이 문제에서 역추적만 포함하면 된다. dp를 호출할 때 왼쪽 자식에서 왔는지 오른쪽 자식에서 왔는지 체크를 해주면서 함수를 호출하면 된다. 코드 #include #include using namespace std; struct T { int x, y, m; }; char from[10004]; char to[10004]; int dp[..
백준[13392] 방법을 출력하지 않는 숫자 맞추기
2021. 9. 3. 16:50
Algorithm/BOJ
문제 링크 http://icpc.me/13392 풀이 dp를 이용하여 풀이할 수 있다. 처음에 문제를 보자마자 든 생각은 dp[현재 숫자]로 1차원으로 정의하려 했지만 이렇게 했을 시 dp테이블이 10^10000 크기를 가져야 하므로 바로 패스했다. 그렇다면 현재 숫자를 가벼운 정보를 가지고 구할 수 있어야한다. 현재 내가 보고 있는 i번째 숫자를 알기 위해서 필요한 정보는 0 ~ i-1번째 숫자를 맞추는 동안 왼쪽으로 몇 번을 돌렸는지를 알아야 한다. 그렇기 때문에 dp를 정의할 때 왼쪽으로 돌린 횟수를 가지고 있어야 한다. 또한 왼쪽으로 10번을 돌리면 다시 자기 자신으로 돌아오기 때문에 (왼쪽으로 돌린 횟수) % 10의 정보만 가지고 있으면 된다. dp[i 번째 숫자 나사를 돌림][0 ~ i -1번..
백준[1509] 팰린드롬 분할
2021. 9. 2. 15:46
Algorithm/BOJ
문제 링크 http://icpc.me/1509 풀이 dp를 2번 사용하여 풀이할 수 있다. palin[i][j] : 문자열 구간 i ~ j 까지가 팰린드롬인지 여부 s[i] == s[j] 이면서 i+1 ~ j-1이 팰린드롬이면 i ~ j 가 팰린드롬이다. 이렇게 구해둔 팰린드롬인지 여부를 이용하여 한번 더 dp를 돌린다. dp[i] : 1 ~ i까지 최소 분할 팰린드롬 수 if palin[i][j] == true : dp[j] = max(dp[j], dp[i - 1] + 1)로 정의 할 수 있다. 코드 #include #include using namespace std; bool palin[2503][2503]; int dp[2503]; int main() { cin.tie(0) -> sync_with_..
백준[7626] 직사각형
2021. 9. 1. 13:43
Algorithm/BOJ
문제 링크 http://icpc.me/7626 풀이 백준[3392] 화성지도 이 문제와 거의 유사하다. 위 문제와 풀이는 모두 동일한데 값의 범위가 매우 크기 때문에 좌표압축을 해야한다. 코드 #include #include #include using namespace std; using ll = long long; using pll = pair; const ll MAX = 4e5 + 5; struct T { T(ll x, pll y, ll finish) : x(x), y(y), finish(finish) {} ll x; pll y; ll finish; }; vector v; vector ySet; ll seg[MAX * 4]; ll cnt[MAX * 4]; void update(ll node, ll s..
백준[3392] 화성지도
2021. 9. 1. 13:40
Algorithm/BOJ
문제 링크 http://icpc.me/3392 풀이 스위핑과 세그먼트 트리를 이용하여 풀이할 수 있다. 모든 점을 x축 기준으로 정렬을 하여 왼쪽부터 쓸면서 값을 구하면 된다. 이때 세그먼트 트리로 y축의 점들을 저장해놓는다. 만약 점이 시작하는 점이라면 세그먼트 트리에 1을 더하고, 끝나는 점이라면 -1을 더하면 된다. 하지만 겹치는 부분의 넓이는 구하면 안되기 때문에 위처럼 저장하여 넓이를 바로 계산하면 문제가 발생한다. 그렇기 때문에 세그먼트 트리를 2개 활용한다. 하나는 구간에 점이 몇개가 있는지를 저장하고, 하나는 점이 있는지 유무만 확인할 수 있게 저장한다. 코드 #include #include using namespace std; using pii = pair; struct T { T(int..
백준[2042] 구간 합 구하기
2021. 8. 29. 23:00
Algorithm/BOJ
문제 링크 http://icpc.me/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 세그먼트 트리 또는 펜윅 트리 기본 문제이다. 개념을 설명은 다른 분이 잘해놓으셔서 생략하겠다. 세그먼트 트리는 여기를 펜윅트리는 여기를 참고해라. 코드 세그먼트 트리 #include using ll = long long; ll arr[1000006]; ll tree[4000006]; ll init(ll node, ll start, ll end) { i..
백준[17131] 여우가 정보섬에 올라온 이유
2021. 8. 26. 17:41
Algorithm/BOJ
문제 링크 http://icpc.me/17131 17131번: 여우가 정보섬에 올라온 이유 첫 줄에 별의 개수 N이 주어진다. 그 다음 줄부터 N개의 줄에 걸쳐 별의 좌표 x y가 주어진다. www.acmicpc.net 풀이 스위핑과 세그먼트 트리를 이용하여 풀이할 수 있다. v를 만들기 위해서는 제일 아래 점 하나를 기준으로 (왼쪽 위의 점 개수) * (오른쪽 위의 점 개수)로 구할 수 있다. 모든 점에 대해 위의 값을 구하기 위해서는 y좌표 기준으로 오름차순으로 정렬한 후 가장 아래 있는 점부터 확인을 하며 업데이트를 해줘야 한다. 가장 아래 있는 점을 고르면 그것보다 x좌표가 작으면 항상 왼쪽 위에 존재하는 점이고, x가 크면 오른쪽 위에 존재하는 점이다. 하지만 이 성질이 항상 만족하려면 y좌표가..
백준[2836] 수상 택시
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) 나는 출력 형식을 제대로 보지 않아서 시간을 약간 날렸다. 출..
백준[12899] 데이터 구조
2021. 8. 19. 13:15
Algorithm/BOJ
문제 링크 http://icpc.me/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 풀이 세그먼트 트리를 이용하여 k번째 수를 가져오는 문제이다. 세그먼트 트리를 만들 때 수의 범위가 아닌 수의 값으로 범위를 정해야 한다. 예를 들어, 5번째 수를 구할 때, 1 ~ N/2에 수가 6개 N/2 + 1 ~ N에 수가 3개가 있다고 한다면 왼쪽 노드로 이동하여 같은 작업을 반복해야 한다. 반면에 1 ~ N/2에 수가 2개 N/2 + 1 ~ N에 수가 5개가 있다고 하면, ..
백준[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)에 처리할..
백준[9345] 디지털 비디오 디스크(DVDs)
2021. 8. 15. 15:18
Algorithm/BOJ
문제 링크 http://icpc.me/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 풀이 세그먼트 트리를 이용하여 풀이할 수 있다. a ~ b 사이에 a, a+1, ... , b 만 존재한다면 이때 최솟값은 a 최댓값은 b이다. 만약 저 구간에 다른 값이 들어간다면 최솟값, 최댓값은 a, b가 될 수 없다. 이 구간 최대, 최소값을 세그먼트 트리로 관리하면 쿼리당 O(logN)에 처리할 수 있다. 코드 #include #include using names..