Algorithm/완전 탐색
-
[Java]순열과 다음 순열Algorithm/완전 탐색 2021. 2. 25. 23:10
*재귀를 이용한 순열 구하기 -> 처음에는, 재귀를 이용하여 모든 순열을 구하였다. 하지만 이전에 공부한 다음 순열을 이용하여도 모든 순열을 구할 수 있다. sskl660.tistory.com/48 [Java] 순열(Permutation) *순열(Permutation) -> 순열이란, 임의의 집합을 순서를 부여하여 차례로 나열하는 것을 말한다. Ex) 이를 테면 집합 {1, 2, 3}중 3개의 원소를 선택한 순열을 구하시오라고 하면, 결과는 {123, 132, 213, 231, sskl660.tistory.com sskl660.tistory.com/54 [Java]다음 순열(Next Permutation) *다음 순열(Next Permutation). -> 다음 순열이란, 말 그대로 해당 숫자의 다음에 ..
-
[Java]다음 순열(Next Permutation)Algorithm/완전 탐색 2021. 2. 25. 22:47
*다음 순열(Next Permutation). -> 다음 순열이란, 말 그대로 해당 숫자의 다음에 올 순열의 수를 의미한다. Ex) {1, 2, 3}에서 3개를 선택하는 경우 순열은 123, 132, 213, 231, 312, 321이 있다. 그렇다면 123 다음에 올 순열은 무엇일까? 132이다. 즉, 123의 다음 순열은 132임을 알 수 있다. *다음 순열 구하기 -> 다음 순열을 구하는 로직은 우리가 무의식적으로 다음 순열을 구하는 로직을 천천히 곱씹으며 구체화시켜보면 가능하다. 우리는 이미 다음 순열을 구하는 방법을 알고 있다!(다만 막상 논리적 순서로 나타내보려 하면 헷갈리고 어려울 뿐이다...) -> 규칙성을 찾기 위해서는, 작은 경우부터 침착하게 내가 어떻게 구하고 있는지 분석해보면 된다...
-
[Java]부분 집합(Subset)과 멱집합(Power Set)Algorithm/완전 탐색 2021. 2. 25. 21:36
*부분 집합(Subset) -> 부분 집합이란 쉽게 말해서 어떤 집합에 포함되는 집합을 말한다. 말 그대로 어떤 집합의 '부분'이 되는 집합이라고 생각하면 된다. Ex) {1, 2, 3}의 부분 집합은 공집합, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 이 있다. *멱집합(Power set) -> 멱집합이란, 해당 집합의 모든 부분 집합을 모아둔 것이다. Ex) {1, 2, 3}의 멱집합은 {공집합, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} 이다. *부분 집합 구하기 -> 부분 집합은 기본적으로 조합을 이용하여 쉽게 구할 수 있다. 어떤 집합에서 개수가 전체 원소의 개수가 n개인 부분 집합을 구한다면, 해당 집합..
-
[Java]중복 조합(Combination with repetition)Algorithm/완전 탐색 2021. 2. 18. 16:35
중복 조합을 완벽하게 이해하기 위해서는 순열, 중복 순열, 조합 세 가지를 모두 정확히 이해하고 공부하는 것이 좋다 sskl660.tistory.com/48?category=879763 [Java] 순열(Permutation) *순열(Permutation) -> 순열이란, 임의의 집합을 순서를 부여하여 차례로 나열하는 것을 말한다. Ex) 이를 테면 집합 {1, 2, 3}중 3개의 원소를 선택한 순열을 구하시오라고 하면, 결과는 {123, 132, 213, 231, sskl660.tistory.com sskl660.tistory.com/49?category=879763 [Java] 중복 순열(Permutation with repetition) *중복 순열(Permutation with repetition..
-
[Java]조합(Combination)Algorithm/완전 탐색 2021. 2. 18. 14:42
조합은 기본적으로 순열을 이해하고 있어야 이해하기 더 수월하다. sskl660.tistory.com/48 [Java] 순열(Permutation) *순열(Permutation) -> 순열이란, 임의의 집합을 순서를 부여하여 차례로 나열하는 것을 말한다. Ex) 이를 테면 집합 {1, 2, 3}중 3개의 원소를 선택한 순열을 구하시오라고 하면, 결과는 {123, 132, 213, 231, sskl660.tistory.com *조합(Combination) -> 조합이란, 임의의 집합을 순서가 없이 선택하는 것을 말한다. Ex) 이를 테면 집합 {1, 2, 3}중 2개의 원소를 선택한 조합을 구하시오라고 하면, 결과는 {12, 13, 23} 총 3가지의 경우의 수가 나온다. ※ 조합이 총 3가지가 나오는 이유..
-
[Java]중복 순열(Permutation with repetition)Algorithm/완전 탐색 2021. 2. 18. 14:13
*중복 순열(Permutation with repetition) ->순열을 이해했다면, 중복 순열은 이해하기 쉽다. 순열을 먼저 이해하도록 하자. sskl660.tistory.com/48 [Java] 순열(Permutation) *순열(Permutation) -> 순열이란, 임의의 집합을 순서를 부여하여 차례로 나열하는 것을 말한다. Ex) 이를 테면 집합 {1, 2, 3}중 3개의 원소를 선택한 순열을 구하시오라고 하면, 결과는 {123, 132, 213, 231, sskl660.tistory.com ->중복 순열이란, 임의의 집합을 순서를 부여하여 차례로 나열하는데 일반 순열과 다르게 집합의 원소를 중복해서 선택할 수 있는 차이가 존재한다. Ex) 이를 테면 집합 {1, 2, 3}중 3개의 원소를 선..
-
[Java]순열(Permutation)Algorithm/완전 탐색 2021. 2. 18. 13:55
*순열(Permutation) -> 순열이란, 임의의 집합을 순서를 부여하여 차례로 나열하는 것을 말한다. Ex) 이를 테면 집합 {1, 2, 3}중 3개의 원소를 선택한 순열을 구하시오라고 하면, 결과는 {123, 132, 213, 231, 312, 321} 총 6가지의 경우의 수가 나온다. ※ 순열이 총 6가지가 나오는 이유는, 위의 예시에서 선택한 3가지 수를 위 박스에 하나씩 넣는 상황을 가정해보면, 첫 번째 자리에는 {1, 2, 3}중 한 가지 숫자 어느것이든 올 수 있다. 두 번째 자리에는 앞에서 이미 한 가지 수를 선택했으므로, 그 선택한 수를 제외한 2가지 숫자가 어느 것이든 올 수 있다. 마지막 자리는 선택이 되지 않은 나머지 한 가지 수가 오게 될 것이다. 따라서 3개의 숫자를 3개선택..