밤이 블로그

카카오 코드 페스티벌 예선 - 캠핑 문제 해설 (Java) 이 문제는 n이 5000이므로 O(N^2)으로 풀어야 합니다.N^3으로 풀 수 있습니다만,, 최적화 과정이 들어가야 통과됩니다. 문제 출제 목적에 맞게 O(N^2)으로 푸셔야 맞습니다. (문제는 프로그래머스에서 다시 풀 수 있습니다.) O(N^2)의 해법은 다음과 같습니다. 1. 세그먼트 트리 개념과 비슷하게 주어진 범위의 직사각형 내부에 쐐기가 몇개 있는지를 먼저 구해놓습니다. -> O(N^2) S[i][j] : (0, 0) ~ (i, j) 범위의 직사각형 내부에 존재하는 쐐기의 개수 2) 그리고 모든 쐐기의 쌍에 대하여 -> O(N^2) 미리 구해놓은 S 배열의 값을 검사하여값이 0인 경우 (내부에 쐐기가 없음) 텐트를 설치할 수 있음을 쉽게..

BOJ#11723 집합 * 문제https://www.acmicpc.net/problem/11723 * 풀이매우 쉬운 문제이지만 시간 제한과 메모리 제한을 모두 생각해야 합니다. 저는 비트마스크를 사용하여 풀어보았습니다.아니면 배열을 사용해서도 쉽게 풀 수 있습니다. * 나의 코드 import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWri..

BOJ#2631 줄세우기 * 문제https://www.acmicpc.net/problem/2631 * 풀이일단 [4, 1, 2, 3, 5]인 경우의 문제를 손으로 풀어봅시다.거의 대부분 4를 3뒤로 옮겨서 한번만에 문제를 푸셨을 것입니다. 위 과정을 조금 더 상세하게 써보면 1. 수열에서 증가하는 가장 긴 부분 수열을 구하고 (이것들은 움직이지 않음)[4, 1, 2, 3, 5] 나머지 숫자를 적절한 자리로 이동시키면 옮겨지는 아이의 수를 최소로 하면서 줄을 세울 수 있습니다.[4, 1, 2, 3, 5] -> [1, 2, 3, 4, 5] 여기서 우리는 횟수만 구하면 되므로전체 길이 - LIS(Longest Increasing Subsequence) 길이 = 아이의 최소 이동 횟수 = 원하는 답 저는 LIS..