개발 공부~

https://www.acmicpc.net/problem/14889 N/2명씩 두 팀(Start / Link)으로 나눠야 함 각 팀 능력치: 팀에 속한 (i, j) 쌍들에 대해 S[i][j] + S[j][i] 합 두 팀 능력치 차이의 최솟값 구하기 => 모든 경우를 보면서 각 경우마다 능력치 차이를 계산하고, 그 중 최소값을 찾는 완전탐색 + 백트래킹 start[i] == true : i번 사람은 스타트 팀 start[i] == false : i번 사람은 링크 팀 dfs(indx, cnt) - indx: 지금 몇 번째 사람을 보고 있는지 (0 ~ n-1), cnt: 지금까지 스타트 팀에 몇 명을 뽑았는지 각 사람에 대해 두 가지 선택선택: 이번 사람을 스타트 팀에 넣는다 -> start[ind..

https://www.acmicpc.net/problem/10974 모두 한 번씩만 사용해서 만들 수 있는 순열을 사전순으로 모두 출력각 자리에 어떤 숫자를 쓸지 하나씩 결정 -> 1~N 중 아직 쓰지 않은 숫자 하나를 넣기모든 자리가 채워졌다면 -> 하나의 순열 완성depth = 현재까지 채운 인덱스 개수이미 사용한 숫자는 visited[i]로 체크 import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.*;public class Main { static..

https://www.acmicpc.net/problem/14888 연산자들의 순서를 어떻게 배치하느냐에 따라 결과가 달라짐 -> 그 중 최소/최대를 찾는 완전탐색 문제가능한 모든 연산자 순열을 다 해보기 -> 수가 적어서 DFS + 백트래래킹총 숫자 개수: n숫자 사이에 들어가는 연산자 개수: n-1각 위치에 어떤 연산자를 쓸지 전부 골라야 한다.depth = 지금까지 사용한 연산자 개수, cur = 지금까지 계산된 현재 값=> depth == n-1 이 되면 모든 연산자를 다 쓴 상태 -> 이때의 cur 값으로 max, min을 갱신연산자 하나 쓰면 op[x]-- 하고재귀를 들어갔다 온 다음 다시 op[x]++ 해서 되돌리기 import java.io.BufferedReader;import jav..

https://www.acmicpc.net/problem/2529 조건: 숫자의 개수 n+1개, 중복 불가, 각 자리에서 이전 부등호 조건을 만족, 그중에서의 최댓값/최솟값 출력-> 조건이 많아서 처음엔 막막했다-> 게다가 0이 앞자리인 경우까지 포함시켜서 비교해야함 --> String으로 비교하자! "그렇다면 모든 결과(String)를 String 리스트에 넣고 정렬한 뒤에 최댓값/최솟값을 출력하자" visited[10] : 중복 불가 길이가 n+1이 되면 문자열 cur을 그대로 list에 넣는다 처음 자리(depth == 0)는 이전 숫자가 없으므로 검사 안함 부등호를 만족하지 않는다면? dfs 호출 없음depth-1이 지금 숫자를 만족시켜야하는 부등호의 인덱스이자 문자열에서는 이전 문자를 가..

https://www.acmicpc.net/problem/6603 번호 6개를 골라 로또 번호를 만들기중복 선택 X순서 상관 XDFS + 시작 인덱스(start)를 이용 배열로 결과 만든 버전import java.io.BufferedWriter;import java.io.IOException;import java.io.OutputStreamWriter;import java.util.*;public class Main { static int n; static BufferedWriter bw; static int[] answer; static int[] rotto; public static void dfs(int depth, int start) throws IOException { if(depth==6)..

https://www.acmicpc.net/problem/1759 서로 다른 C개의 알파벳이 주어졌을 때, 그 중에서 길이가 L인 암호 만들기그 중에서 모음 ≥ 1 자음 ≥ 2 만족하는 암호를 사전순으로 출력dfs()이미 사용한 인덱스보다 앞으로 되돌아가지 않게 해서 다음에 선택할 수 있는 알파벳의 시작 인덱스 설정현재까지 depth개의 문자를 골랐고 다음에는 alp[start] 이후의 문자들만 선택 가능배열로 만든 버전import java.io.BufferedWriter;import java.io.IOException;import java.io.OutputStreamWriter;import java.util.*;public class Main { static int l; static int c; st..

https://www.acmicpc.net/problem/1182 각 숫자에 대해 포함 여부를 결정 -> dfs 두가지로 가지치기모든 숫자에 대해 포함 여부가 결정 되면 합 검사다만,아무것도 선택하지 않는 경우(공집합)는 제외해야함import java.util.*;public class Main { static int n; static int s; static int answer; static int[] nums; public static void dfs(int depth, int cur) { if(depth==n) { if(cur == s) { answer++; }return; } dfs(depth+1,nums[depth]+cur); dfs(depth+1,cur);..

https://www.acmicpc.net/problem/15652 (1) 순열(2) 조합(3) 중복 순열 (4) 중복이 허용되면서 오름차순(정확히는 비내림차순) 인 수열을 만드는 문제즉, 시작점 중복 허용 -> 시작점을 i 로 하면 된다작은 값을 배제하기 위해 시작점을 설정 -> 비내림차순 보장 import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.*;public class Main { static int n; static int m; static int..