[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 #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 #10816] 숫자 카드 2 BOJ #10816, 숫자 카드 문제입니다. 기본적으로 이진 탐색을 이용하는 문제이고 다른 기초적인 이진 탐색 문제와 다르게 이진 탐색을 여러 번 해야 하는 문제입니다. 그래서인지 시간 초과로 틀리는 케이스가 많으며 정답률도 낮은 편입니다. 1. 숫자가 있는지 판단하기 기본적인 이진 탐색 알고리즘을 이용하면 되므로 쉽게 짤 수 있습니다. int M; scanf("%d", &M); int *toFind = (int *)malloc(sizeof(int) * M); for (int i = 0; i < M; i++) { scanf("%d", &toFind[i]); idx = findIdx(card, N, toFind[i]); if (idx == -1) printf("0 "); else printf("%d ", .. 2020. 7. 27. [BOJ #1543] 문서 검색 BOJ #1543, 문서 검색 문제입니다. 입력으로 문서(문자열)와 단어가 주어집니다. 문서 속에서 단어가 총 몇 번 등장하는지 출력하면 됩니다. 단, 일반적인 방법으로 앞에서부터 탐색하면 안 됩니다. 자세한 사항은 예시를 참고해서 이해하는 것이 편합니다. 예를 들어, 문서 doc == 'abababa'이고 찾으려는 단어 word == 'ababa'이면 doc[0:len(word)] == doc[2:2+len(word)] == word입니다. 이런 상황에서 doc[0:len(word)]와 doc[2:2+len(word)]의 두 가지를 모두 count하면 안 됩니다. 둘 중 하나만 count해야 합니다. 사실 이것을 설명하면서 doc에 doc[index:index+len(word)]로 접근한 것이 이 문제.. 2020. 7. 14. [BOJ #15965] K번째 소수 BOJ #15965, K번째 소수 문제입니다. 문제는 간단합니다. 입력으로 K가 주어지면 K번째 소수를 찾아 출력하면 됩니다. 그러나 K의 범위에 따라 서브태스크가 여럿 존재하는 것으로 보아 K의 범위가 문제풀이에 중요하게 작용할 것이라고 예측할 수 있습니다. 이 문제에서는 최대 50만번째 소수를 2초 안에 찾아내야 하므로, 일반적인 방법으로는 시간이 부족할 것으로 보입니다. 1. 소수 구하기 1번째 방법 2 이상의 자연수 N에 대해, N이 1과 N을 제외하고 어떤 자연수로도 나누어 떨어지지 않을 때 그 수를 소수라고 합니다. 가장 원시적인 방법으로는 다음 코드가 가능하겠습니다. def is_prime(N): if N == 2: return True else: for i in range(2, N): if.. 2020. 7. 13. 이전 1 다음
