[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. [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 #13417] 카드 문자열 BOJ #13417, 카드 문자열 문제입니다. 처음에 C로 짜다가 입력 버퍼 관련 문제가 발생해서 한참 헤맸습니다만 Python으로 짜니까 바로 해결했습니다. 입력 버퍼 비우는 테크닉을 알고 있었는데 왜인지 잘 기억이 안 났었네요. 그리고 아직도 왜 안 되는지 모르겠습니다. 구글링도 열심히 하면서 해결하려고 해 보았으나 나중에 다시 시도해보기로 했습니다. 이 문제의 예제에서는 너무나 쉬운 testcase만을 제시하기 때문에, 혼자서 여러 가지 testcase를 만들어서 시험해봐야 합니다. 그리고 bit mask를 이용한 brute force도 문제의 입력 조건 상 시간이 부족하기 때문에 불가능하며 따라서 연역적인 과정을 통해 답을 도출할 수 있어야 합니다. (brute force의 범위를 좁히는 것이 권.. 2020. 7. 25. [BOJ #11659] 구간 합 구하기 4 BOJ #11659, 구간 합 구하기 4 문제입니다. 원소 수 N개의 정수 배열이 주어졌을 때 입력된 구간의 합을 출력하면 됩니다. 프로그램 자체가 간단하지만, 일반적인 방법으로는 시간복잡도가 너무 높아 시간 내에 풀 수 없습니다. 이를 해결하기 위해서는 '누적합'을 이용하면 됩니다. 수학에서 수열을 다룰 때 급수를 이용해 a_n = s_n - s_(n - 1)과 같이 나타내는 것과 동일한 원리를 이용합니다. 이것을 알면 코드 구현은 어렵지 않게 할 수 있겠습니다! 추가적으로 더 효율적인 방식도 있고 다양한 방식이 있으니 검색을 통해 찾아보시거나 직접 떠올려 보시면 큰 도움이 될 것이라고 생각합니다. 간단한 코드이나 제 코드를 첨부하도록 하겠습니다. 더보기 #include #include int main.. 2020. 7. 19. 이전 1 2 3 다음