welcome!

이전 포스트순열과 조합 : 조합의 구현 헤헤헤. 사실 계획대로라면 dp 문제를 들어가야했지만 하나를 제대로 하는 것이 중요하다고 생각해요. 그래야 다른 응용문제도 잘 풀 수 있을테니까 말이죠.우리는 조합을 구현하는데 두 가지 방법을 썼습니다.1 첫 번째는 비트스트링과 순열을 활용한 조합방법 ( 010101011100)2 두 번째는 조합 인덱스를 생성해내는 알고리즘 (2,4,6,8,9,10) 이제 나머지 두 방법을 살펴볼건데 3 DFS를 이용한 조합 경우의 수 찾기 (모든 경우의 수도 가능함)4 비트마스크를 이용한 조합 경우 찾기 (모든 경우의 수도 가능함)방법은 알고리즘 문제를 푸는데 자주 사용하는 것입니다. 그치만 너무 귀찮군요. 푸하하... 대신에 문제를 두개 준비해보았습니다.백문이 불여일견이니까....

이전포스트순열과조합: 순열의구현 순열과 조합, 조합의 구현 이전 포스트에서는 순열을 구현해 보았는데요, 순열의 특징은 사전순으로 정렬하는데 있습니다. 그렇다면 조합의 경우는 어떨까요? 우선 조합은 다음과 같은 특징을 같습니다. 비트스트링을 생각해보죠, 해당 원소가 포함되는 곳엔 1, 아닌 곳은 0이 됩니다. 아래그림을 확인해보죠. r-조합은 기본적으로 n개 중 r개를 선택한 원소들의 고유한 집합입니다. 따라서 위와 같은 비트 스트링으로 포함, 비포함으로 표현할 수 있습니다. 자, 우선 모든 조합을 고려해보죠.그러니까 비트스링의 모든 경우의수요. 그렇다면 경우의수는 2^n 가지 입니다. 자, 우선 간단한 예제를 풀어볼까요?예제 41010111 의 다음 비트스링은 뭔가?정답1010111의 다음 비트스트링은 ..

이전포스트순열과조합 순열과 조합의 구현 반복을 허용하는 순열은 저희가 했던 브루트 포스 와 같습니다. 브루트포스 보러가기즉, 4자로 이루어진 비밀번호가 있는데 소문자 알파벳으로 이루어져있음 그 경우의 수가 26^4이죠. 반복을 허용하는 순열의 경우는 이와 같습니다. 자, 근데 이제 어떤 중요한 정보를 얻었다고 합시다.비밀번호의 알파벳들이 겹치지 않는다는 정보요. 그렇다면 26^4 -> 26*25*24*23 으로 경우의수가 줄어듭니다. 그렇담 순열대로 알고리즘을 생성해내는게 더 효율적이겠죠. 근데....순열 알고리즘은 어떤거죠? 생각보다 어렵지 않습니다. 순열을 생성해내는 것은 사전식으로 정렬 하는것과 똑같습니다. 어떤식으로 정렬을 해야할까요a, b, c, d 의 다음순열은 a, b, d, c 입니다. 자..

이전포스트브루트 포스순열과 조합 경우의 수 문제들 중에 대부분이 - 특정 크기의 집합으로부터 고유한 원소들을 순서를 따지면서 뽑으며 구성하는 경우의 수를 말한다. 또, 뽑은 순서는 상관없이 구성하는 경우의 수 문제도 있다. 5명 학생중에 3명을 선택해서 줄을 세우는 경우의 수는? --> 순열 4명 학생중 3명의 학생을 뽑는 경우의 수는? --> 조합 이게 바로 순열과 조합이다순열예제 15명 학생들 중에 3명을 선택해서 일렬로 줄을 세우려고한다. 이 때 이 경우의 수는 몇 개인가?정답우선 어떤 학생을 선택하는지에 대한 그 순서가 중요하다. 첫 번째에 줄서는 애를 뽑기위해선 5가지 경우의수가 있고, 그 친구가 선택되었을 경우에는 이제 두번째로 줄 서는 애를 뽑기위해선 4가지의 경우의 수가 있다. 그리고 두번..

이전 포스트경우의 수 덧셈규칙http://ingyeoking13.tistory.com/162 경우의 수를 이용한 알고리즘완전탐색 (Brute Force)완전탐색은 기본적이면서, 중요한 알고리즘 패러다임인데요. 완전 탐색 알고리즘의 사용할 때, 문제를 해결하는 방식이 굉장히 직설적입니다. "완전" 이라는 단어도 그렇지만, 해당 문제의 조건을 보면 알 수 있습니다 ㅇㅅㅇ.. 완전탐색 알고리즘은 그다지 좋은 알고리즘이 아닙니다. 왜냐하면 시간 복잡도가 지수 시간exponential time이기 때문이죠. 그래서 완전탐색을 사용한다는건 연산 장치의 리소스를 별로 신경쓰면서 문제를 해결하는 쪽은 아니라는 거죠. 일반적인 완전탐색 예로는, 모든 가능한 정답들을 검사해서 진짜 정답을 찾는겁니다. 제일 그럴듯한 정답을..

이전 포스트 보기 경우의 수 곱셈규칙경우의 수 덧셈규칙 The Sum Rule Definition 덧셈규칙어떤 업무를 완료하기까지 n1 가지 수로 된 방법 그리고 n2 가지 수로 된 방법이 있을 때, 업무를 완료 하는데 총 방법수는 n1+n2 이다. 여기서 n1과 n2는 어떠한 공통된 집합(즉, 부분 또는 원소) 이 없다. 덧셈규칙은 곱셈규칙과 전제가 다르다. 곱셈규칙은 어떤 사건이 and 연산자로 묶여있을 때 적용되며, 어떤 사건이 or 연산자로 묶여있으면 덧셈규칙이 적용된다. 아래의 그림을 확인하자. 나의 하루 (오늘)은 밥먹고 똥싸기로 이루어져있으며, 나의 내일은 밥먹거나 똥싸기로 이루어져있다. 작성자가 가족들한테 인정받는 주특기이다.곱의규칙 참고사이트 (곱의 규칙은 집합과 집합의 곱인 cartes..

경우의 수영어로는 Counting이다. 수 세기. 셈법. 조합론. 등 으로도 불린다. 조합론은 무엇인가?1 무엇보다 이산수학에서 굉장히 중요한 분야 중 하나다.2 비교적 최근 수학이다. 17세기 즈음에 도박 확률 문제와 연관되어 정립되었다.3 주로 특정 상태의 어떤 것들을 세는데 사용한다. 예) 2개 이상 연속하는 0을 포함하지않는 0과 1로만 이루어진 n길이의 문자열 갯수는?4 이론적인 곳 외에도 굉장히 다양한 곳에서 사용된다.예) 알고리즘의 복잡도 구하기, IP 수요와 그 할당의 문제, DNA 염기서열 등등의... 앗 복잡해 어찌됐든 알아보기로 하자... 경우의 수 기초컴퓨터를 사용할 때 패스워드를 생성하는 것을 생각해보자. 패스워드를 생성하는데 최소 1개의 숫자를 포함해야하고 최대 8자의 소문자 알..