이전포스트순열과조합 순열과 조합의 구현 반복을 허용하는 순열은 저희가 했던 브루트 포스 와 같습니다. 브루트포스 보러가기즉, 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..

백준 1, 2, 3 더하기본문보기https://www.acmicpc.net/problem/9095 이번 문제는 경우의 수 구하는 문제이다. 해당문제는 n중 for문으로도 풀 수 있고, 재귀를 이용한 dfs 탐색(트리탐색) 으로도 풀 수 있다. 하지만 또 dp풀듯이도 풀 수 있다. dp 풀듯이라는 뜻은 어쨋든 굉장히 큰 길이 또는 크기를 구하는 문제이지만 서도 낮은 숫자부터 차근차근 sub-answer들을 구해내서 귀납적으로 큰 값에 대한 답 real-answer를 구하는 것이다.이게 바로 sub-problem , overlapping 이라는 개념인데 나는 아직 이 개념에 익숙치 않아서 이 블로그를 포스팅 하는 이유이기도 하다. 이번문제에서 숫자는 어떻게 완성될까? 우선 이전 dp 문제들의 접근법을 확인해..

백준 2*n타일링 2본문보기https://www.acmicpc.net/problem/11727 dp문제. 경우의 수를 구하는 문제이다. 이 문제는 2*n 타일링 의 확장판 같은 문제이다. (브루드워?) 링크참조이번엔 약간 다른것이 있는데 2*2 타일이 있기 때문에 a[n-2]의 경우의 수가 2개가 된다.길이가 3일때를 생각해보자. 2까지 완성된 경우 세로로 길때 완성되는 경우와 1까지 완성된경우 가로로 긴 두개를 쌓아서 완성된경우, 2*2로 완성된경우 가 있다.an 이 n 까지 완성된 블록의 경우의 수라고하자. a3 은 a2+ a1+ a1 으로 표현할 수 있다.3부터 차근차근 경우의수를 기록해나가면서 다음 길이의 블록의 경우의 수를 구하려고하면 된다.낮은 상태에서 부터 높은 상태로 까지의 값을 기로고해나..

백준 2*n 타일링본문보기https://www.acmicpc.net/problem/11726 dp문제. 경우의 수 문제이며, 점화식을 구하는 문제이다. 이 문제의 형식은 다음 문제와 유사하다. n 길이의 비트스트링 문자열의 경우의 수를 구하여라. 단 0이 두개 이상 연속하면 안된다.우선 n길이의 비트스트링 문자열 경우의 수는 2^n 이다. 그런데 0이 연속되면안된단다. 확실히 2^n보다 작을것 같지만 경우의 수가 몇개인지 모른다. 여기서 접근법은 이전 문제(1로만들기)처럼 차근차근 접근하는 것이다. 문자열 3일 때의 경우의 수를 생각해보자.문자열 3일때의 경우의수는 3번째 수가 1인경우와 3번째 수가 0인경우로 표현할 수 있다. 3번째 수가 0일때에는 반드시 2번째 수는 1이 되어야한다. 그리고 물음표인..

백준 1463 1로만들기https://www.acmicpc.net/problem/1463 해설dp로 불어보았다. 문제를 딱 봤을 때 우선 음.. 확실히 3으로 나누는 것이 이동수를 크게 줄이는 이득부분이니까 나누는게 좋다. 라고 생각했고, n에서 1까지 내려가는 것을 연산하였다.그런데 반례는 예제에서도 있듯이 10은, 10 ->9->3->1 이 최소이동이며 내가 생각한대로 하면10->5->4->2->1 이므로 이동횟수가 하나 더 많았다. dp의 배열을 이용하면서 1에서부터 차근차근 해당수로 올라가면서 1에서부터의 최소거리를 구한다면 우리가 원하는 방식으로 알고리즘은 동작한다. 어떤 수 n는 default로 하나 작은 수[n-1] 에서 1을 더한만큼의 거리를 가진다. 그리고 그게 2로 나누어지고 d[n-1..