20250916 순열/조합/부분집합 알고리즘, 트리

일반 순열

일반 순열(nPr)은 서로 다른 n개의 원소 중에서  r개를 뽑아 순서대로 나열하는 방법의 수를 의미한다.

순서를 고려하기 때문에, 내용이 같더라도 나열하는 순서가 다르면 다른 경우로 간주한다.

 

자바 코드로 구현하면

import java.util.Arrays;

public class 주사위일반순열Test {
	
	static int totalCnt;
	static int n; // 주사위 던지는 횟수
	static int[] results; 
	static boolean[] isSelected;
	
	public static void main(String[] args) {
		n = 2;
		results = new int[n];
		isSelected = new boolean[7];
		주사위던지기(0);
		System.out.println(totalCnt);
	}

	private static void 주사위던지기(int cnt) {
		if (cnt == n) {
			totalCnt++;
			System.out.println(Arrays.toString(results));
			return;
		}
		
		for (int i = 1; i <= 6; i++) {
			if (isSelected[i]) continue;
			results[cnt] = i;
			isSelected[i] = true;
			주사위던지기(cnt+1);
			isSelected[i] = false;
		}
	}
}

주사위던지기는 재귀함수로 구현했다. 순서를 고려하기 때문에 내용이 같아도 다른 경우로 친다.

그래서 for문은 1부터 6까지 계속 반복한다. 그리고 앞에서 고른 수의 경우 고르지 않게 한다.

이를 계속해서 반복해서 모든 경우의 수를 출력하고 총 갯수를 출력한다.

cnt가 n이 되면 한 가지 경우가 생긴다고 볼 수 있다.

 

백준 10974번 문제

N(1 ~ 8)이 주어졌을 때 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 문제

 

import java.util.Arrays;
import java.util.Scanner;

public class 모든순열_백준10974 {
	
	static int n;
	static int[] results;
	static boolean[] isSelected;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		
		results = new int[n];
		isSelected = new boolean[n + 1];
		perm(0);
		
		System.out.println(sb.toString());
		sc.close();
	}

	private static void perm(int cnt) {
		if (cnt == n) {
			for (int i: results) {
				sb.append(i).append(" ");
			}
			sb.append("\n");
			return;
		}
		
		for (int i = 1; i <= n; i++) {
			if (isSelected[i]) continue;
			results[cnt] = i;
			isSelected[i] = true;
			
			perm(cnt + 1);
			
			isSelected[i] = false;
		}
	}
}

위의 자바코드와 알고리즘 자체는 다른게 없다. 일반 순열의 알고리즘이다.

차이가 있다면 입력을 직접 받고 출력의 형태가 다르다는 것이다.

Scanner와 System.in으로 정수 N을 입력받고 출력은 StringBuilder를 이용해 조합을 하나씩 sb에 append하고 마지막에 sb를 출력한다. 이 문제의 경우 N 하나만을 입력 받기 때문에 괜찮지만 입력이 커질 경우 BufferedReader를 사용하는 것이 좋다.

Scanner는 입력을 정규식 기반으로 파싱하기 때문에 속도가 느리다. (코드 작성은 간단)

BufferedReader는 단순히 문자열을 읽어오기 때문에 훨씬 빠르다. 대신 문자열을 직접 파싱해야 해서 조금 더 코드 작성이 복잡해지긴 한다.

 

일반 조합

조합은 여러 개 중에서 순서에 상관없이 정해진 개수만큼 선택하는 경우의 수를 말한다.

순서를 고려하지 않아서 같은 조합은 동일한 것으로 한 번만 센다.

 

자바 코드로 구현하면

import java.util.Arrays;

public class 주사위일반조합Test {
	
	static int n;
	static int[] results;
	static int totalCnt;
	
	public static void main(String[] args) {
		n = 2; 
		results = new int[n];
		
		주사위던지기(0, 1);
		System.out.println(totalCnt);
	}

	private static void 주사위던지기(int cnt, int start) {
		if (cnt == n) {
			totalCnt++;
			System.out.println(Arrays.toString(results));
			return;
		}
		
		for (int i = start; i <= 6; i++) {
			results[cnt] = i;
			주사위던지기(cnt + 1, i + 1);
		}
	}
}

주사위던지기는 동일하게 재귀함수로 구현했고 반복문과 매개변수의 차이가 있다.

매개변수는 반복적으로 동일한 부분은 세지 않기 위해 추가되었고 for문은 이미 사용된 조합은 빼고 돌게 된다.

 

부분 집합

부분 집합이란 어떤 집합의 모든 원소가 다른 집합에도 포함될 때, 그 다른 집합을 원래 집합의 부분 집합이라고 한다.

어떤 데이터에 원소들이 있으면 그 데이터로 만들어낼 수 있는 모든 조합이 가능하다고 볼 수 있다. 공집합 포함

 

자바 코드로 구현하면

public class 주사위부분집합Test {
	
	static int totalCnt;
	static int[] data = {1, 2, 3, 4, 5, 6};
	static boolean[] isSelected;
	
	public static void main(String[] args) {
		
		isSelected = new boolean[6];
		
		subset(0);
		System.out.println(totalCnt);
	}

	private static void subset(int cnt) {
		if (cnt == 6) {
			++totalCnt;
			for (int i = 0; i < 6; i++) {
				System.out.print ((isSelected[i] ? data[i] : "X") + " ");
			}
			System.out.println();
			return;
		}
		
		isSelected[cnt] = true;
		subset(cnt + 1);
		
		isSelected[cnt] = false;
		subset(cnt + 1);
	}
}

주어진 data로 만들 수 있는 집합의 모든 종류를 만들어낸다.

원소가 6개이므로 2^6인 64개의 조합이 나온다.

 

실행 결과

1 2 3 4 5 6 
1 2 3 4 5 X 
1 2 3 4 X 6 
1 2 3 4 X X 
1 2 3 X 5 6 
1 2 3 X 5 X 
1 2 3 X X 6 
1 2 3 X X X 
1 2 X 4 5 6 
1 2 X 4 5 X 
1 2 X 4 X 6 
1 2 X 4 X X 
1 2 X X 5 6 
1 2 X X 5 X 
1 2 X X X 6 
1 2 X X X X 
1 X 3 4 5 6 
1 X 3 4 5 X 
1 X 3 4 X 6 
1 X 3 4 X X 
1 X 3 X 5 6 
1 X 3 X 5 X 
1 X 3 X X 6 
1 X 3 X X X 
1 X X 4 5 6 
1 X X 4 5 X 
1 X X 4 X 6 
1 X X 4 X X 
1 X X X 5 6 
1 X X X 5 X 
1 X X X X 6 
1 X X X X X 
X 2 3 4 5 6 
X 2 3 4 5 X 
X 2 3 4 X 6 
X 2 3 4 X X 
X 2 3 X 5 6 
X 2 3 X 5 X 
X 2 3 X X 6 
X 2 3 X X X 
X 2 X 4 5 6 
X 2 X 4 5 X 
X 2 X 4 X 6 
X 2 X 4 X X 
X 2 X X 5 6 
X 2 X X 5 X 
X 2 X X X 6 
X 2 X X X X 
X X 3 4 5 6 
X X 3 4 5 X 
X X 3 4 X 6 
X X 3 4 X X 
X X 3 X 5 6 
X X 3 X 5 X 
X X 3 X X 6 
X X 3 X X X 
X X X 4 5 6 
X X X 4 5 X 
X X X 4 X 6 
X X X 4 X X 
X X X X 5 6 
X X X X 5 X 
X X X X X 6 
X X X X X X 
64

 

백준 1182번 문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제이다.

 

수업 때 배운 내용과 크게 다를 게 없는 문제라서 그대로 적용해서 풀었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 부분집합_백준1182 {
	
	static int N, S;
	static int[] datas;
	static boolean[] isSelected;
	static int totalCnt;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		datas = new int[N];
		isSelected = new boolean[N];
		
		int i = 0;
		while(st.hasMoreTokens()) {
			datas[i++] = Integer.parseInt(st.nextToken());
		}
		
		subset(0);
		if (S == 0) {
			System.out.println(--totalCnt);
		} else {
			System.out.println(totalCnt);
		}
	}

	private static void subset(int cnt) {
		if (cnt == N) {
			int sum = 0;
			for (int i = 0; i < N; i++) {
				if (isSelected[i]) {
					sum += datas[i];
				}
			}
			
			if (sum == S) {
				totalCnt++;
			}
			
			return;
		}
		
		isSelected[cnt] = true;
		subset(cnt + 1);
		isSelected[cnt] = false;
		subset(cnt + 1);
	}
}

 

 

이렇게 풀고 보니 최적화할 수 있는 부분들이 많아 보인다.

 

sum을 끝날 때마다 반복문으로 계속해서 계산하고 있는데 sum을 인자로 넘겨주면 매번 for문을 돌 필요가 없다.

 

 

개선한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 부분집합_백준1182 {
	
	static int N, S;
	static int[] datas;
	static int totalCnt;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		datas = new int[N];
		
		int i = 0;
		while(st.hasMoreTokens()) {
			datas[i++] = Integer.parseInt(st.nextToken());
		}
		
		subset(0, 0);
		if (S == 0) {
			System.out.println(--totalCnt);
		} else {
			System.out.println(totalCnt);
		}
	}

	private static void subset(int cnt, int sum) {
		if (cnt == N) {
			if (sum == S) {
				totalCnt++;
			}
			
			return;
		}
		
		subset(cnt + 1, sum + datas[cnt]);
		subset(cnt + 1, sum);
	}
}

isSelected 배열도 필요 없어지고 for문도 돌지 않아도 되서 엄청 빨라졌다.

 

 

사용한 메모리/시간 둘 다 줄어든 모습

 

비선형 자료구조

비선형 자료구조는 데이터가 선형적으로 배치되지 않고, 계층적 또는 비계층적으로 연결된 구조이다.

복잡한 관계를 표현하고 효율적인 데이터 검색 및 관리가 가능하다.

종류: 트리, 그래프

트리(Tree)

트리는 나무의 가지처럼 뻗어 나가는 형태를 가진 비선형 계층적 자료 구조로, 하나의 루트 노드와 0개 이상의 하위 트리로 구성된다. 각 노드는 값과 다른 노드를 가리키는 포인터를 가지고 있으며, 노드들을 연결하는 간선이 존재한다. 트리에는 순환이 없고 컴퓨터의 파일 시스템이나 조직도 등 계층적 데이터를 표현하는 데 널리 사용된다.

 

트리 종류

트리 종류	설명	특징 및 조건
Binary Tree (이진트리)	각 노드가 최대 두 개의 자식을 가지는 트리	왼쪽, 오른쪽 자식 노드 존재 가능
Ternary Tree (삼진트리)	각 노드가 최대 세 개의 자식을 가지는 트리	Binary Tree보다 자식 노드가 더 많음
Skewed Binary Tree (편향 이진트리)	모든 노드가 한쪽 방향으로만 연결된 이진트리	일자 형태, 불균형 트리
Binary Search Tree (이진 탐색 트리)	왼쪽 자식이 부모보다 작고 오른쪽 자식이 부모보다 큰 이진트리	탐색 효율적, 정렬된 데이터 저장 가능
Complete Binary (완전 이진트리)	마지막 레벨을 제외한 모든 레벨이 꽉 차 있고 마지막 레벨은 왼쪽부터 채워진 트리	노드들이 최대한 왼쪽에 밀집되어 있음
Full Binary Tree (포화 이진트리)	모든 노드가 0개 또는 2개의 자식을 가지는 이진트리	중간 노드 모두 두 자식 보유
Perfect Binary Tree (완전 균형 이진트리)	모든 리프 노드가 같은 깊이에 있고 모든 부모가 정확히 두 자식 보유	높이 균형 최적화, 완벽한 이진트리
Tree (일반적인 트리)	계층적 구조를 나태는 데이터 구조, 노드와 간선으로 구성	루트 노드부터 시작, 사이클 없음

 

용어

노드: 데이터의 단위(정점) 루트: 트리의 최상위 노드(첫 노드)

리프: 자식 노드가 없는 노드(끝 노드)

서브트리: 특정 노드를 루트로 하는 하위 트리

높이: 트리의 루트에서 가장 깊은 리프까지의 경로 길이(전체 깊이)

깊이: 특정 노드가 루트에서 얼마나 떨어져 있는지를 나타냅니다

간선: 부모 노드와 자식 노드를 연결, 트리는 사이클이 없고 항상 연결되어 있어야 함. 노드 수가 n이면 간선의 수는 항상 n-1

 

이진트리 순회 구현 (HashMap)

백준 1991번 문제

이진 트리를 입력받아 전위 순회, 중위 순회, 후위 순회한 결과를 출력하는 문제이다.

 

import java.util.Map;
import java.util.Scanner;

public class 백준1991_트리순회 {

	static Map<Character, char[]> tree = new HashMap<>();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		sc.nextLine(); // 개행 문자 제거 작업
		
		for (int i = 0; i < n; i++) {
			String oneLine = sc.nextLine();
			char parent = oneLine.charAt(0);
			char leftChild = oneLine.charAt(2);
			char rightChild = oneLine.charAt(4);
			
			if (leftChild != '.') {
				tree.putIfAbsent(parent, new char[2]);
				tree.get(parent)[0] = leftChild;
			}
			
			if (rightChild != '.') {
				tree.putIfAbsent(parent, new char[2]);
				tree.get(parent)[1] = rightChild;
			}
		}
		
		preOrder('A');
		System.out.println();
		inOrder('A');
		System.out.println();
		postOrder('A');
	}

	private static void preOrder(char node) {
		System.out.print(node);
		if(tree.containsKey(node)) {
			char[] children = tree.get(node);
			if (children[0] != '\u0000') preOrder(children[0]);
			if (children[1] != '\u0000') preOrder(children[1]);
		}
	}
	
	private static void inOrder(char node) {
		if(tree.containsKey(node)) {
			char[] children = tree.get(node);
			if (children[0] != '\u0000') inOrder(children[0]);
		}
		
		System.out.print(node);
		
		if(tree.containsKey(node)) {
			char[] children = tree.get(node);
			if (children[1] != '\u0000') inOrder(children[1]);
		}
	}
	
	private static void postOrder(char node) {
		
		if(tree.containsKey(node)) {
			char[] children = tree.get(node);
			if (children[0] != '\u0000') postOrder(children[0]);
			if (children[1] != '\u0000') postOrder(children[1]);
		}
		
		System.out.print(node);
	}
}

preOrder는 전위 순회, inOrder는 중위 순회, postOrder는 후위 순회이다.

 

 

HashMap으로 이진 트리를 구현한다.

static Map<Character, char[]> tree = new HashMap<>();

for (int i = 0; i < n; i++) {
    String oneLine = sc.nextLine();
    char parent = oneLine.charAt(0);
    char leftChild = oneLine.charAt(2);
    char rightChild = oneLine.charAt(4);

    if (leftChild != '.') {
        tree.putIfAbsent(parent, new char[2]);
        tree.get(parent)[0] = leftChild;
    }

    if (rightChild != '.') {
        tree.putIfAbsent(parent, new char[2]);
        tree.get(parent)[1] = rightChild;
    }
}

putIfAbsent 메서드는 parent가 존재하지 않으면 new char[2]를 생성한다. 이미 있으면 기존 value를 그대로 유지한다.

 

 

preOrder는 루트 - 왼쪽 자식 - 오른쪽 자식으로 순회한다.

private static void preOrder(char node) {
    System.out.print(node);
    if(tree.containsKey(node)) {
        char[] children = tree.get(node);
        if (children[0] != '\u0000') preOrder(children[0]);
        if (children[1] != '\u0000') preOrder(children[1]);
    }
}

main에서 preOrder('A')로 호출되기 때문에 A(루트)부터 왼쪽 자식들을 먼저 출력하고 오른쪽 자식을 출력한다.

 

 

inOrder는 왼쪽자식 - 루트 - 오른쪽 자식순으로 순회한다.

private static void inOrder(char node) {
    if(tree.containsKey(node)) {
        char[] children = tree.get(node);
        if (children[0] != '\u0000') inOrder(children[0]);
    }

    System.out.print(node);

    if(tree.containsKey(node)) {
        char[] children = tree.get(node);
        if (children[1] != '\u0000') inOrder(children[1]);
    }
}

 

 

postOrder는 왼쪽 자식 - 오른쪽 자식 - 루트순으로 순회한다.

private static void postOrder(char node) {

    if(tree.containsKey(node)) {
        char[] children = tree.get(node);
        if (children[0] != '\u0000') postOrder(children[0]);
        if (children[1] != '\u0000') postOrder(children[1]);
    }

    System.out.print(node);
}

 

이진 검색 (트리가 아닌 1차원 배열)

어떤 노드를 찾기 위해 모든 노드를 순회해야 한다면 완전탐색 O(n)이 된다.

이것을 O(log n)으로 만들 수 있는 방법이 이진 검색이다. 모든 노드가 정렬되어 있다는 조건이 있다.

 

public class MyBinarySearch {

	public static void main(String[] args) {
		int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15};
		int target = 7;
		
		int idx = binarySearch(sortedArray, target);
		
		if (idx != -1) {
			System.out.println(idx);
		} else {
			System.out.println("찾을 수 없습니다.");
		}
	}

	private static int binarySearch(int[] arr, int target) {
		int low = 0;
		int high = arr.length - 1;
		
		while(low <= high) {
			int mid = (low + high) / 2;
			
			if (arr[mid] == target) {
				return mid;
			} else if (arr[mid] < target) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		
		return -1;
	}
}

찾지 못하는 경우는 -1이 인덱스 값이 된다.

 

자바 API

자바에는 이진 검색 메서드가 있다.

import java.util.Arrays;

public class BinarySearchAPI {

	public static void main(String[] args) {
		int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15};
		int target = 4;
		
		int idx = Arrays.binarySearch(sortedArray, target);
		
		if (idx >= 0) {
			System.out.println(idx);
		} else {
			System.out.println("찾을 수 없습니다." + idx);
		}
	}
}

4는 없는 값인데 출력해보면 -3이 나온다. 이는 4가 들어갈만한 자리를 알려주는 것이다.

3과 5사이에 있기 때문에 이는 2를 의미하는데 -3은 (-(들어갈 인덱스) - 1)로 만들어진 값이기 때문이다.