[BOJ #2110] 공유기 설치 BOJ #2110, 공유기 설치 문제입니다. 이전에 풀어서 맞은 문제였는데 얼마 전 재채점이 되면서 틀렸길래 다시 풀어보면서 글을 작성하기로 했습니다. 접근 가장 인접한 두 공유기 사이의 거리가 최대가 되도록 하는 '배치'를 찾는 것은 상당히 어려워 보입니다. 모든 배치를 다 검토해 보는 것은 2 N >> C; for (int i = 0; i > x[i]; sort(x, x + N); int l = 1, r = x[N - 1], mid; do { mid = (l + r) / 2; if (!b(mid)) r = mid; else l = mid + 1; } while (l != mid); cout = C; } 매우 간단한 코드로 이 문제를 해결할 수 있습니다. 2021. 1. 5. [BOJ #1700] 멀티탭 스케줄링 BOJ #1700, 멀티탭 스케줄링 문제입니다. 계속 알고리즘을 풀긴 풀었지만 귀찮은 탓에 블로그는 못 썼습니다. 학교 과제로 바쁘기도 하고, 역시 24학점은 아무나 듣는 게 아닌 것 같습니다. 다음 학기는 학점을 좀 널널하게 들으면서 편한 마음으로 학교를 다니기로 생각했습니다. 그러면서 겨울방학부터 군입대 전까지는 자기계발에 몰두하려고 합니다. 꽤 오랜 시간 고민했던 문제고, 그리디는 참 어렵습니다. 물론 이 문제의 그리디 판단 기준은 상당히 간단해서 해설을 본다면 누구나 바로 이해하겠지만, 꾹 참고 혼자 생각해 보느라 꽤 크게 돌아서 온 것 같습니다. 그리디는 구현이 어렵다기보단, 문제가 그리디로 풀린다는 사실을 인지하는 것이 정말 어렵습니다. 접근 일단 기본적으로 쉽게 생각할 수 있는 사실들을 떠올.. 2020. 11. 24. [BOJ #5641] 겉보기에 쌍둥이 소수 BOJ #5641, 겉보기에 쌍둥이 소수 문제입니다. 작성시각 기준 푼 사람이 16명밖에 되지 않는 문제입니다만 그렇게 어렵지는 않았습니다. 입력으로 n과 t가 주어지면 n자리 겉보기에 쌍둥이 소수를 '아무거나' 출력하면 됩니다. 그런데 3500 2020. 8. 4. [BOJ #1629] 곱셈 BOJ #1629, 곱셈 문제입니다. 문제의 이름과는 다르게 정답률이 낮고 살짝은 까다로울 수 있는 문제입니다. 이 문제는 분할정복법으로 풀게 되며(Divide & Conquer), 따라서 재귀를 사용합니다. 또 (A * B) % C == ((A % C) * (B % C)) % C임을 알고 있어야 합니다. 저는 처음에 이 공식을 몰랐으나 아주 예전 BOJ #10430, 나머지 문제를 푼 것이 기억나 사용하게 되었습니다. 추가적으로 분할정복만으로는 시간 초과가 떠서 메모이제이션(memoization)까지 사용하였습니다. 1. main에서의 array for memoization 생성 int cnt = 0; int main(void) { int A, B, C; scanf("%d %d %d", &A, &B, .. 2020. 8. 2. [BOJ #1051] 숫자 정사각형 BOJ #1051, 숫자 정사각형 문제입니다. 입력 범위를 general하게 바라보면 계산량이 좀 많습니다만 입력 범위가 매우 작아서(N, M M) ? N : M; for (int side = max; side >= 2; side--) { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (!(i + side - 1 < N && j + side - 1 < M)) continue; else { if (isItSquare(matrix, i, j, side)) return side; } } } } return 1; } int main(void) { int N, M; scanf("%d %d", &N, &M); int** matrix = (int**).. 2020. 7. 31. [BOJ #1449] 수리공 항승 BOJ #1449, 수리공 항승 문제입니다. 간단하게 그리디 알고리즘을 이용하는 문제입니다. 테이프의 길이와, 파이프에서 물이 새는 위치가 주어지면 물이 새는 모든 위치를 막으려면 최소 몇 개의 테이프를 이용해야 하는지를 출력하는 문제입니다. 단, 테이프는 자를 수 없으며 무한 개 가진 것으로 간주합니다. 추가적으로 물이 새는 지점의 좌우로 0.5cm까지 테이핑해야 물을 막은 것으로 간주합니다. 따라서 가령 1과 3에서 물이 새고 있고 이것을 하나의 테이프로 막고자 하면 1의 왼쪽 0.5, 사이 거리 3 - 1 == 2, 3의 오른쪽 0.5로 길이 3 이상의 테이프가 필요한 것이죠. 즉 길이 n의 테이프로는 최대 간격이 n - 1인 구멍까지만 막을 수 있습니다. 그리고 이 문제 한참 헤맸던 것이... t.. 2020. 7. 29. 이전 1 2 3 다음
