koucop의 개발탐방기 koucop의 개발탐방기

이번에는 BOJ의 16938번 문제 "캠프 준비"를 풀어보도록 하자 오랜만에 이런 문제를 풀려고 하니, 뇌에 쥐가 나서 살짝 지끈했다. 처음에 문제를 풀때에는 아래에 첨부한 것과 같이 list를 이용해서, 간편하게 max값과 min값 크기를 구할 수 있도록 했는데, 시간초과가 떠버렸다. import java.io.*; import java.util.*; public class sample { static int N, X; static long L, R; static long[] A; static int ans = 0; static ArrayList list = new ArrayList(); public static void main(String[] args) throws Exception { Buffer..

이번에는 BOJ의 3053번 문제 "택시 기하학"을 풀어보도록 하자 문제는 간단하나 용어들이 생소할 수 있다. 유클리드 기하학에서 반지름이 R인 원의 넒이라고 함은, A = PI() * R^2 이다. 그리고 이 문제에서 나오는 택시 기하학에서 반지름이 R인 원의 넓이라고 함은, D(T1,T2) = |x1-x2| + |y1-y2| 의 계산을 통해 얻어지는 도형의 넓이라고 생각하면 된다. 이해하기 쉽게 도형을 보면서 설명해보자면, 위 그림과 같이 반지름이 1인 원과 좌표(1,0), (0,1), (-1,0), (0,-1)를 꼭지점으로 하는 사각형이 있다고 하자. 여기에서 유클리드 기하학에서 원의 넓이라고 함은 파란색원의 넓이이다. 그리고 이문제에서 나오는 택시기하학에서의 원의 넓이라고 함은 빨간 사각형의 넓이..

이번에는 BOJ의 1927번 문제 "최소 힙"을 풀어보도록 하자 PriorityQueue를 이용해서 풀어주면 되는 아주 간단한 문제이다. 성공한 코드는 아래와 같다. import java.io.*; import java.util.*; public class sample { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int N = Integer.parseInt(br.readLine(..

이번에는 BOJ의 7579번 문제 "앱"을 풀어보도록 하자 일단, 문제가 매우 길다. 쉽게 설명해 주면 앱에 백그라운드에 사용되어지고 있는 메모리가 있고, 그 메모리를 처리하는데 비용이 드는데, 입력으로 앱의 개수 N이 나오고, 확보하기위한 메모리바이트 수인 M이 주어진다. 그 다음에, 앱의 개수 N개 만큼 사용중인 메모리의 바이트m이 차례대로 주어진다. 그리고, 앱의 개수 N개 만큼 메모리를 확보하기위해 앱을 비활성화 했을 때 드는 비용 c가 차례대로 주어진다. 출력으로는 필요한 메모리 바이트 수인 M을 확보하기 위한 최소의 비용을 구하면 된는 문제이다. 문제가 길긴하나, 푸는 방법은 간단한다. import java.io.*; import java.util.*; public class sample { ..

이번에는 BOJ의 11653번 문제 "소인수분해" 문제를 풀어보도록 하자 매우 간단한 문제이다. 첫째 줄에 정수 N이 주어기고, 그 수를 소인수 분해해주어서, 그 결과를 한줄에 하나 씩 출력해 주면 되는 문제이다. 단, 여기에서 주의해야될 점은 N의 상한이 10,000,000(천만)으로 상당히 크다는 것을 알 수 있다. 이것을 유의해 주어서 문제를 풀어주면 된다. 성공한 코드는 아래와 같다 import java.io.*; import java.util.*; public class sample { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader..

이번에는 BOJ의 1018번 문제 "체스판 다시 칠하기"를 풀어보도록 하자 먼저 문제설명을 해보자면, 지민친구가 8 * 8 크기의 체스판을 만들려고 하는데, 주어진 N * M 크기의 보드가 검정 / 흰색 패턴이 번갈아가며 칠해져 있지 않아 따로 칠해줘야 된다. 이 때, 8 * 8크기로 보드를 자른뒤에 다시 칠해야하는 정사각형의 개수의 최솟값을 구하는 프로그램을 구해야 되는 문제이다. 입력으로는 처음에 N과 M이 주어지고, 둘째 줄부터 N개의 줄만큼 체스판의 색상태가 주어진다. (B는 검정색이고, W는 희색이다.) 그리고, 출력으로는 지민이가 다시 칠해야하는 정사각형 개수의 최솟값을 출력하면 되는 문제이다. 이 문제는, 목표지점을 사진을 찍듯이 찍어서, 기존의 체스판과 얼마나 다른지 비교하면 되는 문제이다..

이번에는 BOJ의 2164번 문제 "카드2"를 풀어보도록 하자 Queue를 이용한 아주 간단한 문제이다. 예제를 보면, N = 4일 경우에, 제일 위에서부터 1234 순서대로 카드가 주어지고, 차례대로 가장 위에 있는 카드를 버리고 남은 카드중에서 가장 위에있는 카드르 제일 밑으로 옮기는 것을 반복해주면 된다. 이와 같이 N = 4일 때, 답은 4가 된다. 이 프로세스대로 Queue를 이용해 구현해주기만 하면 되는 간단한 문제이다. 성공한코드는 아래와 같다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new..

이번에는 BOJ의 2261번 문제 "가장 가까운 두 점" 문제를 풀어보도록 하자 문제는 간단한데, 풀이가 까다로운 문제이다. 먼저, 입력으로 점의 개수 n이 주어지고, 그다음 줄부터 n줄 만큼 각 점의 x, y 의 좌표가 공백을 사이에 두고 주어진다. 그리고 가장 가까운 두 점의 거리의 제곱값을 출력하면 되는 문제이다. 이 문제를 풀 때, 아래와 같이 하나하나씩 비교해주게 되면, 점이 최대로 많을 때, 100,000(개)가 존재하고, 시간 복잡도가 O(N^2)가 되기 때문에 거의 10,000,000,000(백억)번 정도 루프를 돌려주게되어서, 시간초과가 떠버린다. import java.io.*; import java.util.*; public class Main { public static void ma..