본문 바로가기
반응형

분할 정복5

C, C++ - 1 비트 개수 세기 (Bit Counter) C, C++ 전체 링크 삼성 C형 전체 링크 주어진 숫자에 대해 비트 단위로 1이 몇 개 인지 세는 함수를 만들어보자. 먼저 비트 단위로 출력하기를 이용하여 아래의 코드를 실행해보자. #include #include using namespace std; typedef long long int ll; template void printBitNumber(T number) { unsigned int bitSize = sizeof(number) * 8; T mask = (1ull) = 1; if (i % 8 == 7) printf(" "); } putchar('\n'); } int main(void) { ll bit = 1234123412341234123; printf("bit : "); printBitNumb.. 2023. 7. 29.
BOJ 2630 : 색종이 만들기 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2630 색종이의 판단은 시작 좌표 (sr, sc) 그리고 size를 이용하여 판단한다. 아래의 check 함수는 비정상적인 색종이인 경우 -1을 return하고, 정상적인 경우 MAP[sr][sc]를 return한다. MAP[sr][sc]가 0이면 WHITE 색종이, 1이면 BLUE 색종이가 된다. int check(int sr, int sc, int size) { int tmp = MAP[sr][sc]; for (int r = sr; r < sr + size; r++) for (int c = sc; c < sc + size; c++) if (MAP[r][c] != tmp) return -1; return tmp; } 가장 큰 색종이부.. 2021. 4. 25.
BOJ 10830 : 행렬 제곱 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10830 곱셈 문제처럼 이진수의 원리를 그대로 적용하여 해결하였다. 행렬의 곱은 A = B * C 일 때, A[r][c] = ∑B[r][k] * B[k][c]를 이용한다. #include typedef unsigned long long int ull; int N; ull B; int matrix[7][7]; int ans[7][7]; void multiply(int matrixA[][7], int matrixB[][7]) { int temp[7][7] = { 0 }; for (int r = 1; r 2021. 3. 25.
BOJ 1629 : 곱셈 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1629 A를 B번 곱할 때, B가 최대 2,147,483,647이므로, 2,147,483,647번 곱하면 연산 비용이 너무 많이 든다. 즉, O(B)의 비용이 든다. 하지만 분할 정복을 이용하면, O(logB)로 해결 가능하다. 만약 A를 100번 곱해야 한다고 생각해보자. A100 = A50 * A50 A50 = A25 * A25 A25 = A12 * A13 A12 = A6 * A6 A13 = A6 * A7 A6 = A3 * A3 A7 = A3 * A4 A3 = A * A2 A4 = A2 * A2 A2 = A * A 따라서, 재귀 함수를 이용해 답을 (log100)번만에 찾을 수 있다. typedef unsigned long long.. 2021. 3. 24.
BOJ 2751 : 수 정렬하기 2 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2751 참고 - 머지 소트 Merge Sort 여러 정렬 방법이 있겠지만, 여기에서는 merge sort로 풀어보자. #include int N; int a[1000000 + 50000]; int b[1000000 + 50000]; void merge(int start, int end) { int mid, i, j, k; mid = (start + end) >> 1; i = start; j = mid + 1; k = 0; while (i 2021. 2. 16.
반응형

티스토리툴바