= 접근 방법 = 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/186 백준 - 집합과 맵 10816번 숫자 카드2 / 이분 탐색을 활용 ( 중복값 ) = 내가 접근한 방법 = 숫자 카드1 문제랑 똑같이 접근했다. Map을 이용해서 Map의 메서드 getOrDefault를 활용하는 방식으로 해결했는데 이 문제도 이분 탐색을 이용해서 풀어야 되는 문제였다. 지난 byungil.tistory.com = 접근 방법 = 1. 단순 for문을 이용하면 시간 초과, 따라서 이분 탐색 알고리즘을 활용해서 시간 복잡도 O(logN)로 풀자. 2. 중복값이 허용되는 문제이기 때문에 내가 찾는 숫자의 최소 index와 최대 index를 구해서 개수를 확인하자. 예를 들면, 1 1 2 2 5 => index: 0 1 2 3 ..
= 내가 접근 방법 ( 틀림 ) = 처음 내가 접근한 방법은 부분합을 구할 때 사용한 알고리즘을 이용했다. 처음 합은 0 0
= 접근 방법 = 2중 for문을 이용하면 분명 시간 초과로 실패하기 때문에 이분 탐색을 알고리즘을 이용해서 시간 복잡도를 O(logN)으로 해결하자. 1. n개의 정수를 담은 배열을 정렬한다. ( Arrays.sort ) 2. 이분 탐색 알고리즘으로 m개의 정수가 존재하는지 확인한다. 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 49 50 51 52 53 54 55 56 57 import java.io.BufferedReader; import java.io.IOException; import java.io.I..
= 내가 접근한 방법 = 숫자 카드1 문제랑 똑같이 접근했다. Map을 이용해서 Map의 메서드 getOrDefault를 활용하는 방식으로 해결했는데 이 문제도 이분 탐색을 이용해서 풀어야 되는 문제였다. 지난 숫자 카드1보다는 조금 더 간결하게 코드를 짜긴 했지만, 결국 이분 탐색이 핵심이다. getOrDefault라는 메서드는 card라는 맵 안에 내가 입력한 값이 있으면 그 key의 밸류를 갖고오는 것이고 없으면 defaultValue ( 내가 지정한 값 ) 0을 넣는 메서드다. 이 메서드를 활용하면 이분 탐색을 안 하고 쉽게 해결할 수 있다. = 이분 탐색 = https://st-lab.tistory.com/267 이 블로그를 참고해서 공부했다. 나보다 훨씬 자세한 설명은 이 블로그에 있다. 간단..
