CS/알고리즘 (2) 썸네일형 리스트형 [알고리즘] 순열(Permutation) 계기 SSAFY 교육 정리 순열(Permutation) 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현한다. 그리고 nPr은 다음과 같은 식이 성립한다 nPn = n!이라고 표기하며 Factorial이라 부른다. 다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련 있다. 예> TSP(Traveling Salesperson Problem, 외판원 순회) N개의 요소들에 대해서 n!개의 순열들이 존재한다. 12! = 479,001,600 n > 12 인 경우, 시간 복잡도 폭발적으로 ↑ 단순하게 순열을 생성하는 방법 예) {1, 2, 3}을 포함하는 모든 순열을 생성하는 함수 동일한 숫자가 포함되지 않았을 때,.. [알고리즘] 부분집합 & 조합 + 비트 연산자 개요 SSAFY 교육 정리 부분집합 (Powerset) 비트 연산자 연산자 연산자의 기능 & 비트 단위로 AND 연산 예) num1 & num2 | 비트 단위로 OR 연산을 한다. 예) num1 | num2 ^ 비트 단위로 XOR 연산을 한다. (같으면 0 다르면 1) 예) num1 ^ num2 ~ 단항 연산자로서 피연산자의 모든 비트를 반전시킨다. 예) ~num > 2 부분집합의 수 - 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2ⁿ개 - 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다. - 예) 반복문을 이용하여 부분집합 구하기 - 의사코드 sel = {0, 0, 0, 0} for i in 0 to 1: sel[0] = i /.. 이전 1 다음