[PS] 백준1300 : K번째 수(Java)
CS/알고리즘2023. 12. 28. 18:25[PS] 백준1300 : K번째 수(Java)

문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 풀이 파라메트릭 서치를 활용한 풀이 그리디한 접근법 A[i][j]값을 1차원 배열에 기록 후 오름차순 정렬을 통해 원하는 값 B[K]를 구하는 방식 해당 방식으로 풀이하게 될 경우 N^2만큼의 메모리가 필요할 뿐더러 시간 또한 O(N^2)만큼 걸리기 때문에 AC를 받을 수 없음 LowerBound 접근 위의 방식에서 이분탐색을 추가해서 탐색 시간을 줄여야하는데 ..

CS/알고리즘2023. 12. 23. 16:29[PS] 백준7579 : 앱(Java)

문제 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 DP Knapsack 문제 접근법 전형적인 Knapsack문제라 처음 배열의 행을 최대 BYTE 수인 10,000,000으로 두고 풀이하려함. 하지만 시간복잡도가 N이 최대 100이라 O(NM)이면 1억을 넘기 때문에 시간초과가 나기에 포기. 두번째로는 1차원 dp배열의 값을 최대 비용으로 두고 접근. 해당 문제에서 앱은 최대 100개, 비용은 각 앱 당 최대 100까지 나오기 때문에 최대 1..

image