백준[20551] Sort 마스터 배지훈의 후계자
2021. 10. 11. 14:35
Algorithm/BOJ
문제 링크 http://icpc.me/2051 풀이 map을 사용해서 풀었다. 그냥 모든 쿼리에 대해 탐색을 하면 O(NM)이기 때문에 시간 초과가 발생한다. 그렇기 때문에 탐색하는 시간을 줄여야 한다. 이때 idx[쿼리] = 쿼리의 인덱스로 미리 다 저장해놓으면 탐색을 하지 않고 빠르게 인덱스를 구할 수 있다. 그러나 쿼리의 범위가 -10^9 ~ 10^9으로 매우 크기 때문에 배열을 선언할 수 없다. 그래서 map을 이용하여 값들을 모두 저장해놓으면 쿼리당 O(logN)에 처리할 수 있다. 다른 풀이로는 탐색을 할 때 이분 탐색을 이용하여 인덱스를 빠르게 구할 수도 있다. lower_bound를 이용하여 idx를 구하고 그 인덱스에 있는 값이 주어진 쿼리와 같은 수인지 체크하면 된다. 코드 #inclu..
백준[2457] 공주님의 정원
2021. 10. 8. 22:35
Algorithm/BOJ
문제 링크 http://icpc.me/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 풀이 그리디로 풀 수 있다. 현재 가지고 있는 꽃이 죽기 전에 피고, 가장 오랫동안 살아있는 꽃을 고르면 된다. 날짜는 구현의 편의를 위해 달에 100을 곱하고 일을 더했다. ex) 2월 28일 = 228 문제를 읽자마자 그리디일거같았지만 구현하는데 시간이 꽤 걸렸다. 코드 #include #include using namespace std; pair arr[100005]; int main() {..
백준[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(..
좌표 압축
2021. 9. 25. 10:48
Algorithm/개념
수의 범위가 매우 큰 상황에서 수의 값에 무관하게 좌표들 사이의 대소만 알면 될 때, 좌표 압축을 이용하면 수의 범위를 줄일 수 있다. 1. 좌표 압축을 할 배열을 임시의 배열에 중복이 없고 정렬된 상태로 만들어 놓는다. 2. 압축할 배열의 각 수들이 임시의 배열에 몇 번째 인덱스에 해당하는 수인지 찾으면 된다. 임시의 배열은 정렬된 상태이기 때문에 이분 탐색을 이용하여 O(logN)에 찾을 수 있다. C++에서 좌표 압축을 구현할 때에는 주로 std::sort, std::unique 함수로 1번을 수행하고, std::lower_bound 함수를 이용하여 2번을 수행한다. 가지고 있는 모든 수의 값을 저장한 임시의 배열을 정렬한 후 unique 함수를 이용하여 중복되는 수를 모두 제거하고, lower_b..
백준[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 ..