11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net {8, 2 , 3 , 4} 라는 수열이 있다고 하자. 여기서 가장 긴 증가하는 부분수열을 구하면 {2,3,4}이다. 처음 접근법으로는 단순하게 전수조사했다. {8,2,3,4}라는 수열이 있을때 먼저 8을 선택한 경우와 그렇지 않을 경우를 나눈다. 8을 선택하고 다음으로 가면 2가 있는데 2는 8보다 작으므로 선택할수 없다. 따라서 바로 3으로 넘어가도록 했다. 이런식으로 가장 마지막에 ..

1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net Dynamic Programming을 통해 풀어야하는 문제. 재귀를 통해 정답은 맞출수 있으나, 메모이제이션을 하지 않으면 시간초과가 발생한다. ( 중복된 연산을 제거해야한다 ) 입력으로 10이 주어졌을때 수행방식을 작성해보면 다음과 같다. 여기서 f(n)은 n을 1로만드는 최소 연산횟수. 10이 들어왔을떄 3으로 나눌수 있는지 확인했는데 불가능하다. 그렇기 때문에 나누기2와 빼기1 연산만 수행했다. f(10) = f(5)와 f(9)의 결과중 작은값 + 1 f(10) = min( f(5) , f(1) ) + 1 이므로 f(5) 와 f(1)을 구해야한다. 위의 개념을 코드화 하..

2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 주어진 N이 소수라면 2보다 크거나 같고 N보다 작은 수로 나눠 떨어지면 안된다. ( 주어진 N이 N>2를 만족하는 자연수 ) 예를들어 10을 소수인지 판단 하려면 2보다 크거나 같고 9보다 작은 수로 나눠보면된다 ( 10은 소수가 아니기 때문에 2와 5로 나눠떨어진다. ) 즉 자기보다 작은 수에 의해 나눠떨어지면 소수가 아니다. 이 원리를 이용하면 소수를 빠르게 구할 수 있다. 그 중 대표적인 알고리즘이 에라토스테네스의 체. 에라토스테네스의 체는 특정 범위내에 있는 모든 소수를 빠르게 찾기 위한 알고리즘 중 하나이다. 에라토스테네스의 체를 이용해 ..

1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 팩토리얼같은 경우는 결과로 워낙 큰수가 나오기 때문에 다음과 같은 형태로 문제가 많이 나온다. 팩토리얼 결과중 0의 갯수를 구하는 문제다. 0은 2x5일때 발생한다. 그렇기 때문에 팩토리얼을 소인수분해 해서 2x5의 갯수를 구하면 된다. 단, 2는 모든 짝수에 다 들어가지만 5는 모든 홀수에 다 들어가진 않는다. 따라서 2x5의 갯수는 5의 갯수와 같다. 구현하면서 25, 125와 같이 5가 2번, 3번 들어가는 숫자들을 잘 처리해줘야한다. import java.io.BufferedReader; import java.io.BufferedWriter..

1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 최대공약수를 구하는 문제인데 입력값이 조금 특이하다. 2라고 입력되었으면 11을 의미하고 3이라고 입력되었으면 111을 의미한다. 즉 2 3 이 입력되면 11과 111의 최대공약수를 구해야하는 문제다. 먼저 최대공약수(영어약자는 gcd)를 구하는 공식을 보자. 아래에 gcd(8,24)를 구하는 과정을 써봤다. 앞서 말했듯이 입력을 2와 3으로 했다면 11과 111의 최대공약수를 구해야한다. 하지만 문제에서 주어진 입력가능한 자연수의 크기는 ..

17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 17298번 오큰수를 약간 응용한 버전. 오큰수 문제를 풀었다면 쉽게 풀수 있다. 횟수 개념만 추가된것 외에는 차이가 없다. 변수명과 해당 변수에 담긴 값. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arra..