본문 바로가기

Algorithm/이론3

Next Permutation을 이용한 순열 배열을 오름차순 정렬한 뒤, 사전 순으로 다음 순열을 생성하는 방법 절차 배열을 오름차순으로 정렬 다음이 과정의 반복하여 순열 생성 (가장 큰 내림차순 순열을 만들 때까지 반복) 뒤쪽부터 탐색하여 교환위치(꼭대기 바로 직전) 찾기 (꼭대기 - 가장 큰 수) 뒤쪽부터 탐색하여 교환위치와(꼭대기 바로 직전) 교환할 큰 값 위치 찾기 (교환위치보다 큰 수 중 가장 가까운 수) 두 위치 값 교환 꼭대기부터 맨 뒤까지 오름차순 정렬 ex. 1 2 3 -> 3 2 1 까지 만드는 과정 import java.util.Arrays; public class NextPermutation { static int R, N, nums[], set[]; public static void main(String[] args) { /.. 2022. 5. 17.

Next Permutation을 이용한 조합 flag를 Next Permutation을 이용하여 구현한 것 nCr 을 구하고자 할 때, 크기 n의 배열을 생성하여 r 개의 크기만큼 0 이 아닌 값 초기화 5C2 이면, 00011 로 초기화 Next Permutation 알고리즘 이용 00011을 사용하여 NP를 돌리고 1의 위치에 원소 값이 선택되어 조합을 만든다. Next Permutation 한 번 이용할 때마다 조합이 만들어 진다. (0이 아닌 값의 위치가 변경된다) => r개의 크기 만큼, 즉, 0이 아닌 값이 세팅된 곳에 원소를 선택하여 조합을 만든 것이다. import java.util.Arrays; public class Combination { static int N, R, nums[]; public static void main(S.. 2022. 5. 17.

비트마스킹을 이용한 순열, 조합 비트 0 = false = 사용 중 X 1 = true = 사용 중 O 비트 연산자 & : AND 연산 | : OR 연산 ^ : XOR 연산 (같으면 0, 다르면 1) ~ : 모든 비트 반전 : 비트 열을 오른쪽으로 이동 (빈 공간은 부호비트로 채운다) >>> : 비트 열을 오른쪽으로 이동 (빈 공간은 0으로 채운다) &’은 해당 숫자가 사용중인지, ‘|’은 해당 숫자를 사용 중임을 나타내기 위해 사용 1. 순열 코드 - 비트 마스킹 사용 import java.util.Arrays; public class Permutation_BitMasking { static int R, N, nums[], set[]; public static void main(String[] args) { //nPr R = 2; N.. 2022. 5. 17.

이전 1 다음

티스토리툴바