알고리즘(27)
-
[알고리즘/자바] 백준 1463번 - 1로 만들기
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)을 구해야한다. 위의 개념을 코드화 하..
2021.01.07 -
[알고리즘/자바] 백준 2960번 - 에라토스테네스의 체
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로 나눠떨어진다. ) 즉 자기보다 작은 수에 의해 나눠떨어지면 소수가 아니다. 이 원리를 이용하면 소수를 빠르게 구할 수 있다. 그 중 대표적인 알고리즘이 에라토스테네스의 체. 에라토스테네스의 체는 특정 범위내에 있는 모든 소수를 빠르게 찾기 위한 알고리즘 중 하나이다. 에라토스테네스의 체를 이용해 ..
2021.01.03 -
[알고리즘/자바] 백준 1676번 - 팩토리얼 0의 개수
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..
2021.01.02 -
[알고리즘/파이썬] 백준 2609번 - 최대공약수와 최소공배수
2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 최대공약수를 구하는 여러방법이 있는데 가장 유명한것은 유클리드 호제법. 단번에 이해되는 예시도 있으니 아래의 백과사전을 참고하자. 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 � ko.wikipedia.org 최대공약수를 먼저 구하면 최소공배수는 쉽게 구할 수 있다. 이유는 최대공약수와 최소공배수는 아래와 같은 관계..
2020.09.06 -
[알고리즘/파이썬] 백준 2607번 - 비슷한 단어
2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이�� www.acmicpc.net 문제 이해하는데 한참 걸렸다. 책좀 더 읽어야겠다. 아래 코드처럼 모든경우의 수를 다 확인하는 방법으로 풀었다. 입력은 대문자만 된다고 했으니 대문자 32개를 입력받을수 있도록 했다. ( length가 32인 list에 0으로 초기화 ) 대문자는 아스키코드 65부터 시작하니까 입력받은 문자를 65로 나눈 나머지가 0이면 A, 나머지가 1이면 B 이런식으로 처리했다. 그후 구성이 같은지, 문자를 하나 뺐을때 같은지, 문자를 하나 더했을때 같은지, 기존 문자 ..
2020.09.01 -
[알고리즘/파이썬] 백준 11053번 - 가장 긴 증가하는 부분 수열
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net { 1, 2, 1, 4, 3, 2 }라는 순열이 있을때 구할수 있는 증가 부분 수열이 몇가지 존재한다. 예를들면 [1 2] , [1 4], [1 2 3] , [1 2 4] 같은것들이다. 좌측부터 수를 뽑되(순열) 반드시 증가해야하며(증가) 주어진 순열내에 있는 숫자(주어진 순열의 부분)로 이뤄져있다. 위의 예시같은 경우는 3이 가장긴 부분 수열이다. ( [1 2 3] 또는 [ 1 2 4..
2020.07.27