Java/Algorithms

문제 접근 방식 주어진 수들로 부분수열을 만들어 합이 S가 되는 경우에 카운트를 1씩 늘려주면 된다. N과 M 시리즈 문제들과 비슷하게 풀면서 카운팅만 해주면 되는데 조심해야 할 부분은 [-3, -2, 5], [-3, 5, -2], [-2, -3, 5], [-2, 5, 3] 같이 똑같은 수가 들어가고 순서만 다른 경우는 모두 하나의 수열로 취급해야 한다. 이제 재귀를 통해 수열을 만들어주면서 수의 합이 S인 경우 카운팅을 해주면 되고 재귀의 기저조건은 만들어진 수열의 크기가 N과 같은 경우지만 1 ~ N까지의 수열의 크기를 만들 때마다 sum이 S와 같은지 확인해줘야 한다. 풀이 public class Main { private static int n; private static int s; privat..

문제 접근 방식 N * N 크기의 체스판에 N개의 퀸들이 서로 공격하지 않게 놓으려면 우선 퀸의 공격 범위를 알아야 한다. 퀸은 가로와 세로의 직선과 대각선 모두 자신이 이동하고 싶은 만큼 이동할 수 있는데 이 말은 퀸과 같은 행이나 열 혹은 같은 좌표의 기울기를 가진 대각선을 제외한 곳에만 퀸을 둘 수 있다는 것이다. N과 M시리즈를 풀면서 많이 사용했던 사용 여부를 기록하던 배열 방법을 사용해서 풀면 생각보다 쉽게 풀 수 있다. 우선 위와 같이 퀸이 하나 존재 한다면 같은 행과 열에는 다른 퀸을 둘 수가 없으니 한 줄에는 하나의 퀸만 둘 수 있고 모든 줄에 퀸이 존재한다면 모든 퀸들이 서로 공격 하지 못하는 위치에 존재하게 되니 이를 재귀 함수의 기저 조건으로 지정해 주면 된다. (X == N) 다음..

문제 접근 방식 11번 문제에 조건 하나만 더 추가된 문제로 다음 인덱스를 뽑을 때마다 이전 인덱스 이전의 값을 제외한 동일한 인덱스 부터의 값만 뽑을 수 있다. 재귀 호출 시 두 번째 인자로 넘겨주던 시작 인덱스 값을 현재 호출 스택에서 사용 중인 시작 인덱스를 넘겨주면 된다. 풀이 public class Main { private static StringBuilder sb = new StringBuilder(); private static int n; private static int m; private static int[] arr; private static int[] sequence; public static void main(String[] args) throws IOException { Bu..

문제 접근 방식 같은 수를 여러번 골라도 상관 없지만 이전 글에서와 같이 9a, 9b 같은 값이 9로 동일한 경우는 순서가 바껴도 똑같기 때문에 이 부분만 중복으로 취급하여 넘어가주면 된다. 풀이 public class Main { private static StringBuilder sb = new StringBuilder(); private static int n; private static int m; private static int[] arr; private static int[] sequence; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStre..

문제 접근 방식 수열 [1, 7]과 수열 [7, 1]을 같은 경우로 취급하여 오름차순으로 출력하기 위해 [1, 7]만 출력해야 한다. 그러면 [1, 7, 8, 9, 9] 라는 배열이 주어졌을 때 1로 시작하는 경우의 수가 7로 시작하는 경우보다 많을 것이고 8보다는 7이, 9보다는 8이 경우의 수가 더 많아지는 시작에서 끝으로 갈수록 경우의 수가 적어지는 규칙이 있다. 즉 정렬된 배열에서 이미 사용한 인덱스는 다시 사용할 필요가 없기 때문에 재귀 메서드의 파라미터로 인덱스를 추가로 전달해준다. 풀이 public class Main { private static StringBuilder sb = new StringBuilder(); private static int n; private static int ..

문제 접근 방식 주어진 수들을 정렬하여 오름차순으로 출력하는건 이전 문제들과 똑같지만 이미 뽑은 수를 재사용하면 안되고 중복된 수열은 제외해야 한다는 조건이 붙었다. 중복된 수열을 제외하는 부분이 많이 힘들었는데 이미 뽑은 수를 체크하는 배열 외에도 현재 재귀 호출에서 이전에 뽑은 수를 기록해둘 지역변수를 하나 추가해서 해결했다. 예를 들어 [1, 7, 9, 9] 같은 수들이 주어진 경우 두 번 등장하는 9를 각각 9a, 9b라고 했을 때 1 7 9a 9b와 1 7 9b 9a는 같은 수열로 취급하여 하나만 출력해야 하는데 이때 9a를 이전에 사용한 값이라고 저장해둘 지역변수에 담아두면 나중에 1 7 까지 뽑고 9b를 뽑는 순간에 비교하여 넘어갈 수 있다. 글로 적으려니 설명을 잘 못하겠어서 재귀 호출 순..

문제 접근 방식 1231 1231 1231 1231 1231 1231 1231 1232 1231 1231 1231 1233 1231 1231 1231 1234 1231 1231 1232 1232 1231 1231 1232 1233 1231 1231 1232 1234 1231 1231 1233 1233 1231 1231 1233 1234 1231 1231 1234 1234 1231 1232 1232 1232 1231 1232 1232 1233 1231 1232 1232 1234 1231 1232 1233 1233 1231 1232 1233 1234 1231 1232 1234 1234 1231 1233 1233 1233 1231 1233 1233 1234 1231 1233 1234 1234 1231 1234..

문제 접근 방식 주어진 배열을 정렬하여 중복해서 선택할 때 M개의 수를 고르는 모든 경우를 출력하면 된다. 모든 수를 중복해서 계속 사용할 수 있기 때문에 사용 여부를 체크하거나 인덱스에 변화를 줄 필요 없이 계속해서 재귀호출과 M번의 반복문을 돌아주면 된다. 풀이 public class Main { private static StringBuilder sb = new StringBuilder(); private static int n; private static int m; private static int[] arr; private static int[] sequence; public static void main(String[] args) throws IOException { BufferedReade..