오답 노트 & 새로 알게 된 점 처음에 이 문제를 접근할 때, 조건 2개를 계속 생각했다. 1. 가로수를 같은 간격에 심기 2. 심어야 하는 가로수의 개수가 최소 그래서 갯수가 최소가 되기 위해서는 간격이 최대가 돼야 하며, 그 간격이 이미 심어져 있는 가로수와 일치해야 한다. 그래서 문제를 풀 때 배열로 입력받고, 그 간격들을 배열에 저장하였다. 그리고 그 간격들의 최대공약수를 구했고, 그 최대공약수를 간격으로 정했다. 사용 개념 유클리드 호제법(최대공약수) 코드 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 42 43 44 45 46 47 48 ..

오답 노트 & 새로 알게 된 점 처음에 isConditionTrue를 작성할 때, 행, 열에서 검사하는 것은 쉽게 생각했지만 3*3일 때는 검사를 하기 위해선 총 9개의 범위를 나눠야 하는 생각이 들었다. 하지만 이 9개 범위를 다 나누는 것은 효율적이지 않고, 어떠한 방법이 있을 것이라 생각했다. 그래서 구글링을 하여 힌트를 얻었다. - 이러한 문제를 풀 때, 규칙성을 찾고 구현하는 실력을 쌓아야겠다. 처음에 backTracking을 돌릴 때, sdk ArrayList에 저장되어 있는 것을 어떻게 꺼내올지가 고민이었다. 이게 무슨 말이냐면, 내가 스도쿠를 입력할 때 숫자가 0 이면 따로 ArrayList에 저장을 했는데, 이 ArrayList 안에 있는 좌표를 어떻게 꺼내올까라는 것이 고민이었다. 반복..

오답 노트 & 새로 알게 된 점 문제를 처음 볼 때, StringBuilder를 사용해서 isConditionTrue를 만족하면 sb에 넣고, 틀리면 sb에 있는 제일 끝에 있는 문자를 지우려고 했다. 하지만 sb는 전역 변수로 사용해서 조건식에 넣을 때마다 무조건 문자를 넣게 되고, 삭제를 해도 그 문자 그대로였다. 그래서 코드를 싹 다 갈아엎고, 처음부터 시작했다. int형으로 선언할지, String으로 선언할지 고민하다가 문제에서 N이 80 이하라고 하여, int형으로는 80자리를 받을 수 없어 String을 이용하기로 했다. 그리고 백트래킹을 무조건 하나를 추가하고 검사하고 다시 하나를 삭제한다. 이런 생각은 안 갖는 게 이 문제를 통해 알게 되었다. 나는 백트래킹이 무조건 하나를 추가하고 다음으..

오답 노트 & 새로 알게 된 점 처음 접근 방식은 백트래킹을 이용하여 치킨집을 0으로 만들고 다시 2로 설정해서, 거리를 구하려고 했다. 하지만 여기서 어떻게 제일 가까운 거리를 구해야 할지 전혀 방법이 떠오르지 않았다. 물론, 포문을 여러 개 사용하여 거리를 구할 수 있지만 시간 복잡도를 보니 무조건 TLE가 나올 것 같아 새로운 방법을 생각해보았다. 하지만 방법이 떠오르지 않아 구글링을 하여 힌트를 얻었다. 이러한 거리 계산이 나온다면 Point 클래스를 선언해주는 방법을 생각하자. 그리고 꼭 이차원 배열 안에서 생각하지 말자. 예를 들어 chicken과 home ArrayList를 만들어주어 좌표를 저장하는 방법. 어떻게 이런 생각을 하는지 정말 기발하다고 생각했다. 그리고 입력 순서대로 chick..

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

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

풀이 방법 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..