본문 바로가기

알고리즘44

[UCPC] B번 던전 지도, 백준 19543 https://www.acmicpc.net/problem/19543 19543번: 던전 지도 첫 번째 줄에 던전의 행 개수 $N$, 열 개수 $M$, 블록의 종류 $K$가 공백으로 구분되어 주어진다. ($1 \leq N, M \leq 200\ 000$, $1 \leq K \leq 26$) 두 번째 줄부터 $K$개의 줄에 R과 U로만 이루어진 길이 $M$의 문� www.acmicpc.net 문제를 잘 이해하면 쉽게 풀 수 있습니다. 위에서 i번째 행이 i번째 알파벳에 대응되는 행입니다. 아래의 예제에서 A에 대응되는건 RRURRR 이고, B는 RRURRRU, C는 RRRRRRR입니다. 3 7 3 RRRURRR RRURRRU RRRRRRR CBA 주어진 길이 n의 k개의 문자로 이루어진 지도를 그리면 j번째.. 2020. 8. 18.
머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이 머지 소트 트리를 이용한 백준 문제 풀이 수열과 쿼리 1 , 수열과 쿼리 3 , 트리와 색깔 , K번째 수 는 맨 아래를 참고해주세요. 코드 스포일러를 방지하기 위해 접은 글로 풀이를 남겼습니다. 알고리즘에서 c++의 algorithm 헤더에 있는 내장 sort함수는 코드의 간결성과 실수를 줄여줍니다. 그러나, 내장함수가 있다고해서 정렬 알고리즘을 구현할줄 몰라도 되는 것은 아닙니다. 아래의 버블 소트는 알고리즘 입문자들이 대부분 알고있는 정렬 알고리즘으로 O(N^2)의 비효율적인 복잡도로 작업을 수행합니다. 모든 수를 비교하면서 큰 수를 뒤로 보내는 단순한 방식으로 동작합니다. // 버블 소트 for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) {.. 2020. 8. 17.
[BOJ] 백준 10830번: 행렬 제곱 (빠른 거듭 제곱) 먼저 우리는 빠른 거듭 제곱 알고리즘을 알고있습니다. pow(a,y), 즉 a^y 를 구할때 만약 y가 홀수면 a * a^y/2*a^y/2로 분해하여 짝수 거듭 제곱의 반을 구해가면서 O(lgY)의 복잡도로 구할 수 있습니다. int pow(int a, int y) { int x = 1; while (y) { if (y & 1) { x *= a; } a *= a; y /= 2; } return x; } math.h 헤더의 내장 pow를 사용하지 않고 직접 구현하여 쓰는 이유는, 몇몇 문제에서 특정 수로 나눈 나머지 값을 요구하기 때문입니다. 이유는 답이 너무 커지거나 하는 경우에, 보통 1,000,000,007 (1e9+7)와 같은 소수로 나눈 나머지 값을 요구합니다. 소수는 어떠한 수와도 나누어 떨어지.. 2020. 8. 17.
오일러 𝜑(피 또는 파이) 함수, 서로소 개수 구하기 서로소란 1 을 제외하고 공약수가 없는 두 수의 관계입니다. 오일러 피함수 φ(n)은 n이하의 자연수 중 n과 서로소인 자연수의 개수를 의미하는 함수입니다. 예를 들어 φ(6)은 2로 1과 5의 서로소가 있음을 의미합니다. 모든 자연수는 소수들의 (prime) 곱으로 표현 할 수 있습니다. 예를들어 16은 2^4 로 표현할 수 있고 15는 3^1 * 5^1 로 나타낼 수 있습니다. φ(16)은 2, 4, 6, 8, 10, 12, 14, 16을 제외한 나머지 자연수와 서로소입니다. 여기서 알 수 있는 사실은, 자연수를 구성하는 소수들의 배수는 전부 서로소가 아닙니다. 즉, φ(16) = 16 - (16/2) = 8개로 구할 수 있습니다. ( n 이하의 k의 배수의 개수는 n/k로 구할 수 있습니다, 나머지.. 2020. 8. 13.
[BOJ] 백준 1028번: 다이아몬드 광산 https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net R, C 가 750으로 (i, j) 좌표에서 우측 하단으로의 대각선 길이 DP[i][j][0], 좌측 하단으로의 대각선 길이 DP[i][j][1], 좌측 상단으로의 각선 길이 DP[i][j][2], 우측 상단으로의 대각선길이를 구해놓고 모든 좌표에 대하여 O(R*C*750*4)의 복잡도로 가능한 다이아몬드 크기를 구할 수 있습니다. (시간초과가 날것 같지만 가지치기를 통해 충분히 시간을 줄일 수 있습니다.) #include #include #i.. 2020. 8. 12.

티스토리툴바