순열은 어떤 집합의 원소들을 중복없이 뽑아 순서에 상관있게 나열하는것입니다.

n개의 원소를 가진 집합에서 r개를 뽑아 순열을 만든다고 하면 nPr 과 같이 나타냅니다.

 

원소를 넣을지 말지를 정했던 부분집합과 달리 순열은 이 위치에 이 원소를 넣을지 말지를 나누어서 진행됩니다.

{1,2,3,4}로 4개의 원소를 가진 집합에서 4개를 뽑아 만들 수 있는 순열을 모두 구한다고 해봅시다. = 4P4

 

우선 첫번째 위치에 1이 들어갑니다.

이 과정에서 우리는 1로 시작하는 모든 순열을 구하게 됩니다. (1로 만들수 있는 경우)

중복이 허용되지 않기 때문에 이미 사용된 1을 제외한 나머지 원소들 중에서 두번째 자리에 들어갈 것을 정해야합니다.

순서대로 2를 넣어줍니다. (1-2로 만들수 있는 경우)

같은 방식으로 중복이 되지 않게 다음 자리에 넣어질 수를 구해봅시다.

이때 재귀 호출된 함수는 이런 상태입니다. 

가장 위쪽에서부터 하나씩 숫자를 선택하며 4번째 같은 함수를 호출했습니다.

원했던 4개의 원소를 뽑았으므로 1-2-3-4 순열이 완성됩니다. (1-2-3 으로 만들수 있는 경우)

이제 4번째 함수는 종료되고 세번째 함수로 돌아갑니다. (1-2로 만들수 있는 경우)

세번째 자리에 3을 넣은 경우는 앞에서 시행했으므로 이번엔 4가 들어갑니다.

같은 방식으로 진행해서 이번엔 1-2-4-3 이라는 순열을 완성했습니다. (1-2-4 로 만들수 있는 경우)

순열은 구성한 원소가 같더라도 순서가 다르면 다른 것으로 보기때문에 1-2-3-4와 1-2-4-3은 다른 순열입니다.

첫 자리와 두번째 자리가 각각 1, 2인 경우는 모두 탐색되었습니다.

이제 두번째 자리가 달라지는 경우를 찾습니다.

두번째 자리에 3이 들어가는 경우가 시작됩니다.

위와 같은 방식으로 진행해서 1-3-2-4 순열을 얻었습니다.

 

같은 방식으로 진행하면 위와 같은 순서로 24개의 순열을 얻습니다.

처음 시작할때 원소들이 오름차순 정렬된 상태였으므로 결과들도 오름차순으로 정렬된 순서로 나옵니다.

아래는 위 아이디어를 구현한 Java와 Python코드입니다.

size 변수를 number배열의 원소 갯수보다 작게 조절하면 부분순열이 됩니다.

 

순열을 만드는 방법은 아래와 같이 재귀를 이용한 것과 반복문을 이용한 nextPermutation이란것이 있는데 후자는 다른 포스팅에서 얘기해보도록 하겠습니다.

 

public class algo_02_permutation {
	static int[] number = { 1, 2, 3, 4, 5, 6 };
	static int size = 6;

	public static void main(String[] args) {
		makePermutation(0, new int[size], new boolean[number.length]);
	}

	public static void makePermutation(int count, int[] picked, boolean[] used) {
		if (count == size) {
			printPermutation(picked);
			return;
		}
		
		for(int i = 0; i < number.length; i++) {
			if(!used[i]) {
				picked[count] = number[i];
				used[i] = true;
				makePermutation(count+1, picked, used);
				used[i] = false;
			}
		}
		
	}

	public static void printPermutation(int[] picked) {
		StringBuilder sb = new StringBuilder();
		sb.append("{ ");
		for (int i = 0; i < size; i++) {
			sb.append(picked[i]).append(" ");
			}
		sb.append("}");
		System.out.println(sb.toString());
	}
}

 

def makePermutation(count, picked, used):
    global size
    global number

    if(count == size):
        printPermutation(picked)
        return
    
    for i in range(0, len(number)):
        if(not used[i]):
            picked[count] = number[i]
            used[i] = True
            makePermutation(count+1, picked, used)
            used[i] = False
    

def printPermutation(picked):
    global size
    msg = "{ "
    for i in range(0,size):
            msg += str(picked[i])
            msg += " "
    msg += "}"
    print(msg)

number = [1,2,3,4,5,6]
size = 6

makePermutation(0, [0]*size, [False]*len(number))
728x90
저작자표시 비영리 변경금지

'📖 CS > 💡 알고리즘' 카테고리의 다른 글

[Algorithm] 07.부분집합 (Subset)  (0) 2022.07.18
[Algorithm] 06.정렬 - 계수정렬 (Counting sort)  (0) 2022.04.21
[Algorithm] 04.정렬 - 퀵정렬 (Quick sort)  (0) 2022.04.19
[Algorithm] 04.정렬 - 병합정렬 (Merge sort)  (0) 2022.02.23
[Algorithm] 03.정렬 - 삽입정렬 (Insertion sort)  (0) 2022.02.21

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

주어진 조건에 맞게 양팔저울에 추를 올리는 경우의 수를 구하는 문제입니다.

Java의 경우에는 모든 경우에 대해 순열을 구하고 그 순열이 조건에 적합한지 검증을 하면서 가지치기를 해도 주어진 실행시간 안에 통과가 되지만, 조금 더 효율적으로 코드를 짤 수 있는 방법들이 있어 3가지를 전부 소개해드리겠습니다.

 

 

우선 기본적으로 모든 순열을 만들고, 이후 조건에 맞는 경우를 찾는 코드입니다.

시간 초과를 방지하기 위해 좌측의 무게가 절반을 넘어서는 경우 이후의 경우는 검증하지 않고 2^(N-현재 단계)만큼 더해주었습니다.

더보기 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class q3234_SWEA_준환이의양팔저울 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, answer, total;
	static Integer[] gram;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			answer = 0;
			total = 0;
			gram = new Integer[N];

			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) {
				gram[n] = Integer.parseInt(st.nextToken());
				total += gram[n];
			}
			total /= 2;

			makePermutation(0, new int[N], new boolean[N]);

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}

	static void makePermutation(int count, int[] choosed, boolean[] visited) {
		if (count == N) {
			check(1, choosed, choosed[0], 0);
			return;
		}
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				choosed[count] = gram[i];
				makePermutation(count + 1, choosed, visited);
				visited[i] = false;
			}
		}
	}

	static void check(int count, int[] choosed, int left, int right) {
		if (count == N) {
			answer++;
			return;
		}
		if (total < left) {
			int num = 1;
			for (int i = 0; i < N - count; i++) {
				num *= 2;
			}
			answer += num;
			return;
		}

		if (left >= right + choosed[count]) {

			check(count + 1, choosed, left, right + choosed[count]);
		}
		check(count + 1, choosed, left + choosed[count], right);

	}
}

 

두 번째론 모든 순열을 만들지 않고, 순열을 만드는 과정 안에 조건에 따른 검증을 넣어서 가지치기한 코드입니다.

마찬가지로 시간 초과를 방지하기 위해 좌측의 무게가 절반을 넘어서는 경우 이후의 경우는 검증하지 않고, (N-현재 단계)! * 2^(N-현재 단계)만큼 더해주었습니다.

순열이 다 만들어지지 않았기 때문에 경우의 수를 계산할 때 남은 추의 개수 팩토리얼까지 곱해주어야 합니다.

더보기 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class q3234_SWEA_준환이의양팔저울Re {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, answer, total;
	static Integer[] gram;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			answer = 0;
			total = 0;
			gram = new Integer[N];

			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) {
				gram[n] = Integer.parseInt(st.nextToken());
				total += gram[n];
			}
			total /= 2;

			makePermutation(0, new boolean[N], 0, 0);

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}

	static void makePermutation(int count, boolean[] visited, int left, int right) {
		// System.out.println(count + "선택됨," + left + " : " + right);

		if (count == N) {
			answer++;
			return;
		}

		if (total < left) {
			int num = 1;
			for (int i = 1; i <= N - count; i++) {
				num *= 2;
				num *= i;
			}
			answer += num;
			return;
		}

		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				makePermutation(count + 1, visited, left + gram[i], right);
				if (right + gram[i] <= left) {
					makePermutation(count + 1, visited, left, right + gram[i]);
				}
				visited[i] = false;
			}
		}
	}
}

 

세 번째로 메모이제이션을 활용해서 이미 탐색한 경우를 스킵한 코드입니다.

어떤 방법으로든 추의 위치 배정이 똑같은 시점이 오면 이후의 경우의 수의 개수는 같아집니다.

예를 들어 1,2,8,... 의 무게를 가진 추가 주어졌을때, 8(좌) → 1(우) → 2(우) 경우나 8(좌) → 2(우) → 1(우) 경우나 추의 현재 상태는 같습니다.

추의 상태가 같으면 이후 가능한 경우의 수도 같아집니다.

추의 상태를 사용한 추 (갯수가 작기 때문에 비트 마스킹으로 기록), 좌측에 놓인 무게로 저장하고 이전에 탐색한 적이 있다면 더 탐색을 하지 않고 그 값을 사용하는 코드입니다.

더보기 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class q3234_SWEA_준환이의양팔저울Re2 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, total;
	static int[] gram;
	static int[][] memo;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			total = 0;
			gram = new int[N];

			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) {
				gram[n] = Integer.parseInt(st.nextToken());
				total += gram[n];
			}

			memo = new int[total + 1][1 << N];

			sb.append("#").append(tc).append(" ").append(makePermutation(0, 0, 0, 0)).append("\n");
		}

		System.out.println(sb);
	}

	static int makePermutation(int count, int bitmask, int left, int right) {
		if (count == N) {
			return 1;
		}

		int sum = memo[left][bitmask];

		if (sum == 0) {
			for (int i = 0; i < N; i++) {
				if ((bitmask & (1 << i)) == 0) {
					sum += makePermutation(count + 1, bitmask | (1 << i), left + gram[i], right);
					if (right + gram[i] <= left) {
						sum += makePermutation(count + 1, bitmask | (1 << i), left, right + gram[i]);
					}
				}
			}
			return memo[left][bitmask] = sum;
		}
		return sum;
	}
}

 

위에서부터 순서대로 메모이제이션 → 순열구하면서 가지치기 → 순열 구하고 가지치기 코드의 실행결과입니다.

여러가지로 생각할 거리가 많은 좋은 문제였습니다.

728x90
저작자표시 비영리 변경금지

'🔍 알고리즘 > SWEA' 카테고리의 다른 글

[Java] SWEA 5656.벽돌깨기 (모의SW테스트)  (0) 2022.07.11
[Java] SWEA 4698.테네스의 특별한 소수 D3  (0) 2022.07.08
[Java] SWEA 7699.수지의 수지맞는 여행 D4  (0) 2022.07.04
[Java] SWEA 8382.방향전환 D4  (0) 2022.07.03
[Java] SWEA 8458.원점으로 집합 D4  (0) 2022.07.03

+ Recent posts

티스토리툴바