그래프 문제에서 점 하나는 무엇일까
그래프 문제를 보면 BFS나 최단 경로부터 떠올릴 때가 있다. 그런데 코드를 고르기 전에 그림부터 잘못 그렸을 수도 있다. 점 하나가 무엇이고 선 하나가 무엇인지 설명하지 못하면, 정확한 알고리즘으로 엉뚱한 답을 구할 수 있다.
그래프 문제를 보면 BFS나 최단 경로부터 떠올릴 때가 있다. 그런데 코드를 고르기 전에 그림부터 잘못 그렸을 수도 있다. 점 하나가 무엇이고 선 하나가 무엇인지 설명하지 못하면, 정확한 알고리즘으로 엉뚱한 답을 구할 수 있다.
1. 조건부확률 확률의 곱셈정리 ex) 주사위 두번 던져, 첫번째는 1의눈, 두번째는 3의 눈일 확률?첫번째: 1/6 두번째: 1/6 = 1/6*1/6 = 36ex) 5개의 공, 3개의 당첨제비가 있는 주머니에서 두번 모두 당첨제비의 확률은?3/5 * 2/4 = 3/10여기서는 앞의 사건이 뒤의 사건에 영향을 받음. 즉, A,B의 사건에서 P(B)가 아니라 P(B|A)로 표기해야함. 2. 독립사건과 종속사건 두사건이 독립: 베이즈정리 조건부확률의…
주사위 1개 던질 때 짝수의 눈이 나오는 확률은?3/6 = 1/2시행: 주사위 1개를 던진다표본공간: {1,2,3,4,5,6} 사건: 짝수의 눈이 나온다. 1. 확률의 기초개념1) 시행과 사건(3) 사건: 시행의 결과로 나타난 표본공간의 일부(부분집합)ex) 주사위 한 개를 던지는 시행에서 짝수의 눈이 나오는 사건:(4) 근원사건: 표본공간의 부분집합 중에서 한 개의 원소로 이루어진 것ex) 주사위 한 개를 던지는 시행의 근원사건: {1}, {2},…
서로 다른 대상, 서로 다른 자리: 중복순열 서로 같은 대상, 서로 다른 자리: 중복조합 서로 다른 대상, 서로 같은 자리: 집합의 분할 서로 같은 대상, 서로 같은 자리: 자연수의 분할 문제: 두 집합 X={1,2,3,4}, Y={1,2,3,4,5,6,7}에 대하여 다음 조건을 만족하는 함수 f:x -> y의 개수를 구하여라(1) 함수: x->y로 x는 무조건 가야함. -> 중복순열 (7^4)(2) i!=j이면 f(i)…
자연수의 분할 1) 자연수 n을 k개의 자연수의 합으로 쪼갠다 : P(n,k) (Partition)2) P(n,1) = 1 P(n,n) = 1 문제: 자연수 8을 4개의 자연수로 분할하는 방법의 수를 구하시오.P(8,4) => 내림차순으로 수작업!8 = 5+1+1+1 = 4+2+1+1 = 3+3+1+1 = 3+2+2 = 2+2+2+2이것은 4의 분할과도 같음. 작은 숫자(8보단 4)가 더 쉬움.4 = 3+1, 2+2 = 2+1+1 = 1+1+1+1언제쓰냐?…
이항정리 으로 나올 수 있는 것을 모두 정리한 것.ex) 여기서 컴비네이션은 이항계수. 일반항: 문제: 에서 의 계수를 구하시오 일반항, 즉 5-r = 3, r=2가 됨. 즉, 문제: 을 이항정리를 이용하여 전개하시오. 문제: 을 이항정리를 이용하여 전개하시오.우선 일반항 구하기: 여기서 (계수가 2를 구하는 것이므로)즉, 문제: 의 전개식에서 의 계수가 1440일때, 양수 a의 값을 구하시오.1) 일반항 구하기:…
중복조합 서로다른 n개에서 중복을 허락하고 r개를 뽑는 경우의 수: 5는 두가지 ‘종류’ 중 한 개의 구분, 그중에 뽑는 4가지. = => 서로 다른 2개에서 중복을 허락하여 4개를 택하는 중복조합의 수 = 4개의 과일과 (2-1)개의 막대를 일렬로 나열하는 경우의 수 = (4+2-1)개의 자리에서 4개의 과일을 놓을 자리 4개를 선택하는 조합의 수 문제: 1,2,3,4의 번호가 적힌 카드…
조합 n개중 r을 뽑아서 나열을 안하는 경우. 공식1) 2) , 3) 이항정리 참조 tip: 자동배열 = 조합 (ex: 키큰 순서 나열 / 세 자리 자연수) 문제: 1,2,3,4의 번호가 적힌 4장의 카드 중에서 서로 다른 2장의 카드를 택하는 경우의 수를 구하시오. 문제: 다음 식을 만족하는 자연수 n또는 r의 값을 구하시오.(1) => 4 혹은 5(2) 문제: 10명의…