문제 https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 풀이 두 분수의 합을 기약 분수로 나타낸 식은 다음과 같습니다. $$ {a \over b} \times {c \over d} = {(a \times d + c \times b) \div GCD \over (b \times d) \div GCD} $$ $$ GCD = (a \times d + c \times b)와 (b \times d)의 최대공약수$$ 코드 import sys def get_GCD(a, b): if b == 0: return a..

문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 로봇청소기가 0으로 연결된 영역을 전부 청소할 것이라고 생각해서 BFS로 풀려고 했지만, 2-c와 2-d 조건에 의해 0으로 연결된 영역이라고 하더라도 로봇 청소기가 청소하지 않은 영역이 생기게 되어 결국 구현 문제라는 것을 깨달았습니다. 문제에서 주어진 2번 예제에서 로봇청소기가 청소하고 나면 matrix[4][8]과 matrix[6][6] 두 영역이 청소를 안하고 남게 됩니다. c..

문제 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 풀이 DP를 이용하여 풉니다. 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)를 찾는 문제입니다. DP 테이블의 값은 각 열의 숫자를 포함하는 LIS의 길이를 의미합니다. 아래 표는 문제에서 주어진 예제의 DP 테이블입니다. numbers 1 6 2 5 7 3 5 6 dp 1 2 2 3 4 4 4 5 n의 길이를 갖는 DP 테이블을 선언하고 dp[0] = 1로 ..

문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 \( _{C}\mathrm{C}_{L} \) 의 모든 조합을 오름차순으로 정렬하여 출력합니다. 단, 아래의 조건을 만족해야 합니다. 최소 한 개의 모음을 포함해야 합니다. 최소 두 개의 자음을 포함해야 합니다. 코드 import sys from itertools import combinations l, c = map(int, sys.stdin.readline().rstrip().split()..

문제 https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 풀이 next_permutation 알고리즘을 사용합니다. 아래 페이지를 참고하세요. https://steadycode.tistory.com/27 [알고리즘]Next Permutation 알고리즘 Next Permutation Algorithm은 순열 알고리즘 중에 하나로 무작위 순열의 다음 순열을 구하는 알고리즘입니다. 시간 복잡도는 O(N)이고 Greedy 알고리즘을 기반으로 합니다. 아래의 수열을 예로 다음에 올 steadycode.tistory..

문제 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 풀이 단순히 \( _{n}\mathrm{C}_{m} \) 으로 답을 구하기엔 n과 m이 20억일 때 제한시간을 초과할 수 있습니다.(1000만 ~ 10억 개의 연산이 약 1초 소요) 따라서 수학적으로 접근해서 풉니다. 조건(1): \( _{n}\mathrm{C}_{m} = {_{n}\mathrm{P}_{m} \over m!} = { n! \over m! \times (n - m)!} \) 조건(2): 어떠한 수x가 있을 때, x를 인수분해했을 때 인수..