순열과 조합 (백준 N과 M 시리즈)
순열과 조합 순열(Permutation) / 조합(Combination)에서 개수를 구하는 경우에는 ▶ P(n, r) = n × (n - 1) × (n - 2) × ... × (n - r - 1) = n! / (n - r)! 상황에 따라서는 주어지는 Data가 나올 수 있는 모든 경우가 필요할 수 있다. - 순서 의미 O → 순열 - 순서 의미 X → 조합 - 중복 허용 순열 접근 방식 ① P(4, 3) = 4 x 3 x 2 ② P(4, 3) = 4개 중 1개 선택 x 3개 중 1개 선택 x 2개 중 1개 선택 ③ 재귀탐색하는 모습은 아래와 같다. [1, 2, 3, 4] 에서 『1』 선택 [2, 3, 4] 에서 『2』 선택 [3, 4] 에서 『3』 선택 ▶ 1 2 3 [3, 4] 에서 『4』 선택 ▶ 1..
2021. 5. 8.
[구간합] Sum of sub-matrix가 무엇이고, 어떻게 하는 것일까?
Sum of sub-matrix 란? N × N와 같은 2차원 배열상에서 특정 영역의 합을 의미한다. 위에서 표시한 4 × 2 크기의 사각형이 가지고 있는 영역의 합은 어떻게 구할까? Brute Force 방식으로 구한다면 아래와 같이 구할 수 있다. #include const int N = 7; int main() { int map[N][N] = { {0, 0, 0, 0, 0, 0, 0}, {0, 1, 2, 3, 4, 5, 6}, {0, 2, 2, 2, 2, 2, 2}, {0, 3, 3, 3, 3, 3, 3}, {0, 4, 4, 4, 4, 4, 4}, {0, 5, 5, 5, 5 ,5 ,5}, {0, 6, 6, 6, 6, 6, 6}, }; int sx, sy, ex, ey; sx = 2, sy = 4; ..
2021. 5. 3.
