welcome!

이전포스트순열과조합: 순열의구현 순열과 조합, 조합의 구현 이전 포스트에서는 순열을 구현해 보았는데요, 순열의 특징은 사전순으로 정렬하는데 있습니다. 그렇다면 조합의 경우는 어떨까요? 우선 조합은 다음과 같은 특징을 같습니다. 비트스트링을 생각해보죠, 해당 원소가 포함되는 곳엔 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 입니다. 자..