'Algorithm/BOJ' 카테고리의 글 목록 (5 Page)

2021. 10. 22. 12:30 Algorithm/BOJ

문제 링크 http://icpc.me/1270 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n n / 2) printf("%lld\n", idx); else printf("SYJKGW\n"); } }

2021. 10. 20. 11:24 Algorithm/BOJ

문제 링크 http://icpc.me/23247 23247번: Ten A real estate company IC is managing a rectangular section of land. The section is divided into $mn$ segments in $m \times n$ matrix shape, where the number of rows and that of columns are $m$ and $n$, respectively. Each segment has its own price as a posi www.acmicpc.net 풀이 2차원 누적합을 이용하는 문제다. 2차원 누적합을 모른다면 2차원 누적합 설명을 참고해라. 모든 경우를 확인하며 넓이가 300이 되는 경우를 찾으면 ..

백준[20168] 골목 대장 호석 - 기능성

2021. 10. 20. 01:27 Algorithm/BOJ

문제 링크 http://icpc.me/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 풀이 백트레킹을 이용하여 풀 수 있다. n의 크기가 매우 작으니 백트레킹을 하며 모든 경우를 확인해보면 된다. 코드 #include #include using namespace std; int d[11][11]; int n, m, a, b, c, ans = 1e9, totalSum = 1e9; bool visited[11]; void solve(int cur, int total, i..

백준[2729] 이진수 덧셈

2021. 10. 19. 17:46 Algorithm/BOJ

문제 링크 http://icpc.me/2729 2729번: 이진수 덧셈 이진수 덧셈은 매우 간단하고, 십진수 덧셈과 비슷하게 하면 된다. 십진수 덧셈을 할 때는, 오른쪽부터 왼쪽으로 차례대로 숫자 하나씩 더하면 된다. 이진수 덧셈도 이와 비슷하게 하면 된다. 십 www.acmicpc.net 풀이 구현만 잘하면 되는 문제다. 수를 더할 때 맨 뒤에서부터 더하기 때문에 구현의 편의를 위해 입력받은 이진수를 둘 다 뒤집고 앞에서부터 연산하며 정답이 될 수의 앞부터 채워나갔다. 그런 후 최종 정답은 reverse를 했다. 그리고 문제 조건에 앞에 불필요한 0이 붙으면 안 된다는 조건 때문에 출력을 1을 발견했을 때부터 하고, 만약 다 끝까지 1이 발견되지 않는다면 값이 0이기 때문에 0을 출력한다. 이 부분을 ..

백준[1374] 강의실

2021. 10. 16. 22:40 Algorithm/BOJ

문제 링크 http://icpc.me/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 풀이 이 문제는 관찰을 잘한다면 풀 수 있다. 모든 수업에 대해서 시작하는 시간과 끝나는 시간을 정렬해서 가지고 있을 때, 만약 지금 보는 수가 수업이 시작하는 수라면 필요한 강의실이 하나 더 필요할 것이다. 반대로 지금 보고 있는 수가 끝나는 시간이라면 필요한 강의실이 하나 줄어들 것이다. 예를 들어, 1~4까지 하는 수업과 2~5까지 하는 수업이 있고 이 수들을 정렬하여 1 2 4 5라는 수를 가지..

백준[18429] 근손실

2021. 10. 16. 13:30 Algorithm/BOJ

문제 링크 http://icpc.me/18429 풀이 3대 500을 찍고 싶은 헬창이라면 누구나 풀어봐야 할 루틴을 정하는 문제이다. 백트레킹으로 모든 경우를 확인하며 풀 수 있다. 코드 #include #include using namespace std; vector v; int n, k, ans; bool visited[10]; void solve(int cur, int sum) { if (sum < 0) return; if (cur == n) { ans++; return; } for (int i = 0; i < n; i++) { if (visited[i]) continue; visited[i] = true; solve(cur + 1, sum + v[i] - k); visited[i] = false;..

백준[16507] 어두운 건 무서워

2021. 10. 15. 15:10 Algorithm/BOJ

문제 링크 http://icpc.me/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 풀이 2차원 누적합으로 풀 수 있다. 누적합을 이용하지 않고 푼다면 주어진 쿼리를 모두 확인하는 방식으로 푼다면 O(RCQ)로 10억이 넘어가 시간이 터질 것이다. 그렇기 때문에 누적합을 이용하여 쿼리당 O(1)에 구간 합을 구해야 한다. psum [i][j] : 오른쪽 아래 꼭짓점이 (i, j)에 있을 때 내부에 있는 밝기의 합이라고 할 때, psum [i][j]는 ..

백준[3015] 오아시스 재결합

2021. 10. 15. 02:37 Algorithm/BOJ

문제 링크 http://icpc.me/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이 스택을 이용하여 풀 수 있다. 이 문제는 i번째 사람이 1 ~ i -1번째 사람 중에서 몇 명을 볼 수 있는지 확인하면 된다. 여기서 잘 관찰을 해보자면 i번째 사람이 볼 수 있는 사람은 자기보다 큰 사람에 막히지 않은 사람들이다. 그렇다면 사람들을 자기보다 큰 사람이 앞에 있어 볼 수 없는 사람과 볼 수 있는 가능성이 있는 사람들로 나눌 수 있다. 그럼 이제 가능성이 있는 사람들만 가지..

백준[14428] 수열과 쿼리 16

2021. 10. 14. 14:16 Algorithm/BOJ

문제 링크 http://icpc.me/14428 풀이 세그먼트 트리 문제다. 세그먼트 트리에 최솟값을 저장할 때, 인덱스도 포함하여 저장하면 된다. cf) 나는 min도 구현을 해서 사용했지만, stl에 있는 min()을 그냥 사용해도 된다. 코드 #include #include using namespace std; using pii = pair; int arr[100005]; pii tree[400005]; pii min(pii &a, pii &b) { if (a.first < b.first) return a; if (a.first == b.first) { if (a.second < b.second) return a; else return b; } else return b; } pii query(int..

백준[20164] 홀수 홀릭 호석

2021. 10. 14. 13:39 Algorithm/BOJ

문제 링크 http://icpc.me/20164 풀이 전탐색을 하여 풀 수 있다. 처음에 N조건이 10억으로 매우 크기 때문에 전탐색을 생각하기 쉽지 않지만, 이 문제는 n의 자릿수만 중요한 문제이기 때문에, 분할하는 경우가 한 번당 10^2밖에 되지 않는다. 최대 몇 번 쪼갤 수 있을지는 아무리 크게 잡아봤자 10번 미만일 것 같은 직감이 들기 때문에 O(10^3) 보다 작은 시간 안에 풀 수 있다는 믿음을 가지고 풀었다. cf) n & 1의 값이 1이라면 n은 홀수이다. 홀수는 항상 첫번째 비트가 1이고 짝수는 0이기 때문에 이처럼 계산할 수 있다. 코드 #include #include using namespace std; int m = 1e9, M = -1e9; void solve(int n, in..

백준[16401] 과자 나눠주기

2021. 10. 14. 12:38 Algorithm/BOJ

문제 링크 http://icpc.me/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN www.acmicpc.net 풀이 결정문제로 바꿔 이분 탐색을 하여 풀 수 있다. m명에게 길이가 n인 과자를 줄 수 있는지 없는지 판단하는 문제로 바꿔, 길이 n을 이분탐색을 돌리면 된다. 이렇게 풀면 O(NlogN)에 풀 수 있다. 코드 #include int arr[1000006]; int main() { int m, n; scanf("%d %d", &m, &n)..

백준[2239, 2580] 스도쿠

2021. 10. 14. 01:20 Algorithm/BOJ

문제 링크 http://icpc.me/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 2239번과 2580번이 아예 똑같은 문제인데 왜 두 문제가 있는지는 잘 모르겠다. 한번 풀고 복습까지 하라는 백준님의 말씀이실지도... 이 문제는 백트레킹을 사용하여 풀 수 있다. 모든 행, 열, 박스들에 무슨 수가 들어있는지 미리 저장해 두고 빈칸에 백트레킹을 하며 1~9까지 넣어보면 된다. row [n][k] : n열에 숫자 k가 있다는 의미이다. 그리고 끝까지 도달하면 출력을 하고 더 이상 백트레..

백준[14500] 테트로미노

2021. 10. 13. 21:07 Algorithm/BOJ

문제 링크 http://icpc.me/14500 풀이 ㅜ모양을 제외한 나머지 모양은 잘 관찰해보면, 어떤 점 하나를 시작으로 어떻게 가든 한번 갔던 칸으로 돌아가지 않으면서 상하좌우로 4칸을 가는 모든 경우를 나타낸다. 그렇기 때문에 백트래킹을 하며 4칸을 고르면 된다. ㅜ는 예외처리를 하여, 90도씩 돌리는 경우를 4개 고려해주면 된다. 코드 #include #include using namespace std; const int NN = 502; int arr[NN][NN], ans, n, m; int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; bool visited[NN][NN]; void solve(int y, int x, int sum, int sz) {..

백준[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() {..

티스토리툴바