본문 바로가기
728x90

조합

Algorithm/정리 2022. 7. 15. [알고리즘] 순열 vs 조합 vs 부분 집합 (순조부) 순열 (Permutation) 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 서로 다른 n개 중 r개를 택하는 순열은 nPr 순열을 생성하는 방법 반복문을 통한 순열 생성 : 순열의 갯수가 적을때, 순열의 길이가 변동이 없을때 재귀 호출을 통한 순열 생성 : boolean[ ] 사용 비트마스킹을 통한 순열 생성 : 정수와 비트연산자를 사용 현 순열에서 사전 순으로 다음 순열 생성 ( NextPermutation ) 배열을 오름차순으로 정렬한 후 시작 아래 과정을 반복하여 사전 순으로 다음으로 큰 순열 생성 뒤쪽부터 탐색하며 교환위치 ( i-1 ) 찾기 ( i:꼭대기 ) 뒤쪽부터 탐색하며 교환위치 ( i-1 )와 교환할 큰 값 위치 ( j ) 찾기 두 위치 값 ( i-1, j ) 교환 꼭대기위치..
문제 풀이/Baekjoon 2021. 10. 26. [백준] S3 2407번 조합 (JAVA) 문제 출처 - Baekjoon Online Judge 문제는 여기 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net [문제] nCm을 출력한다. [입력] n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) [출력] nCm을 출력한다. [풀이] 1. 주어진 시간이 적기 때문에 dp로 풀었다. 2. long형의 범위를 벗어나기 때문에 BigInteger를 사용해야 한다. [접근] 1. 시간이 부족하다고 생각해 long형의 dp 배열을 만들어서 문제를 풀었다. 2. 하지만 long형의 범위를 벗어나는 경우가 있어 어떻게 처리해야 하는지 고민하였다. 3. 검색을 통해 알아보니 long형의 범위를 벗어날 ..
728x90

티스토리툴바