백준[2800] 괄호 제거
2021. 10. 7. 15:52
Algorithm/BOJ
문제 링크 http://icpc.me/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 풀이 백트래킹과 스택을 이용하여 풀 수 있다. 우선 여는 괄호와 닫는 괄호의 짝을 찾아 이것을 인덱스로 가지고 있어야 한다. 이 짝을 찾기 위해서 스택을 이용한다. )를 만날 때 까지 스택에 모두 push하다가 ) 를 만날때 ( 를 만날 때까지 pop을 하고 처음 만난 (가 )의 짝이다. 위에 구해둔 괄호 쌍을 이용하여 백트래킹을 한다. 백트래킹을 해도 괄호가 최대 10개이기 때문에 ..
백준[2015] 수들의 합 4
2021. 10. 5. 16:12
Algorithm/BOJ
문제 링크 http://icpc.me/2015 풀이 누적합을 이용하여 풀 수 있다. 0~i번째까지의 합을 미리 구해놓고, 구해놓은 누적합을 잘 관찰하여 풀 수 있다. psum[i] : 0 ~ i까지의 합이라고 할 때, i ~ j까지의 합은 psum[i] - psum[j-1]이다. 이때 구간 합이 k가 되는지 확인할 수 있는 여부는, psum[i] - psum[j-1] (j < i) == k가 되는 j 값이 몇개 존재하는지 확인하면 된다. 그리고 psum[i] 자체가 k인지도 체크하면 된다. 그렇기 때문에 psum[1] ~ psum[n]까지 값을 기록해야 하는데 값의 범위가 20억으로 매우 크므로 그냥 배열을 만들 수 없어, map을 이용하여 저장한다. 코드 #include #include #include..
백준[13976] 타일 채우기 2
2021. 10. 5. 12:37
Algorithm/BOJ
문제 링크 http://icpc.me/13976 13976번: 타일 채우기 2 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000,000,000,000)이 주어진다. www.acmicpc.net 풀이 dp와 분할 정복을 이용하여 풀이할 수 있다. 분할 정복을 이용한 행렬의 빠른 거듭제곱은 곱셈을 풀면서 공부하자. dp점화식은 dp[n] = 3*dp[n-2] + sum(dp[k]) (k는 n-4부터 0까지 k-=2) 위의 식에 n-2를 대입한식과 위의 식을 빼면 dp[n] = 4 * dp[n-2] - dp[n-4]가 나온다. 행렬식으로 표현하면 위와 같이 표현할 수 있다. 이제 위의 행렬식을 분할정복을 이용하여 빠르게 계산하면 된다. 코드 #include #include using namespace st..
백준[15961] 회전초밥
2021. 10. 2. 18:36
Algorithm/BOJ
문제 링크 http://icpc.me/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 풀이 슬라이딩 윈도우로 풀 수 있다. k개의 연속된 초밥 그룹에 어떤 종류의 초밥이 몇 개 있는지 그룹을 오른쪽으로 밀면서 그룹에 수들의 종류가 몇 개 있는지 확인하면 된다. 그룹을 밀 때, 기존의 왼쪽 끝의 수가 하나 빠지고, 오른쪽에 수가 하나 들어온다. 이때, 왼쪽 수가 기존의 그룹에 유일하면 cnt--해주고, 새로운 수가 기존에 없으면 cnt++을 하면 된다. 회전..
백준[22352] 항체 인식
2021. 10. 2. 00:18
Algorithm/BOJ
문제 링크 http://icpc.me/22352 풀이 간단한 bfs/dfs문제이다. 붙어있는 같은 데이터들을 모두 탐색하면서, before와 after가 다른 세트가 2세트 이상 있다면 No를 출력하면 되는 문제다. 필자는 bfs로 구현했다. 코드 #include #include using namespace std; int before[32][32], after[32][32]; bool visited[32][32]; queue q; int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i
백준[22965] k개의 부분 배열
2021. 10. 1. 01:11
Algorithm/BOJ
문제 링크 http://icpc.me/22965 22965번: k개의 부분 배열 4 5 6 / 1 2 3으로 나눈 뒤, 1 2 3 / 4 5 6으로 재배열하면 된다. www.acmicpc.net 풀이 이 문제는 아이디어만 잘 생각해낸다면 쉽게 풀 수 있는 문제다. 처음에 삽질을 좀 많이 했는데 푸는데 매우 재밌었다. 잘 생각을 해보면 이 문제에서 나올 수 있는 k의 값의 최댓값은 3이다. 이유는 간단하다. 선택 정렬을 하듯이 가장 큰 값, 또는 가장 작은 값을 찾아서 그 수를 맨 앞, 또는 맨 뒤로 보내는 과정을 계속하면 정렬이 될 것이다. 예를 들어, 4 3 6 1 2 5 로 수행을 해보자. 4 3 6 | 1 | 2 5 -> 4 3 6 2 5 1 4 3 6 | 2 | 5 1 -> 4 3 6 5 1 2 ..
백준[1120] 문자열
2021. 9. 29. 14:50
Algorithm/BOJ
문제 링크 http://icpc.me/1120 풀이 A를 B의 부분 문자열과 비교할 때 A와 B의 부분 문자열 사이에 다른 개수를 세면 된다. A와 길이가 같은 B의 부분 문자열과 비교를 하여 다른 부분을 구한다면, A의 나머지 추가하는 부분은 모두 B와 동일하게 앞뒤에 추가를 하면 되기 때문에 이렇게 풀 수 있다. 구현은 N이 50으로 매우 작기 때문에 전탐색 하면 된다. 코드 #include #include #include using namespace std; string s1, s2; int ans = 1e9; int main() { cin >> s1 >> s2; for (int i = 0; i
백준[19951] 태상이의 훈련소 생활
2021. 9. 28. 19:52
Algorithm/BOJ
문제 링크 http://icpc.me/19951 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연 www.acmicpc.net 풀이 세그먼트 트리를 이용하여 풀이하였다. 하지만 누적합을 이용하여 더 쉽게 풀이할 수 있는 것 같다. 수열과 쿼리21과 문제가 비슷하여 똑같이 풀이하였다. 자세한 풀이는 저 링크를 참고하자. 코드 #include int seg[400005], arr[100005]; void init(int node, int s, int e) { if (s == e) { seg[node] = arr[s]; return..
백준[1021] 회전하는 큐
2021. 9. 28. 00:10
Algorithm/BOJ
문제 링크 http://icpc.me/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 덱을 이용하여 풀 수 있다. 덱에서 뽑을 수의 위치를 찾아서 그 위치가 덱의 중간지점보다 오른쪽에 있다면 3번을 덱의 첫 번째에 원하는 수가 위치할 때까지 반복하고, 중간지점보다 왼쪽에 있다면 2번을 첫 번째에 원하는 수가 위치할 때까지 반복한다. 코드 #include #include #include using namespace std; int main() { deque dq; int n, m; scanf(..
백준[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행에 채울 값과 동일한 값이 있는지 체크하면 된다. 대각선에 놓여..
백준[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번..