백준[9663] N-Queen
2021. 9. 25. 00:24
Algorithm/BOJ
문제 링크 http://icpc.me/9663 풀이 백트레킹을 이용하여 풀이할 수 있다, 백트레킹을 이용하면서 약간의 테크닉이 필요하다. N * N 크기의 배열에 좌표가 있는지 true/false로 저장을 해놓으면 퀸이 놓을 수 있는지 확인하는데 시간이 많이 든다. 한 행에는 하나의 퀸만 놓일 수 있다는 점을 이용하여 크기가 N인 배열만을 이용하여 퀸을 놓을 수 있는지 여부를 확인할 수 있다. visited 배열은 visited[2] = 1이라고 하면 (1, 2)의 점에 퀸이 놓아져 있다는 의미로 사용할 수 있다. 0 ~ n -1 행순으로 채운다고 할떄, 현재 행 x를 채울 때 같은 열에 있는지 확인하는 방법은 0 ~ x-1 행의 값 중 x행에 채울 값과 동일한 값이 있는지 체크하면 된다. 대각선에 놓여..
백준[17070] 파이프 옮기기 1
2021. 9. 15. 16:34
카테고리 없음
문제 링크 http://icpc.me/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 풀이 dp를 이용하여 풀 수 있다. dp[x][y][state] : (1, 1)에서 가장 오른쪽 아래 점 (x, y)까지 state(가로, 세로, 대각선)로 올 수 있는 개수 코드 #include #include int arr[20][20]; int dp[20][20][3], n; bool check(int y, int x) { // 대각선 체크 if (!arr[y + 1][x] && ..
백준[1657] 두부장수 장홍준
2021. 9. 10. 15:10
Algorithm/BOJ
문제 링크 http://icpc.me/1657 풀이 비트 마스크를 하면서 dp를 돌면 된다. 백준[1648] 격자판 채우기와 거의 유사한 문제이다. 위의 문제와 차이점은 현재 칸을 안 채우고 넘어가는 경우가 있는 것이다. 코드 #include using namespace std; int dp[15 * 15][1 s[1]) swap(s[0], s[1]); if (s[0] == 'A') { if (s[1] == 'A') return 10; if (s[1] == 'B') return 8; if (s[1] == 'C') return 7; if (s[1] == 'D') return 5; if (s[1] == 'F') return 1; } else if (s[0] == 'B') { if (s[1] == 'B') r..
백준[1648] 격자판 채우기
2021. 9. 10. 14:15
Algorithm/BOJ
문제 링크 http://icpc.me/1648 1648번: 격자판 채우기 준규는 침대에 누워서 천장을 바라보고 있었다. 천장은 격자판 모양이었고, 계속해서 천장을 바라보다 보니 이런 생각이 들었다. 세로 크기가 N이고, 가로 크기가 M인 격자판을 2x1 크기의 도미노 www.acmicpc.net 풀이 비트 마스킹을 하며 dp를 돌면 풀 수 있다. 위와 같은 타일이 있을 때, k 번째 타일을 놓기 위해 필요한 정보는 k + 1 번째 타일이 채워져 있는지 여부와 k + 6(m) 번째 타일이 채워져 있는지 여부이다. 이와 같이 k번째 타일을 채우기 위해서는 m개의 타일 정보만 가지고 있으면 된다. 그렇기 때문에 m개의 타일 정보를 비트 마스킹하며 채워나가면 된다. 코드 #include #include int ..
백준[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..
백준[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) 나는 출력 형식을 제대로 보지 않아서 시간을 약간 날렸다. 출..