[Python] 알고리즘
-
[1759] 암호 만들기 (Python)[Python] 알고리즘/Gold 2022. 5. 31. 17:38
[문제] https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 알고리즘 분류는 수학, 브루트포스 알고리즘, 조합론, 백트래킹 입니다. Python의 combinations(조합)을 사용한 후, 모음과 자음의 개수를 이용하여 답을 도출해냈습니다. [코드] import sys from itertools import combinations L, C = map(int, sys.stdin.readline().split()) word = sys.stdin.readl..
-
[14888] 연산자 끼워넣기 (Python)[Python] 알고리즘/Silver 2022. 5. 24. 21:30
[문제] https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 알고리즘 분류는 브루트포스 알고리즘, 백트래킹 입니다. 저는 Python의 permutations(조합)을 사용하여 풀었습니다. 연산자 우선순위를 무시하고 앞에서 부터 계산해야 하고, 음수를 양수로 나눌 때의 조건도 지정해주어야 합니다. [코드] import sys from itertools import permutations N =..
-
[11053] 가장 긴 증가하는 부분 수열 (Python)[Python] 알고리즘/Silver 2022. 5. 6. 12:13
[문제] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 알고리즘 분류는 다이나믹 프로그래밍 입니다. A 10 20 10 30 20 50 num 1 2 1 3 2 4 부분수열의 수를 num이라 했을 때, 값을 비교한 뒤 num을 늘려줍니다. 이 중 가장 큰 값(max)를 출력하면 됩니다. [코드] import sys N = int(sys.stdin.readline()..
-
[1912] 연속합 (Python)[Python] 알고리즘/Silver 2022. 4. 30. 19:06
[문제] https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 알고리즘 분류는 다이나믹 프로그래밍 입니다. [a, b, c] 에서, b와 a + b를 비교하여 더 큰 값을 저장합니다. [코드] import sys n = int(sys.stdin.readline()) li = list(map(int, sys.stdin.readline().split())) for i in range(1, n): li[i] = max(li[i], li[i] + li[i - 1]) ..
-
[9184] 신나는 함수 실행 (Python)[Python] 알고리즘/Silver 2022. 4. 12. 14:30
[문제] https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 알고리즘 분류는 다이나믹 프로그래밍, 재귀 입니다. 이전에 계산한 값을 저장하여 시간을 줄입니다. [코드] import sys li = [[[0 for _ in range(51)] for _ in range(51)] for _ in range(51)] def w(a, b, c): if a 20: if li[20][20][20] == 0: li[20][20][20] = w(20, 20, 20)..
-
[10819] 차이를 최대로 (Python)[Python] 알고리즘/Silver 2022. 4. 12. 11:47
[문제] https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 알고리즘 분류는 브루트포스 알고리즘, 백트래킹 입니다. 저는 Python의 permutations (순열)을 사용하여 풀었습니다. [코드] import sys from itertools import permutations N = int(sys.stdin.readline()) A = list(map(int, sys.stdin.readline().split())) perm = list(permutation..
-
[1182] 부분수열의 합 (Python)[Python] 알고리즘/Silver 2022. 4. 4. 13:24
[문제] https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 알고리즘 분류는 브루트포스 알고리즘, 백트래킹 입니다. 저는 python의 combinations를 사용하여 모든 경우의 수를 구한 뒤, 더한 결과를 비교하였습니다. [코드] import sys from itertools import combinations N, S = map(int, sys.stdin.readline().split()) li = lis..
-
[6603] 로또 (Python)[Python] 알고리즘/Silver 2022. 4. 4. 13:19
[문제] https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 알고리즘 분류는 수학, 조합론, 백트래킹, 재귀 입니다. 저는 python의 combinations를 이용하여 풀었습니다. [코드] from shlex import join import sys from itertools import combinations comb = list() while True: S = list(map(int, sys.stdin.readline().spli..