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

이번에는 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의 1708번 문제 "볼록 껍질"을 풀어보도록 하자 이 문제는 Convex Hull Algorithm(볼록 껍질 알고리즘)의 기초 문제이다. 일단, 입력으로 점의 개수 N이 주어지고, 둘째 줄부터 N줄 만큼 각 점의 x, y좌표가 공백을 사이에 두고 주어진다. (단, 각 점의 좌표는 다르다.) 출력으로는 볼록껍질을 이루는 점의 개수를 출력하면되는 문제이다.(단, 볼록껍질의 변에 점이 여러개 있는 경우에는 가장 양 끝 점만 개수에 포함한다.) 성공한 코드는 아래와 같다. 오버플로우 때문에, 점의 x, y좌표는 모두 long으로 받아줬다. 그렇게 하지않으면, 제출시 런타임 오류가 뜨게 된다. import java.io.*; import java.util.*; public class sample..

이번에는 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..

이번에는 BOJ의 15904번 문제 "UCPC는 무엇의 약자일까?" 에 대해서 풀어보도록 하자. (참고로, UCPC는 전국 대학생 프로그래밍 대회)이다. 문제 자체는 매우 간단하다. 입력으로, 문자열이 주어지고, 이 문자열에 UCPC가 차례대로 들어있어서 UCPC를 축약해서 만들 수 있는지 판별해 내는 문제이다. 만약, UCPC를 축약해서 만들 수 있으면, "I love UCPC"를 그렇지 않다면, "I hate UCPC"를 출력해주면 된다. 일단, 이 문제를 푸는데, 아래와 같이 노가다를 해서 한 조건문으로 판별할 수 있게 만들었다. if ((line.charAt(i) == 'U' && ans.equals("")) || (line.charAt(i) == 'C' && ans.equals("U")) || ..