알고리즘 스터디 (35) 썸네일형 리스트형 [Python] BOJ 2004 조합 0의 개수 이 문제를 풀기 전에 팩토리얼과 승수의 관계를 알아야 한다. 예를 들어 5! 을 소인수 분해하면 2의 승수는 몇일까? 5! = 120이고 $ 2^3 \times 3 \times 5 $ 이기 때문에 3이 정답이다. 이를 컴퓨터가 계산하기 위해서 어떻게 해야 할까. 5! = $ 1 \times 2 \times 3 \times 4 \times 5 $ 반복문을 1부터 5까지 돌며 2로 나누어지는 수가 있으면 그 수가 1이 될 때까지 2로 나누어주고 나누어 줄 때마다 카운트를 올린다. 하지만, 문제에서는 M과 N의 범위가 20억까지 주어지기 때문에 이 방법은 시간 초과를 유발한다. 그렇다면 이 승수를 빠르게 계산하기 위한 방법이 필요한데 이는 다음과 같다. 5! 에서 2의 승수를 보기 위해서 5/2 + 5/4 +.. [JAVA] BOJ 9375 패션왕 김해빈 이 문제의 경우 옷을 한 개만 입어도 되는 경우를 생각하고 전체 경우의 수에서 아예 하나도 안 입었을 경우를 빼주면 된다. 예제 입력 1의 첫 번째 테스트 케이스의 경우 headgear = [hat, turban] , eyewear = [sunglasses]가 있는데 옷 종류 중에 하나만 입어도 된다. 즉, headgear 중 한 개를 입었으면 eyewear를 입지 않아도 된다. 이를 반영하면 각 옷 종류에 아무것도 입지 않은 None의 경우를 추가해주어야 한다. headgear = [None, hat, turban] , eyewear = [None, sunglasses] 가 된다. 이제 경우의 수를 계산하면 3 * 2 = 6 이 될 것이고 이 때, headgear와 eyewear 둘 다 입지 않은 경우.. [Python] BOJ 1010 다리놓기 이 문제는 복잡하게 생각하면 절대로 못 푸는 문제다. 간단하게 강 동쪽 사이트에서 강 서쪽 사이트 개수를 뽑는 조합을 생각하면 된다. 조합인 이유는 문제에서도 나와있다시피 다리를 교차해서 놓을 수 없다. 예를 들어 N=2, M=5라고 할 때, M으로 연결할 수 있는 사이트 N개를 뽑는 조합과 같은데 다섯 개 중에 두개를 뽑는 조합의 수는 그림[1]의 경우와 그림 [2]의 경우가 같은 경우이기 때문에 자연스럽게 다리가 교차되는 것의 경우의 수는 빠지게 된다. 자바로 이 문제를 풀면 오버플로우 문제로 인해 복잡하게 동적계획법, 조합 이론 등을 사용해야 하지만 파이썬은 앞선 포스팅에서도 다뤘다시피 오버플로우 문제가 발생하지 않기 때문에 파이썬으로 구현하면 다음과 같다. def fact2(n,m): sum = .. [Python] BOJ 11051 이항 계수2 이 문제를 처음엔 자바로 풀려고 했지만 12! 이 넘어가면 int 형을 초과하고 20! 을 넘어가면 long 형을 초과하여 엉뚱한 숫자가 튀어나온다. 이를 해결하기 위해선 모듈러 증명과 페르마의 소정리에 대한 수학적 지식이 있어야 알고리즘으로 접근할 수 있다. 정석으로 풀기 위해선 이분 블로그를 참고하면 좋을 것 같다. https://st-lab.tistory.com/162 [백준] 11051번 : 이항 계수 2 - JAVA [자바] www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 이전의 이항 계수 1 문제와 같은 문제다... [JAVA + Python] BOJ 2981 검문 왜 정답 비율이 저렇게 낮은지 알법한 문제였다. 처음엔 유클리드 호제법을 알지 못한 체 무작정 최대 공약수 구하다 보니 시간 초과가 정말 괴롭게 했다.. 수학적으로 접근하는 방법도 있지만 필자는 숫자들의 패턴을 보고 알고리즘에 접근했다. 예를 들어 N=2, 주어진 입력값은 [2, 12] 라고 할 때 M은 2, 5, 10이다 이를 보고 알아낸 것은 같은 M을 가지려면 두 수의 차의 약수를 구하면 되는구나라고 생각했다. 12-2 = 10이고 10의 공약수는 1을 뺀 2, 5, 10이 되기 때문이다. 만약 N=3 이고 2, 12, 18 가 주어진다면 M은 2 뿐이다. 2와 12의 차이는 10이고 18과 12의 차이는 6이기 때문에 10과 6의 최대 공약수는 2이고 최대 공약수의 약수 중 1을 제외하면 2만 남.. [JAVA + Python] BOJ 1934 최소공배수 간단하게 최소공배수를 구하는 문제이다. 이 문제는 자바랑 파이썬으로 동시에 풀어봤는데 그 실행시간의 차이가 커서 기록해두고자 한다. 우선 같은 알고리즘을 사용했다. 두 수 A와 B가 주어졌을 때 작은 값을 Min, 큰 값을 Max로 저장하고 반복문을 1부터 Min까지 하나씩 증가하면서(i라 하겠다) (Max*i)% Min==0 인 i값을 찾으면 break로 탈출하는 것이다. 파이썬으로 먼저 보면 다음과 같다. T = int(input()) for i in range (T): A, B = map(int, input().split()) Min = min(A,B) Max = max(A,B) for i in range(1,Min+1): if (Max*i)%Min==0: print(Max*i) break 코드의 .. [JAVA] BOJ 13305 주유소 문제가 꽤나 길지만 단순하다. 목적지까지 가기 위해 최소비용으로 기름을 넣는 문제인데, 지금 앞에 있는 주유소가 다음 주유소보다 싸면 더 많이 넣고 더 비싸면 다음 주유소까지 갈 수 있을 정도만 넣고 다음 주유소에서 넣는 것과 같다. 예제 입력 1 예로 들면 기름 리터 당 값이 [5, 2, 4, 1]이고 거리가 [2, 3, 1] 일 때 처음엔 무조건 기름을 넣어야 하므로 5를 최솟값으로 저장하고 5의 가격으로 주유한다. 5 * 2 = 10 다음, 최소값인 5와 2를 비교하여 2가 더 작으므로 2를 최솟값으로 저장하고 2의 가격으로 주유한다. 2 * 3 = 6 다음, 최소값인 2와 4를 비교하여 2가 더 작으므로 2를 최솟값으로 저장하고 2의 가격으로 주유한다. 2 * 1 = 2 합은 18이 된다. 예제 .. [JAVA] BOJ 1541 잃어버린 괄호 숫자와 +, - 연산자가 주어졌을 때 괄호를 넣어서 최솟값을 만드는 문제이다. 그리디 알고리즘은 인간의 두뇌와 정말 비슷한 알고리즘을 가진 것 같다. 이 문제를 봤을 때 사람은 당연히 - 뒤에 오는 숫자는 커야 하고 그렇기 때문에 - 뒤에 오는 숫자의 값을 크게 하기 위해선 +이면 괄호를 쳐주고 -이면 괄호를 치지 않고 진행할 것이다. 따라서 필자는 주어진 입력값을 -로 분리한 후 +로 분리하는 과정을 거쳤다. 무슨 말인가 하면, 55-50+40의 문자열이 주어졌을 때 -로 split("-")을 하게 되면 55와 50+40 이 남는다. 다른 예로 125-50-30+20 이 주어지면 125, 50, 30 + 20 이 남는다. 이때 나누어진 수대로 반복문을 돌며 해당 요소를 다시 +로 split("+") 한.. 이전 1 2 3 4 5 다음
