[Python] 알고리즘/Silver
-
[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..
-
[1535] 안녕 (Python)[Python] 알고리즘/Silver 2022. 3. 21. 15:28
[문제] https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 알고리즘 분류는 다이나믹 프로그래밍, 브루트포스 알고리즘, 배낭 문제 입니다. itertools의 combinations(조합)을 사용하여 풀었습니다. [코드] import sys from itertools import combinations N = int(sys.stdin.readline()) health = list(map(int, sys.stdin.readline().split()..