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

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

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

이번에는 BOJ의 2166번 문제 "다각형의 면적"을 풀어보도록 하자 입력으로 첫째줄에 다각형의 꼭지점의 개수인 N 이 주어지고, 그다음 N개의 줄에 N개의 점의 x, y 좌표가 주어진다. 출력으로, 다각형의 면적을 구하면 되는 문제이다. 문제 자체는 간단하고, 수학만 할줄 알면 풀 수 있는 문제이다. 이번 문제에서 사용한 삼각형 넓이 공식은 S = 1/2|(x1y2+x2y3+x3y1) - (x1y3+x2y1+x3y1)| 을 이용해서, 기준점을 두고 넓이를 구하는 방식을 선택했다. 그리고 입력으로 주어지는 x, y의 좌표가 다각형을 이루는 순서대로 되어있기 때문에, 입력된 순서대로 배열에 저장시킨 다음에, 처음을 고정시키고 그 다음 점부터 차례대로 3점을 뽑아서 넓이를 구해가는 방식으로 문제를 풀었다. ..

이번에는 BOJ의 1915번 문제 "가장 큰 정사각형"을 풀어보도록 하자 다이나믹 프로그래밍으로 풀면 간단하게 풀리는 문제이다. 입력으로 먼저 n, m 주어지고, 그 다음 n개의 줄에 m개 만큼 "0"이나 "1"이 주어진다. 이것을 이용해서, 1로 이루어져 있는 가장 큰 정사각형의 넓이를 구하면 되는 문제이다. 예제를 보면 4 4 0100 0111 1110 0010 이 주어졌을 때, 가운데에 있는 굵은 글씨부분이 가장 큰 정사각형이고, 그 넓이는 4가 된다. 이것을 풀 때, 입력을 배열로 받으면서 계산까지 가능하도록 프로그램을 만들어서, 살짝 더럽긴하지만, 성공한 코드는 아래와같다. import java.io.*; import java.util.*; public class sample { public s..