오답 노트 & 새로 알게 된 점 백트래킹 문제를 풀면서 재귀 함수의 인자로 항상 count(depth)로만 설정하여 문제를 풀었다. 그런데 시간 초과가 나와서 앞으로는 start점을 설정해서 돌려야 하겠다는 점을 깨달았다. 풀이 방법 이 문제는 어느 백트래킹 문제와 매우 유사한 문제이다. 단지 애먹었던 부분은 diffSum 부분에서 visit[] 에서 true인 부분들을 어떻게 나열하여 어떻게 arr[][]에 넣어서 더할 수 있을까라는 생각을 했다. 예를 들어 1 2 3이 팀이고, 4 5 6이 팀인데, 여기서 또 2개씩 뽑아서 arr의 index에 넣어 값을 더해야 하는데 여기서 그러면 1 2 3에서 또 숫자를 두 개 뽑아야 하는구나라는 생각이 들었다. 그래서 아 문제가 복잡해지겠구나 했는데, 그냥 처음..

오답 노트 & 새로 알게 된 점 N-Queen 문제는 대표적인 백트래킹 문제로 많은 사람들이 풀었다. 그래서 대표적인 문제는 꼭 맞아야겠다고 생각했다. 처음에는 visit, arr 이차원 배열, 퀸을 놓으면 대각선을 다 지우는 메소드, 범위를 확인하는 메소드를 만들어 문제를 해결하려 했다. 하지만 이 대각선은 우상, 우하, 왼상, 왼하 다 지우고 배열을 하나하나 다 들어갈 때마다 실행하는 게 시간 복잡도가 넘을 것 같아서 다른 방법을 생각해보았다. 하지만 떠오르지 않았고 구글에 검색하여 어떻게 접근했는지 힌트를 얻었다. 문제를 그대로 보지 말고 어떻게 풀어볼지 생각을 하자. 이차원 배열이 나왔다해서 무작정 이차원 배열만으로 생각하지 말고, 유연하게 생각하는 습관을 기르자. 새로 알게된 점은 대각선을 나타..

에라토스테네스의 체 시간 복잡도 에라토스테네스의 체는 소수를 찾는 방법이다. 대량 소수를 찾는데 최적화된 방법이다. 원래 두 수 사이의 소수를 구하려면 시간 복잡도가 아마 O(N^2)가 걸릴 텐데, 에라토스테네스의 체를 이용하면 O(Nlog(logN))이 된다. 그래서 많은 소수를 구하려면 이 방법을 사용해야 TLE가 걸리지 않는다. 에라토스테네스의 체 개념 소수의 배수들을 체크하여 체크하지 않은 곳이 바로 소수이다. 구하려는 소수의 범위에서 2, 3, 5, 7 ... √n까지의 배수들을 체크하고, 체크하지 않은 곳들을 출력하면 소수들을 구할 수 있다. 에라토스테네스의 체 구현코드 1 2 3 4 5 6 7 8 9 10 11 12 import java.io.*; import java.util.*; publ..

풀이 방법 1 두 수를 입력받아 두 수중 최대 최솟값을 구한다. 그래서 for문으로 1부터 최솟값까지 i로 나누어 둘 다 나머지가 0이 되는 것 중에 최댓값을 구한다. 이것이 최대공약수이다. 그리고 두 수를 곱하고 최대공약수로 나눈 것이 최소공배수가 된다. 사용 개념 1 최소 공배수 = 두 수 곱 / 최대 공약수 코드 1(유클리드 호제법 사용 X) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader ..

풀이 방법 boolean형 visit배열을 전부 true로 초기화시켜 visit의 index가 소수일 경우 값을 true로, 아닐 경우는 false로 바꾸었다. 그래서 마지막에 visit 값이 true인 곳만 출력시켜 답을 구했다. 소수를 판별하는 것은 에라토스테네스의 체 개념을 사용하여 구현했다. 사용 개념 에라토스테네스의 체 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedRea..

풀이 방법 수를 입력받으면, 2부터 그 수까지 나눈 나머지가 0이 되는 수가 있으면 소수가 아니고, 없으면 소수이다. 그래서 findPrime 메소드를 사용하여 boolean 값을 리턴 받은 후, 리턴 값이 true이면 소수의 개수를 늘렸다. 사용 개념 소수 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRea..

풀이 방법 1과 자기 자신을 제외한 약수를 입력값으로 준다. 그래서 처음에 입력을 내림차순으로 입력할 줄 알고, 입력값들을 배열에 저장한 뒤, arr[0] * arr[arr.length-1]이라고 계산을 했다. 문제를 틀리고 난 뒤, 내림차순이 아닐 것 같다는 생각이 들어 배열에 값을 넣을 때, 최대 최솟값을 구하여 둘을 곱했다. 사용 개념 최대 최소 구하기 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Buffer..

풀이 방법 문제를 다 풀고 나서, 카테고리를 보았는데 dp로 되어있었다. 하지만 처음에는 백트레킹 문제라고 생각하여 백트레킹으로 문제를 해결했다. 값은 어차피 1, 2, 3만 이용할 수 있어, 배열을 만들 때 1, 2, 3으로 바로 초기화를 시켰다. 그리고 중요한 점은 중복이 가능했기 때문에 visit배열을 사용할 필요가 없고, 메소드 인자로 start를 사용하여 시작점을 설정할 필요도 없었다. 문제 해결을 하면서 가장 애먹었던 부분은 메소드를 작성할 때, 1 1 1 1 1을 만족하지 않으면 1 1 1 2로 넘어가는 과정에서, sum값이 계속해서 더해져 갔다. 그래서 resum이라는 변수를 사용하여, 그 해당 메소드 인자인 sum을 저장하였다. 그래서 sum값이 재귀 함수로 인해 다시 돌아와도 계속해서 ..

풀이 방법 이 문제는 배열을 집합이라 생각하고, 부분 집합들의 원소들의 합이 주어진 합을 만족시키면 count를 ++해주는 방식으로 생각했다. backTracking 함수를 호출할 때, 인자에 sum을 1222222를 넣었다. 왜냐하면 만약 주어진 합이 0일 때, 처음에 인자를 0으로 보낸다면 count를 늘리고 시작해서 답이 틀리게 된다. 그래서 주어진 조건을 보면 sum은 절댓값 1,000,000보다 작거나 같다고 주어져있어서, 이 조건을 뛰어넘는 숫자를 대입하여 그러한 실수를 방지했다. 사용 개념 재귀 함수 코드 package BackTracking; import java.io.*; import java.util.*; public class BOJ1182 { static int[] arr; stat..

풀이 방법 문제에 처음 접근했을 때, priority라는 배열에 우선순위를 저장하고, q에는 문서를 0부터 넣는다.(문제에서 문서 제일 왼쪽을 0이라 함) 그리고 target은 index로 생각했다. 세 번째 태케로 예를 들면, 큐 : 0 1 2 3 4 5 priority 배열 : 1 1 9 1 1 1 index : 0 1 2 3 4 5 target : 0 target은 index를 가리킨다. 따라서 1. findMax() 를 통해 priority 배열에서 가장 큰 우선순위를 얻는다. 2. 큐에서 poll 한 값을 element에 저장한다. 2-1. 만약에 priority[element]가 가장 큰 우선순위라면 q에서 빼냈으므로 cnt를 1 증가시키고, 다음 max값을 구하는데 오류가 나지 않으려면 해당..

풀이 방법 문제에 처음 접근했을 때는 원형 큐를 생각했다. 그래서 처음 index를 -1로 설정하고, (index + K) % q.size()로 풀려고 했다. 하지만 해당 index의 값을 삭제할 순 없었고, 0으로 설정을 했는데 index가 그대로 남아 0인 부분을 뛰어넘을 수 없어서 답이 나오질 않았다. 다시 생각해보니 큐를 만들고, 제일 앞의 두 개를 뒤로 넘기면 제일 앞에 있는 숫자가 3번째 숫자임을 깨달았다. 1 2 3 4 5 6 7 에서 1 2 를 뒤로 보낸다. 3 4 5 6 7 1 2 에서 poll()을 사용하면 3이 나오게 된다. 4 5 6 7 1 2 에서 또 4 5 를 뒤로 보낸다. 6 7 1 2 4 5 에서 poll()을 사용하면 6이 나오게 된다. 그래서 이 방법을 생각하고 while..

풀이 방법 stack 클래스를 이용하여 문제를 풀었다. 1. '(' 을 받으면 push 2. ')'을 받을 때 2-1. stack이 비어있으면 VPS가 아님 2-2. stack이 비어있지 않으면 pop한다. 3. 스택이 비어있으면 VPS이고, 스텍이 비어있지 않으면 VPS가 아님. 사용 개념 stack 소스 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 package Data_Structure; import java.util.*; import java.io.*; public class Main { static Stack stack; static St..