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

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

이번에는 BOJ의 1016번 문제 "제곱 ㄴㄴ수"를 풀어보도록 하자 문제는 간단하다. 입력으로 minimum인 min 과 maximum인 max가 주어진다. 그리고 min과 max를 포함한 사이에 제곱 ㄴㄴ수 가 얼마나 있는지 출력하는 문제이다. 일단, max >= min + 1,000,000(백만) 이기 때문에, 이 사이에 수들에 대해서만 반복문으로 구해주면 된다. 여기에서, 유의해야 될 점은 min이 1 보다 크거나 같고, 1,000,000,000,000(1조) 보다 작거나 같은 자연수 라는 점이고, 이 부분을 유의해서 min과 max를 long 자료형으로 받아왔다. 성공한 코드는 아래와 같다. import java.io.*; import java.util.*; public class sample {..

이번에는 BOJ의 1717번 문제 "집합의 표현"를 풀어보도록 하자 문제를 풀어서 설명해 보면, 입력으로 맨처음에 주어지는 원소들의 총 크기, n 이 주어지고, 연산의 개수 m이 주어진다. 연산중에서 "0 a b"의 형태로 주어지는 것은 합집합으로, a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합치는 연산이다. 그리고, "1 a b"의 형태로 주어지는 연산은 확인하는 연산으로, 두 원소 a b가 같은 집합에 포함되어 있는지를 확인해서 포함되어 있으면, "YES"를 아니면 "NO"를 출력하는 문제이다. 가장 기본적인 디스조인트셋(Disjoint-set)문제이다. 이런 문제는 기본적으로, 초기에 set을 만들어주는 makeset public static void makeSet(int n){ par..

이번에는 BOJ의 11051번 문제 "이항계수2"를 풀어보도록 하자 입력으로 N과 K가 주어지고 주어진 입력을 통해, 이항계수 (N K) 를 10,007로 나눈 나머지를 구하는 프로그램을 작성하는 문제이다. 문제는 간단하니, 부가설명없이 성공한 코드는 아래와 같다. import java.io.*; import java.math.BigInteger; 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 Buff..

이번에는 백준알고리즘의 1256번 문제 "사전"을 풀어보도록 하자 문제를 이해하기 약간 애매한 부분이 있어서, 예제를 보면서 설명하도록 하겠다. 일단, 입력으로는 "a"의 개수인 N, "z"의 개수인 M, 마지막으로 K가 주어지고, 출력으로 사전에서 K번째 문자열이 무엇인지 구하면 되는 프로그램이다. 여기에서, K의 상한이 1,000,000,000(십억)이므로 정수형(long)으로 받아야된다. 먼저 예제를 보면, 입력 : 2 2 2 출력 : azaz 이 주어졌다. 2개의 "a"와 2개의 "z"로 되어진 문자열 중 사전에서 2번째 문자열은 "aazz"다음인 "azaz"가 되므로, 출력으로 "azaz"를 내보내면 된다. 이번문제는, combination을 이용해서 문제를 풀었다. BigInteger를 이용해..

이번에는 백준알고리즘의 5355번 문제 화성수학을 풀어보도록 하자 문제에 나와있는 부분은 살짝 이해하기 어렵게 되어있으므로, 예제를 보면서 문제를 설명하도록 하겠다. 일단, 입력으로 테스트케이스의 개수 T가 주어지고 그 다음 줄부터 하나의 숫자와 연산자(@, %, #)가 띄어쓰기로 주어진다. @는 3을 곱하는 연산자 %는 5를 더하는 연산자 #은 7을 빼는 연산자이고, 출력으로 각 테스트 케이스에 대해서 결과를 소수점 둘째자리까지 구하면 된다. 예제로 주어진, 3 @ % 는 (3 * 3) + 5 이고, 이것은 14가 되는데, 소수점 둘째자리까지 구하라고 하였으므로, 14.00을 출력값으로 넣어주면 된다. 성공한 코드는 아래와 같다. import java.io.*; import java.util.*; pu..

이번에는 백준 알고리즘의 1107번 문제 "리모컨"을 풀어보도록 하자 문제가 살짝 복잡한데, 수빈친구가 가지고 있는 리모컨의 일부 숫자 버튼이 고장났다. 수빈이가 현재 보고 있는 채널은 100번이고, 입력으로 수빈이가 이동하려고 하는 채널 N, 고장난 버튼의 개수 M, 그리고 고장난 버튼이 있는 경우에 셋째줄에 고장난 버튼이 주어지고, 출력으로 채널 N 으로 이동하기 위해 버튼을 최소 몇번 눌러야 하는지를 출력하는 문제인데, 입력으로 주어지는 채널이 500,000이므로 반복문으로 여러번 판별해주다 보면 시간초과가 뜰 위험이 있다. 이것을 주의하면서 문제를 풀면 된다. 일단 부르트포스(완전탐색)으로 문제를 풀었다. 총 이동가능한 채널의 개수는 입력의 상한이 500,000 이었으므로, 1,000,000(백만..

이번에는 백준 알고리즘의 1806번 문제, "부분합"을 풀어보도록 하자 일단 이번 문제에서 입력은 수열의 길이 N 과 연속된 수들의 합의 판단기준이 될 S 가 주어지고, 두번째 줄에는 해당 수열이 주어진다. 출력으로는 부분합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 출력하면 된다. 문제 설명 자체는 간단하지만, 과정이 살짝 복잡해 보인다. 이번 문제에서 사용되는 알고리즘은 투포인터이다. 투포인터 알고리즘이란, 두개의 포인터를 두고 그 포인터들을 이동 시키면서 답을 구해나가는 과정이다. 밑에 그림을 보면서 이해해 보도록 하자. 일단, 예제에서 주어진 것과 같이 N = 10 S = 15 수열 : 5 1 3 5 10 7 4 9 2 8 이 있을때, 처음위치(0)인 부분에 두개의 포인터를 놔둔다.(sum..