-
Permutation Power Set (순서를 구분하는 멱집합)FrontEnd/알고리즘 2021. 3. 6. 05:09
input:
배열 [1, 2, 3]
output:
(원 배열의 멱집합에 순서 배리에이션까지 더해진 배열 [1, 2] ≠ [2, 1])
[],
[1], [2], [3],
[1, 2], [2, 1], [1, 3], [3, 1], [2, 3], [3, 2],
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
순열 멱집합이라는 명칭이 실제로 있는 것인지는 잘 모르겠다.
일반적인 PowerSet은 순서를 구분하지 않는 부분 집합을 가리키는데,
프로그래머스에서 완전탐색 > 소수 찾기 풀이를 하다가 순서를 구분하는 부분 집합이 필요해졌다.
인풋으로 1~7개의 숫자가 주어지고, 주어진 숫자로 만들 수 있는 수 중 소수인 것이 몇 개인가를 묻는 문제다.
내가 생각했던 풀이는 이런 식이었다.
인풋으로 0, 1, 7이 주어지는 경우,
1. 우선 멱집합을 만든다.
0, 1, 7, 01, 70, 17, 071
2. 멱집합 요소들에 순열 배리에이션을 추가해준다.
0, 1, 7, 01, 10, 07, 70, 17, 71, 017, 071, 107, 170, 701, 710
3. 그러면 이 순열멱집합 중에서 중복인 것을 골라내고
(1과 01은 같은 수다. 그리고 인풋으로 들어오는 숫자에는 중복이 있을 수 있다.)
0, 1, 7,
01,10,07,70, 17, 71,017,071,107, 170, 701, 7104. 남은 숫자가 소수인가를 판별한다.
0, 1,7,70,17, 71,107, 170, 701, 710PowerSet
멱집합은 예전에 파이썬으로 똑같은 문제로 삽질했던 기억을 되살려서 산술시프트를 이용했다.
function genPowerSet(arr) { const result = []; const len = arr.length; for (let i = 0; i < 2**len; i++) { const eachSet = []; for (let j = 0; j < len; j++) { if (((i >> j) % 2) == 1) { eachSet.push(arr[j]); } } result.push(eachSet); } return result; }아마도 다음에 봤을 때도 의아해할 부분은 아래 두 군데.
for (let i = 0; i < 2**len; i++) {원 배열에 요소 하나가 늘어날 때마다 PowerSet 개수는 2배가 되기 때문에 전체 경우의 수는 2**요소개수 가 된다.
(직전까지 만들어진 PowerSet을 복사해서 한 쪽에는 새 요소를 집어넣고, 한 쪽은 그냥 유지해줘야 하므로 2배다.)
for (let j = 0; j < len; j++) { if (((i >> j) % 2) == 1) {전체 요소가 3개일 때 PowerSet을 만든다면 전체 경우의 수는 8이 되고, 각 요소들은 4번씩 등장해야 한다.
한 요소가 없고, 있고를 끝내면, 다음 요소는 이 경우의 수에 다시 없고, 있고를 한 사이클로 가져간다.
요소1: X O X O X O X O
요소2: X X O O X X O O
요소3: X X X X O O O O
혹은 이렇게 (이 경우 (((i >> j) % 2) == 0)로 써야한다. 전체 다 포함된 집합이 제일 앞에 등장한다.
요소1: O O O O X X X X
요소2: O O X X O O X X
요소3: O X O X O X O X
위에서 i가 2**요소 개수만큼 for 루프를 도는 동안, 이 숫자를 이용해서 위의 정오표(?)를 만들어야 한다.
0 1 2 3 4 5 6 7 X O X O X O X O X X O O X X O O X X X X O O O O 각자 자기 사이클일 때 포함되면 된다.
요소1은 2, 4, 6, 8번째에 포함된다.
요소2는 2사이클을 한 단위로 봤을 때 2, 4번째에서,
요소3은 4사이클을 한 단위로 봤을 때 2번째에서 포함된다.
i >> j는 i를 2진수로 표현했을 때, j만큼 비트를 오른쪽으로 밀라는 뜻이다.
8 >> 1이라면, 8은 00001000이니까 이걸 1칸 밀면 00000100, 즉 4가 된다.
7 >> 1이면 0000111을 미니까 0000011, 3이 된다.
이걸 표현해보면 첫번째 요소는 이렇게 되고
i 0 1 2 3 4 5 6 7 i 2진수 0 1 10 11 100 101 110 111 j == 0 0 0 0 0 0 0 0 0 >> 결과
2진수0 1 10 11 100 101 110 111 결과 0 1 2 3 4 5 6 7 % 2 0 1 0 1 0 1 0 1 정오 X O X O X O X O 두 번째 요소는 이렇게
i 0 1 2 3 4 5 6 7 i 2진수 0 1 10 11 100 101 110 111 j == 1 1 1 1 1 1 1 1 1 >> 결과
2진수0 0 1 1 10 10 11 11 결과 0 0 1 1 2 2 3 3 % 2 0 0 1 1 0 0 1 1 정오 X X O O X X O O 마지막 요소는 이렇게 된다.
i 0 1 2 3 4 5 6 7 i 2진수 0 1 10 11 100 101 110 111 j == 2 2 2 2 2 2 2 2 2 >> 결과
2진수0 0 0 0 1 1 1 1 결과 0 0 0 0 1 1 1 1 % 2 0 0 0 0 1 1 1 1 정오 X X X X O O O O 같은 방식으로 요소가 4개라면 16개의 조합이 가능하고,
첫 번째 요소는 X O,
두 번째 요소는 X X O O,
세 번째 요소는 X X X X O O O O,
네 번째 요소는 X X X X X X X X O O O O O O O O 로 포함되어야 한다.
각 요소마다 전 요소 사이클의 2배의 사이클로 돌아가야 하므로
다음 요소로 넘어갈 때마다 인덱스 번호를 절반으로 나눠주면 된다.
비트의 오른쪽을 하나씩 빼면 값이 절반으로 줄어들고, 빠진 값만큼은 숫자가 변하더라도 같은 사이클로 돌아간다.
**
2번째 요소의 인덱스는 1이니까, i >> 1를 하면 오른쪽 비트 하나가 빠진다.
0(0 -> 0), 1(1 -> 0)은 0, 2(10 -> 1), 3(11 -> 1)은 1. 4(100 -> 10)와 5(101 -> 11)은 0, 6(110 -> 11), 7(111 -> 11)은 1.
비트 하나가 돌아가는 동안인 2만큼은 나머지 숫자가 변화하지 않으므로 2번째 요소는 2의 사이클을 갖게 된다.
마찬가지로 3번째 요소의 인덱스는2이니까 i >> 2를 하게 되면 오른쪽 비트 2개가 빠진다.
0(0 -> 0), 1(1 -> 0), 2(10 -> 0), 3(11 -> 0)까지는 2자리 미만이므로 비트를 2개 빼면 0.
4(100 -> 1), 5(101 -> 1), 6(110 -> 1), 7(111 -> 1)은 1.
8(1000 -> 10), 9(1001 -> 10), 10(1010 -> 10), 11(1011 -> 10)은 0.
9(1100 -> 11)부터 11(1111 -> 11)까지는 다시 1.
비트 두개가 돌아가는 동안인 4만큼은 나머지 숫자가 변화하지 않으므로 3번째 요소는 4의 사이클을 갖게 된다.
**
그러면 전체 루프가 돌아가는 동안 계속 자신의 사이클을 유지하게 된다.
Permutation
숫자를 붙이는 부분과 재귀 부분을 함수로 나누어서 처리했다.
function genPPSet(arr) { function call(s, arr) { if (arr.length === 0) { return [s]; } return arr.map((x) => String(x) + s); } let result = []; function loop(arr, temp = []) { if (arr.length < 1) { result = result.concat(temp); } for (let i in arr) { const newArr = arr.slice(); const element = newArr[i]; newArr.splice(i, 1); const r = call(element, temp); loop(newArr, r); } } loop(arr); return result; }기본적인 로직은 이렇게 생각했다.
배열: [1, 2, 3]가 있을 때, for 루프의 각 루프마다 i번째 요소를 제거하고, 제거한 요소를 그때까지 만들어진 순열값에 붙이는 재귀로 처리한다.
순열값 [], 남은 요소 [1, 2, 3]
i == 0
순열값 [1], 남은 요소 [2, 3]
i == 0
순열값 [12], 남은 요소 [3]
i == 0
[123]
i == 1
순열값 [13], 남은 요소 [2]
i == 0
[132]
i == 1
순열값 [2], 남은 요소 [1, 3]
i == 0
순열값 [21], 남은 요소 [3]
i == 0
[213]
i == 1
순열값 [23], 남은 요소 [1]
i == 0
[231]
i == 2
순열값 [3], 남은 요소 [1, 2]
i == 0
순열값 [31], 남은 요소 [2]
i == 0
[312]
i == 1
순열값 [32], 남은 요소 [1]
i == 0
[321]
먼저 순열값을 만들어줄 함수를 작성했다.
요소를 순열값에 붙여서 점차로 완성하는 방식이라서 맨 처음에는 순열값 배열에 값이 없다. 그 경우는 초기값을([s]) 리턴하도록 했다.
function call(s, arr) { if (arr.length === 0) { return [s]; } return arr.map((x) => String(x) + s); }그리고 재귀함수.
arr.length가 1보다 작아지면 남은 요소가 없는 것이니까 result에 추가하도록 했다.
외부 전역변수 안 끌어오고 최대한 함수 내에서 처리하고 싶었는데,
처음에 생각했던 로직이 분기하면서 각 순열을 만들어나가는 방식이라서 중간에 리턴 방식으로 값을 넘기면 거기서 루프가 중단돼버리는 문제가 있었다.
하는 수 없이 loop를 감싸줄 껍데기 함수를 만들고, 거기서 result를 선언하는 방식으로 했다.
function loop(arr, temp = []) { if (arr.length < 1) { // arr.length가 1보다 작아지면 남은 요소가 없는 것 result = result.concat(temp); // 재귀함수 바깥의 외부 변수에 값 저장 } for (let i in arr) { const newArr = arr.slice(); // 함수파라미터 직접 손대면 안 되니까 복사하고 const element = newArr[i]; newArr.splice(i, 1); // 각 루프마다 i번째 요소를 제거하고 const r = call(element, temp); // 순열값 배열 갱신하고 loop(newArr, r); // 다시 루프 } }그리고 함수 2개를 껍데기 함수에 넣어주면 끝.
function genPPSet(arr) { function call(s, arr) { // 블라블라 } let result = []; function loop(arr, temp = []) { // 블라블라 } loop(arr); return result; }소수 판별
소수 판별은 비슷한 예제가 많았다.
일단 정의를 먼저 참조했다. 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수라고 한다.
자신보다 작은 두 개의 자연수를 곱한다고 했으니 제곱근보다 큰 약수는 무시해도 된다.
100의 제곱근은 10인데, 10이 넘어가는 약수로 100을 만들려면 20 * 5처럼 제곱근 보다 큰 수 x 작은 수 조합을 택해야 하고,
그러면 제곱근 보다 작은 수를 검사했을 때 이미 5가 걸리니까 큰 수는 따로 검사하지 않아도 된다.
먼저 제곱근을 구하고
const sqrt = Math.floor(Math.sqrt(numbers));제곱근부터 시작해서 1까지 숫자를 하나씩 줄여가면서, 나누어떨어지는 수가 있는지를 확인해본다.
나누어떨어지면 약수가 있는 것이고, 소수가 아니니까 false를 리턴한다.
function isPrime(numbers) { var sqrt = Math.floor(Math.sqrt(numbers)); for (let i = sqrt; i > 1; i--) { if (numbers % i <= 0) { return false; } } return true; };
최종 함수
순열멱집합 중에서 중복인 것을 골라낼 함수를 추가해주었다.
function solution(numbers) { function genPowerSet(arr) { const result = []; const len = arr.length; for (let i = 0; i < 2**len; i++) { const eachSet = []; for (let j = 0; j < len; j++) { if (((i >> j) % 2) == 1) { eachSet.push(arr[j]); } } result.push(eachSet); } result.shift(); return result; } function genPPSet(arr) { function call(s, arr) { if (arr.length === 0) { return [s]; } return arr.map((x) => String(x) + s); } let result = []; function loop(arr, temp = []) { if (arr.length < 1) { result.push(...temp); } for (let i in arr) { const newArr = arr.slice(); const element = newArr[i]; newArr.splice(i, 1); const r = call(element, temp); loop(newArr, r); } } loop(arr); return result; } function isPrime(numbers) { var sqrt = Math.floor(Math.sqrt(numbers)); for (let i = sqrt; i > 1; i--) { if (numbers % i <= 0) { return false; } } return true; } function convertToNumberSet(arr) { const set = Array.from(new Set(arr), Number); // 중복제거 return set; } function subsetToString(arr) { return [...new Set(arr.map((x) => x.join("")))]; } function applyPPSet(powerSetString) { const ppset = []; for (let powerString of powerSetString) { const candidate = genPPSet(Array.from(powerString)); const uniqueOnes = candidate.filter(x => !ppset.includes(x)); ppset.push(...uniqueOnes); } return ppset; } function filterZeroOne(arr) { const newArr = arr.slice(); const zeroOne = [0, 1]; for (let i of zeroOne) { const index = newArr.indexOf(i); if (index >= 0) { newArr.splice(index, 1); } } return Array.from(new Set(newArr), Number); } const numArr = Array.from(numbers, Number); const powerSet = genPowerSet(numArr); const powerSetString = subsetToString(powerSet); const ppset = applyPPSet(powerSetString); const converted = Array.from(ppset, Number); const uniques = Array.from(new Set(converted), Number); const filtered = filterZeroOne(uniques); return filtered.filter(isPrime).length; }'FrontEnd > 알고리즘' 카테고리의 다른 글
Base N(n진법)으로 변환하기 (0) 2021.05.23