조합

[알고리즘]#6_백 트래킹 백 트래킹 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 백 트래킹 백 트래킹 알고리즘은 문제 해결을 위해 여러 후보 해결책들을 점진적으로 탐색하며, 현재 선택한 경로가 해결책으로 이어질 수 없다고 판단되면, 이전 단계로 돌아가(백 트래킹) 다른 경로에 대한 탐색을 시도하는 방법입니다. 이처럼 백 트래킹 과정을 통해 문제의 모든 후보 해결책들을 효과적으로 탐색할 수 있습니다. 특히, 백 트래킹 알고리즘은 모든 가능한 해결책 후보를 조합적으로 탐색해야 할 때, 최고의 성능(시간, 자원)을 보여줍니다. 따라서, 백 트래킹 알고리즘은 (1) 미로 찾기, (2) 스도쿠, (3) 순열, (4) 조합, (5) N-Queens 문제, 그리고 (6) 그래프의 탐..

[BOJ알고리즘, C++]#15650_N과 M(2) BOJ 알고리즘 문제 풀이, 15650문제 N과 M(2) 조합 문제를 백 트래킹을 활용해 해결하는 방법에 대해 알아보겠습니다. Overview 문제 풀이 코드 #0. 문제 #1. 풀이 1. 백 트래킹 // 링크 조합 문제는 백 트래킹 알고리즘을 활용하는 대표적인 문제 중 하나입니다. 백 트래킹 알고리즘은 문제 해결을 위해 여러 후보 해결책들을 점진적으로 탐색하며, 현재 선택한 경로가 해결책으로 이어질 수 없다고 판단되면, 이전 단계로 돌아가 다른 경로에 대한 탐색을 시도하는 알고리즘입니다. 이를 통해, 효율적으로 문제의 모든 가능한 후보 해결책들을 탐색할 수 있습니다. 2. 조합 [확률과 통계]#2 조합, nCr [확률과 통계]#2 조합, nCr 확률과..

[확률과 통계]#3_이항 정리, 파스칼 삼각형 확률과 통계 과목의 "이항 정리"와 "파스칼 삼각형"에 대해 공부합니다. Overview 이항 정리 파스칼의 삼각형 #0. 이항 정리 1. 이항 정리? 이항 정리(Binomial Theorem)는 이항식의 거듭제곱을 이항 계수를 계수로 하는 일련의 단항식들의 합으로 전개하는 정리입니다. 2. 다항식 이항정리에서 소개되는 (a+b)ⁿ는 n차 다항식으로, 전개하면 위와 같은 형태로 나타납니다. 다항식 (a+b) ³을 전개해 보겠습니다. 이때, 단항식의 계수들을 정리하면, 1, 3, 3, 1이 나옵니다. 우리는 간단한 방법을 통해 다항식을 통해 전개하여 나오는 계수들을 찾아낼 수 있습니다. 3. 이항 계수와 조합의 관계 가장 먼저, (a+b)³를 (a₁+b₁) x..

[확률과 통계]#2 조합, nCr 확률과 통계 과목의 "순열과 조합"에 대해 공부합니다. Overview 조합과 순열의 차이점 조합의 성질 같은 것이 있는 순열 vs 조합 중복 조합 조합과 순열의 차이점 1. 조합? Details 확률에서 조합이란, '서로 다른 n개 중에서 순서에 상관없이 r개를 선택하는 것'입니다. 여기서 우리가 주목할 점은 "순서"입니다. 반장, 부반장, 그리고 주번 자리에 각각 영수, 철수, 그리고 민수를 앉히는 경우의 수는 3!입니다. 여기서 조건을 바꿔보죠. 반 대표 3명을 세 사람 중에서 뽑는 경우의 수는? 1입니다. 왜 다를까요? "순서"가 결과에 영향을 미치는가? 바로 이 점에서 "순열"과 "조합"의 차이점을 찾을 수 있죠. 순열 : 서로 다른 n개 중 r개를 뽑아서 주어..