Dino Rudy

NextPermutation 함수란? NextPermutation은 말 그대로 다음 순열을 알아내는 함수입니다. 이때 다음 순열이란 사전 순으로 순열을 정렬했을 때 사전적으로 바로 다음번에 오는 순열이라는 뜻이죠 N개의 원소(원소 1~N)를 갖는 순열은 기본적으로 N! 개가 있습니다. 예를 들어 1,2,3의 순열은 사전 순으로 1,2,3 1,3,2 2,1,3 -이놈의 np? 2,3,1 -요놈 3,2,1 로 3! -> 6개 만약 2,1,3 다음의 순열을 알고 싶다! 이때 사용하는 게 nextPermutation입니다. 2,1,3의 다음 순열은 2,3,1이죠 다른 말로 하면 A라는 순열의 다음 순열 B는 사전적으로 A 바로 다음에 오는 순열입니다. 그렇다면 마지막 순열인 3,2,1의 다음 순열은? 없습니다...

Union-Find란? Union-Find는 서로소 집합을 표현할 수 있는 자료구조로 크게 Union과 Find라는 2가지 연산으로 이루어져 있어 Union-Find라고 불립니다. Union-Find를 구현 위해서는 union이라는 연산과 find라는 연산에 대해 이해할 수 있어야 합니다. Find 연산의 개념 find 연산의 목적은 어떤 원소가 어떤 집합에 속하여 있는지 알아내는 연산입니다. 예를 들어 a, b, c, d라는 각각의 원소가 있다고 가정할 때 해당 원소가 어떤 집합에 속하여 있는지 알아내는 연산으로 find(a), find(b) 등을 통하여 해당 원소가 어떤 집합인지 알 수 있어야 합니다. find 연산을 구현하기 위해서는 해당 원소들이 어떤 집합에 포함되어 있는지 알 수 있는 자료구조(..

객체 배열 Arrays.sort()와 Comparator를 이용해 정렬 java.util.Arrays에서 제공하는 많은 메서드 중 정렬 메서드가 있습니다. 위 이미지에서 확인할 수 있듯이 Arrays에서 제공하는 sort()는 배열을 파라미터로 받습니다. 따라서 Collections에 포함되는 ArrayList나 LinkedList 타입은 Arrays.sort()의 파라미터가 되지 못합니다. Arrays.sort()에 배열이 입력값으로 들어가게 되는데 일반적인 primitive 타입을 원소로 갖는 배열은 원소끼리의 비교가 가능하게 되어있습니다. 하지만 사용자가 정의한 클래스로부터 객체 배열을 생성한 경우 무엇을 기준으로 비교를 할지 기준을 정해줘야 합니다. 어떤 기준으로 정렬을 할지를 Comparator..

조합 2차원 배열에서 R개의 원소를 뽑는 조합입니다. 기본적인 방법은 조합과 유사하지만 뽑고자하는 원소의 행과 열을 뽑는 방법으로 나누기와 모듈러 연산을 사용합니다. import java.util.Arrays; //2차원 배열에서 조합! public class Combination2 { static int [][] arr; static int [][]selected; static int N,M,R; static public void makeCombination(int cnt, int start) { if(cnt==R) { System.out.println(Arrays.deepToString(selected)); }else { for(int i=start;i

순열 조합에 이어 알고리즘 문제를 풀 때 많이 쓰이는 순열입니다. 순열은 조합과 다르게 순서가 중요합니다. 순열은 nPr로 표현 할 수 있으며 n개중 r개를 뽑아 나열하는 수열입니다. 구현할 때 조합과 가장 큰 차이점은 isSelected라는 boolean 배열을 만들었다는 점과 조합은 for구문에서 start부터 시작했는데 순열은 i=0부터 시작합니다. import java.util.Arrays; public class BasicPermutation { static int [] selected; static boolean [] isSelected; static int count; static void makePermutation(int[] arr, int R, int cnt) { //순열을 만들때 끝나..

조합 알고리즘 문제풀이를 하다 보면 조합을 구해야 하는 경우가 많습니다. 대표적으로 BruteForce 문제 같은 경우, 여러 가지 경우를 시도해야 하는데 이때 조합, 중복조합, 순열, 중복순열, 부분집합 등이 쓰일 때가 많습니다. Python이나 C++ 같은 경우 라이브러리가 제공되지만 JAVA 같은 경우 내부 라이브러리에서 조합과 순열 등을 제공하지 않고 구글? 에서 제공하는 라이브러리를 이용하면 된다고 들었습니다. 하지만! 구현이 그렇게 어려운 것도 아니고 라이브러리에 의존하지 않는 게 좋다고 들어서 배우고 공부한 내용을 토대로 구현을 해보았습니다. import java.util.Arrays; public class Combination { static int [] selected; static i..