본문 바로가기

Algorithm/Math5

[Math] 부분집합과 멱집합 / Java 부분집합(Subset)과 멱집합(Power Set) 집합 A와 B가 있을 때, B의 특정 원소 x가 반드시 A의 원소이면 B를 A의 부분집합이라고 합니다. 그리고 이러한 부분집합(Subset)의 모든 경우의 수로 구성된 집합을 멱집합이라고 합니다. 부분집합을 Power Set으로 부르는 경우가 있는데 엄밀히 따지면 부분집합과 멱집합은 구분되는 개념입니다. 구현 구현 방식은 다음 두 가지가 있습니다. 재귀와 방문배열을 활용한 방식 비트마스킹을 활용한 방식 Java Code public class PowerSet { static int[] arr = {1, 2, 3}; static int n = arr.length; // 주어진 수의 갯수 static boolean[] visited = new boolean.. 2023. 8. 14.
[Math] 순열(Permutation) / Java 순열(順列) 순서를 고려해 나열한 경우의 수. 즉, 서로 다른 n개 중 r개를 골라 순서를 정해 나열하는 경우의 수(nPr)를 의미합니다. 예를 들어, 다섯 명의 학생 중 반장 1명과 부반장 1명을 뽑는 경우의 수를 구하는 것이 순열에 해당한다고 볼 수 있습니다. 공식은 다음과 같습니다. 구현 주어진 수의 배열이 1, 2, 3일 때 두 개를 뽑는 순열의 경우의 수를 출력하는 코드입니다. 구현 방식은 두 가지입니다. 재귀와 방문배열을 활용한 방식 비트마스킹을 활용한 방식 // 순열(nPr) - n개의 값 중 r개를 순서대로 뽑는 경우의 수 public class Permutation { static int[] arr = {1, 2, 3}; static int n = arr.length; // 주어진 수의 .. 2023. 8. 13.
[백준] 11758. CCW / Java https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 문제 풀이 이 문제는 두 벡터의 외적을 구하는 공식으로 풀 수 있는 문제이다. 일명 '신발끈 공식'으로 (빨간색 빗금으로 이어진 것들의 곱의 합) - (파란색 빗금으로 이어진 것들의 곱의 합) 이다. 즉, 아래와 같은 식이다. (x1*y2 + x2*y3 + x3*y1) - (y1*x2 + y2*x3 + y3*x1) 계산 결과가 양.. 2023. 6. 20.
순열(Permutation) 순열(Permutation) 서로 다른 n개 중 r개를 순서 있게 배열하는 경우의 수 (중복 X) 중복 순열 서로 다른 n개 중 r개를 순서 있게 배열하는 경우의 수 (중복 O) 원 순열 서로 다른 n개를 원형으로 배치하는 경우의 수 ex) 원 모양의 테이블에 각자 이웃하는 사람의 구성이 다른 모든 경우의 수. 회전시켜서 같은 경우는 하나의 경우로 여김 코드(Java) public class Main { public static void main(String[] args) { int n = 6; int r = 3; // 순열 int p1 = 1; for (int i = n; i >= n - r + 1 ; i--) { p1 *= i; } // 중복 순열 int p2 = 1; for (int i = 0; i.. 2023. 1. 9.

티스토리툴바