= 내가 접근한 방법 = 처음 작성한 dfs 함수다. 이 메서드의 문제점은 2개까지는 구할 수 있어도 => n = 4일 때만 가능하고 n = 6일 때 부터 불가능했다. n = 6일 때, 1-2-3 vs 4-5-6 이렇게 팀을 이루는 건데 내가 짠 함수로는 1-2, 3-4, 5-6 이런 식으로 진행이 되기 때문에 당연히 오답. public static void dfs(int n, int depth) { // System.out.println("depth = " + depth); if (depth == n / 2) { for (int i = 0; i < depth; i++) { System.out.println("result: " + temp[i]); } int check = Math.abs(temp[0] ..
= 접근 방법 = NxN 배열 A A[i][j] = i * j 이 수를 일차원 배열 B에 넣으면 B의 크기는 NxN이 된다. B[k]를 구해보자 N = 3, B = 7일 때 b[7] = 6이 문제에서 주어졌다. 문제를 그래도 만들어보자, int[][] A = new int[3][3] 그동안 우리가 해왔던 이분 탐색 문제들은 단순하게 주어진 값을 이용해서 반으로 나누는 식으로 어떻게든 2중 for문 시간 복잡도 O(N^2)이 아닌, O(logN)형식으로 만들면 되는 거였다. 이 문제가 어려운 이유는? => 지금까지 풀어왔던 틀에서 완전히 벗어나 새로운 규칙을 발견하고 응용해야 된다. 입력) 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수 이 문장을 봤을 때, 순수하게 배열을 그대로 만든다면..
= 문제 접근 방법 ( 틀림 ) = 내가 접근한 방법은 공유기를 하나 하나 다 설치해보고 그거에 최댓값을 찾는 식으로 했었다. 애초에 끝까지 구현도 못한 방식이라 어떻게 말해야 될지 모르겠다.. 이분 탐색 파트에서 1번 2번 문제는 이해했고 어떻게 접근하면 되는 건지 깨달았는데 이런식으로 조금만 문제가 다르게 나오고, 응용이 필요하면 항상 틀린다. 더 깊게 생각하고 여러 문제를 풀면서 사고력을 키워야겠다. = 해결 = 우리가 그동안 해왔던 방식이랑 매우 비슷하다. 인덱스에서 절반을 나누고, 최댓값을 찾는 식으로 구현했었다. 이 문제도 똑같다. 단지, 응용하고 사고력이 필요했던 문제다. 주어진 식으로 최댓값을 찾냐 아니면 주어진 식을 이용해서 결과를 최대로 만드냐 ? 이런 느낌이라고 보면 된다. 숫자 찾기..
= 처음 접근 방법 (틀림) = 이 문제는 시간 초과로 틀렸다. https://byungil.tistory.com/210 백준 - 이분 탐색 1654번 랜선 자르기 / 풀이,오답 = 처음 접근 방법 (틀림) = 접근을 못했다. 숫자 카드2를 응용해서 풀 수 있는 문제였는데, index로만 생각해봤지 이렇게 길이를 쪼개서 이분 탐색을 한다는 것을 새로 배웠다. 구글링을 통해 다른 byungil.tistory.com 이 문제랑 접근 방법, 풀이까지 거의 일치한다고 보면 된다. 똑같은 문제인데 왜 틀렸을까... 좀 더 고민하고 응용 능력을 키워야겠다. upperBound를 이용해서 해결하지 않았기 때문에 틀렸다. 상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이 문장..
= 처음 접근 방법 (틀림) = 접근을 못했다. 숫자 카드2를 응용해서 풀 수 있는 문제였는데, index로만 생각해봤지 이렇게 길이를 쪼개서 이분 탐색을 한다는 것을 새로 배웠다. 구글링을 통해 다른 사람의 풀이를 보고도 이해하는데 조금 오래걸렸다. 되게 단순한 문제였는데 더 열심히해야겠다. = 풀이 = 어떻게 접근해서 해결했는지 알아보자 https://byungil.tistory.com/205 백준 - 이분 탐색 10816 숫자 카드2 문제 / 복습 자세한 풀이 https://byungil.tistory.com/186 백준 - 집합과 맵 10816번 숫자 카드2 / 이분 탐색을 활용 ( 중복값 ) = 내가 접근한 방법 = 숫자 카드1 문제랑 똑같이 접근했다. Map을 이용해서 Map의 메서드 getO..
= 접근 과정 ( 틀림 ) = 이렇게 N개의 전구와, K가지의 색 => 최대 200개의 전구, 최대 20개의 색이므로 완전 탐색을 이용하면 시간 초과로 분명히 오답! => O(N!), 이유는 N개의 색이 모두 다 다를 수 있기 때문 이러한 문제는 DP를 이용해서 시간을 줄이는게 핵심이다. 처음 나는 재귀 함수를 이용해서, 이미 거친 전구들은 return하는 형식으로 문제를 접근했다. 1. int[] arr = new int[n] 배열에 1, 1, 2, 3, 3, 3, 2, 2, 1, 1의 값을 넣고 0번 index의 값을 2로 바꿨을 때, 인접한 값(1번 index)이 0번째 값(1)이랑 같을 때 같이 2로 변경해주고 아니면 return을 하는 형식으로 count를 했다. 2. 모든 값이 k로 다 통일 ..
