알고리즘/알고리즘 이론
-
순조부 2 - 순열(Permutation)알고리즘/알고리즘 이론 2022. 10. 15. 12:39
순열은 서로 다른 n개 중 r개를 택하여 한 줄로 나열한 것이다. 순열을 코드로 표현하는 방법은 재귀, 비트마스킹, 넥퍼(Next Permutation) 3가지 방법으로 나타낼 수 있다. 재귀 N개의 숫자를 배열에 저장 배열에서 각 위치의 숫자를 뽑았을 때, 뽑지 않았을 때의 순열을 생성 순열의 크기가 R개가 됐을 때 순열 완성 public class Permutation { // N개 중 R개의 순열 뽑기 static int N, R; // arr - 입력받을 배열 // temp - 순열을 저장할 배열 static int[] arr, temp; // 순열을 만들기 위해 arr의 요소가 선택됐는지 안됐는지 판단하는 배열 static boolean[] isSelected; public static void..
-
순조부 1 - 순열, 조합, 부분 집합알고리즘/알고리즘 이론 2022. 9. 30. 10:49
이 글에서는 알고리즘의 기초 중 하나인 순열, 조합, 부분 집합을 다루겠습니다. 순열, 조합, 부분 집합은 나중에가면 비슷하기 때문에 같은 문제를 서로 다른 방법으로도 풀 수 있는데 시간의 차이가 있기 때문에 문제를 파악해서 적절한 알고리즘을 사용할 수 있도록 개념을 정리해봅니다. 이 글에서는 각각의 기본 개념에 대해 다루며 자세한 내용은 다음 글에서 다루도록 하겠습니다. 1. 순열 정의 - 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열(순서있게)하는 것 순열은 간단하게 말해 순서가 있는 집합이라 표현할 수 있습니다. 예를 들어 {1, 2, 3} 과 {2, 1, 3}은 내용물은 같지만 순서가 다르죠 이 경우 순열에서는 두 집합은 다른 집합입니다. 표현 nPr nPr = n * (n-1) * (n-2)..