-

# 주소 https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net # 문제 # 문제 해설 및 코드 리뷰 import java.util.*; public class Main { public static boolean[] visit; public static int[] arr; public static int N, M; public static int[] ans; public static StringBuilder sb = new StringBuil..

# 주소 https://www.acmicpc.net/submit/15652/33669457 로그인 www.acmicpc.net # 문제 # 문제 해석 저번 문제처럼 간단했다. 이번엔 중복을 허용하여 비내림차순(중복허용하여 오름차순)으로 경우의 수를 구하는 것이다. 특히, t = i라고 선언하고 for문을 i = t 부터 시작점을 잡아야 두번째 항, 세번째 항의 값을 구할 때 이전 위치의 항보다 작지 않은 값을 가질 수 있다. 코드로 보면 빠르게 이해할 수 있을 것이다. import java.util.*; public class Main { public static int[] arr; public static int N, M; public static StringBuilder sb = new StringB..

# 주소 www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net # 문제 # 문제 분석 이번에도 백트래킹을 이용하여 문제를 해결해야 합니다. 이번엔 저번 문제처럼 간단히 해결할 수 있습니다. 다만 중복을 허용하여 경우의 수를 따지는 것이므로 코드를 작성할 때 arr의 값은 i로 통일하되 arr[depth +1]만 해주어 이전 문제와 마찬가지로 depth == M일 때에만 출력하고 return 하는 방식을 취했습니다. 따라서 dfs함수를 작성하는 방식에 있어서 인수..

# 코드 해설 이번엔 저번 문제의 N과 M(1) 보다 훨씬 간단한 문제입니다. 중복된 수열에 대해서는 따로 신경 쓸 필요가 없기 때문에 단순히 for문에 대해서 증가되는 수열 값만 출력해주면 되겠습니다. import java.util.Scanner; public class Main { public static int[] arr; public static int N, M; public static void main(String[] args) { Scanner in = new Scanner(System.in); N = in.nextInt(); M = in.nextInt(); arr = new int[M]; dfs(1, 0); } public static void dfs(int at, int depth) { ..

문제 해석 알고리즘 기법 중에는 백트래킹(Back-Tracking)이라는 기법이 있다. 되추적이라는 의미로서 어떤 노드의 유망성을 판단한 뒤 해낭 노드가 유망하지 않을 경우 부모 노드로 돌아가 다른 자식 노드를 찾는 알고리즘의 기법이다. 즉 모든 경우의 수를 찾는다는 점에서 BFS와 비슷하지만 그 중에서도 가능성이 있는 노드의 경우의 수만 찾는 기법이라고 할 수 있다. 나도 아직 공부하는 입장이라 백트래킹, 브루트포스 깊이우선탐색(DFS)의 정확한 차이를 쉽게 구분하기 어려워 여러 사이트의 정보를 인용하여 블로그를 작성하였다. 만약 지나가다 들렀으면 잘 이해하고 넘어가길 바란다. 예를 들어 "a + b + c + d = 10"을 만족하는 모든 경우의 수를 구하시오 (단, a,b,c,d는 0이 아닌 정수)..

문제 설명 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다. 제한 조건 strings는 길이 1 이상, 50이하인 배열입니다. strings의 원소는 소문자 알파벳으로 이루어져 있습니다. strings의 원소는 길이 1 이상, 100이하인 문자열입니다. 모든 strings의 원소의 길이는 n보다 큽니다. 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다. 입출력 예 strings n return ["abce", "..