조합

[SWEA] 1767 - 프로세서 연결하기 (자바/Java)

조합을 통해 경우의 수를 한정하는 방법을 자주 사용해야 할 것 같다. 처음에는 그냥 dfs로 풀어서 답은 맞았는데, 시간과 메모리를 너무 많이 잡아 먹었다. 지금 생각해보니 필요 없는 경우의 수까지 모두 탐색해서 그런 것 같다. 연결하는 코어의 수가 최대여야 하기 때문에, 모든 코어를 연결하는 경우의 수부터 dfs를 진행하고, 만약 그 수의 코어를 연결할 수 없다면 코어의 개수 N 중 N-1개, N-2개를 뽑는 조합을 통해 dfs를 반복하여 결과값이 나올 때까지 계속하면 된다. 이런 경우에서는 조합을 활용하는 게 유용한 것 같다. for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { arr[i][j] = sc.nextInt(); if (arr[i][j] ..

[백준] 1759 - 암호 만들기 (자바/Java)

문제 링크 성능 요약 메모리: 13036 KB, 시간: 120 ms 분류 백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing), 조합론(combinatorics), 수학(math) 문제 설명 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서..

[백준] 9375 - 패션왕 신해빈 (자바/Java)

문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까? 입력 첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다. 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다. 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다. 모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 ..

[백준] 1010 - 다리 놓기 (자바/Java)

문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지..

[알고리즘] 기본 수학 - 순열 조합 중복순열 중복조합 (자바/Java)

순열/조합 순열, 조합, 중복 순열, 중복 조합을 dfs를 이용하여 구할 수 있다. 백준의 N과 M시리즈가 순열/조합을 공부하기 좋은 문제들이다. https://www.acmicpc.net/workbook/view/2052 1. 순열 순열은 N개의 수에서 R개의 수를 뽑아 순서대로 나열하는 것이다. {1, 2, 3, 4} 4개의 수에서 2개의 수를 뽑아 나열하는 경우의 수는 {1, 2} {1, 3} {1, 4} {2, 1} {2, 3} {2, 4} {3, 1} {3, 2} {3, 4} {4, 1} {4, 2} {4, 3} 의 12가지다. $$ nPr = n*(n-1) * ... (n-r+1) $$ 순열을 구하기 위해서는 dfs를 활용한다. static void dfs(int N, int M, int cn..

[백준] N과 M (자바/Java) 순열, 조합, 중복순열, 중복조합

N과 M은 순열, 조합, 중복순열, 중복조합을 연습할 수 있는 문제이다. 순열과 조합은 재귀를 사용하여 풀 수 있다. 1. 순열 순열에서 nPr은, N개의 수에서 가능한 r개의 수를, 순서대로 나열하는 것이다. 순열에는 순서가 존재하기 때문에 1 2 3과 3 2 1은 다른 경우로 취급한다. 이를 재귀와 dfs를 활용하여 풀면 다음과 같다. cnt는 dfs의 깊이를 의미한다. cnt가 M이 되면 M개의 순열이 완성되었다는 의미이므로 함수를 return 한다. 또한 순열은 중복을 허용하지 않기 때문에 순열에 포함되었는지 여부를 확인할 boolean check 배열이 필요하다. 배열의 처음부터 for문을 돌며 방문하지 않은 노드일 경우 check를 true로 바꾸고, 다시 깊이 cnt를 +1 한 다음, 재귀적..

[백준] 2407 - 조합 (자바/Java) BigInteger 클래스

문제 nCm을 출력한다. 입력 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) 출력 nCm을 출력한다. 굳이 재귀로 팩토리얼을 구하지 않아도 간단하게 풀 수 있지만, 수의 범위가 커서 BigInteger 클래스를 사용해야 한다. package BOJ0809; import java.math.BigInteger; import java.util.Scanner; public class BOJ_2407_조합 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); BigInteger n = new BigInteger(Integer.toString(sc.nextInt())); BigInteger ..

[백준] 15650 - N과 M (2) (자바/Java) 백트래킹 DFS 조합

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 이전 문제와 달라진 점은 전의 문제가 순열이었다면 이번에는 조합을 구하는 경우이다. 조건에 수열이 오름차순이라는 것이 추가되었는데, 이는 즉 1 2 3 4만 허용되고, 1 2 4 3, 1 4 3 2 등은 허용되지 않는 것이니 중복을..