일단 해보자

학습 목적- DFS 중에 combination을 활용해야 하는 문제를 익숙하게 풀기 위해서 학습 방법- 쉬운 문제부터 단계적으로 활용해보자 1단계) 기본 조합 문제[문제]N개의 숫자가 주어질 때, 그중에서 M개를 뽑는 모든 조합을 구하시오. (중복 허용x) [입력]N = 4, M = 2 nums = [1, 2, 3, 4] [출력]1 2 1 3 1 4 2 3 2 4 3 4 [코드] public class Main { static int[] nums = {1,2,3,4}; static int[] arr; static int n,m; public static void main(String[] args) throws IOException{ n = 4; ..

3단계[문제]  N개의 숫자 중 M개를 선택하는 조합을 구한 뒤, 선택한 숫자들의 곱을 최대로 하는 조합을 찾아라. [입력]N = 4, M = 2nums = [1, 5, 3, 2] [출력]5 3 [접근 방법] 1. DFS로 모든 조합을 탐색하면서 arr에 조합을 담고, 매번 곱을 계산 2-1. dfs반복 횟수 (depth가 M번이랑 같을 때) => 곱한 값과 최댓 값을 비교해서 갱신한다.2-2. 곱을 갱신하면서 최대의 곱한 값을 만든 조합의 수를 ans배열에 복사한다. [코드]public class Main { static int N, M, K; static int[] arr; static int[] ans; static long max = 0; // 오버플로우 방지를 위해 lon..

문제 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 입력 첫째 줄에 N이 주어진다.둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다. 출력 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다. => 무슨 소리지...??? 요약 수직선 위에 N개의 좌표의 => 각 번호가 몇 번째로 큰 숫자인지 출력 (압축)EX) 1 2 1 5 3 (총 5개 좌표) => 압축 0 1 0 3 2  => 1이 0..

1. 기본 정렬 => 사전 순으로 정렬- 오름차순 정렬 [Collections.sort(list) ]public class Main { public static void main(String[] args) throws IOException{ List list = Arrays.asList(3,1,4,2); Collections.sort(list); for(int i : list){ System.out.print(i + " "); // apple banana kiwi pear } }}- 내림차순 정렬 [ Collections.sort(list, Collections.reverseOrder())  ]public class Main..

배열 문제에서 Stream 활용 1. 배열 내에 'target' 값이 몇 개 포함 되어있는지 카운트 => filter(), count() 사용int[] arr = {1,1,3,3,4};long count = Arrays.stream(arr) // 배열을 Stream으로 변환 .filter(num -> num == 3) // 3과 같은 숫자만 필터링 .count(); // 필터링된 요소 개수를 카운트 System.out.println(cnt) // 출력: 2/* long cnt = IntStream.of(arr) .filter(num -> num == 3) .count(); */  2. 배열 내에 target 값보다 작은 수를 모두 찾아 배열..

- 그래프를 모양을 보고 => 인접 리스트 형태로 구현 =>   ArrayList> graph- 그래프는 총 4가지 종류 - 무방향 , 방향 , 가중치 무방향 , 가중치 방향- 가중치가 있을 때 구현하는 방법은? 1. 무방향 그래프 구현 Codepublic class Main{ static ArrayList> graph; public static void main(String[] args) throws IOException{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; // n: 정점의 갯수 , m: 간선의 갯수 int n..

- 그래프 모양을 보고 => 2차원 배열(행렬) 형태로 구현 => int[][] graph; -  그래프는 총 4가지 종류 - 무방향 , 방향 , 가중치 무방향 , 가중치 방향 1. 무방향 그래프  구현 Codepublic class Main{ static int[][] graph; public static void main(String[] args) throws IOException{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; // n: 정점의 갯수 , m: 간선의 갯수 int n = 5; int m = 5..

개념) i번째 숫자보다 앞에 있는 숫자들이 더 작다면 뒤로 밀리면서 정렬 즉, i번째의 값이 자기 자리에 삽이되면서 정렬 Code) public static int[] insertionSort(int[] nums){ for(int i=1; i=0 && nums[j] > target){ nums[j+1] = nums[j]; j--; } nums[j+1] = target; } return nums; } 전체 Code) import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; impor..

개념) 1.앞의 값과 바로 뒤에 값을 비교한다. 2. 뒤에 값이 더 작다면 자리를 바꾼다. (아니라면 변경 x) 정렬 Code) public static int[] bubbleSort(int[] nums){ for(int i=0; i

개념) 1. 배열의 앞에서 부터 가장 작은 수를 찾아낸다. 2. 배열의 현재 앞의 값보다 뒤에 작은 값이 있다면 두 수의 위치를 변경한다. 정렬 Code) public static int[] selectionSort(int[] nums){ for(int i=0; i