본문 바로가기
728x90

알고리즘339

[python] 백준 1182 부분수열의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 해결 ●리스트 안의 숫자가 매우 다양하고 주어지는 수열이 특징은 알 수 없으므로 모든 경우의 수를 다 계산해 봐야 할 것이다. ●부분수열의 합을 알아야 하기 때문에 부분수열의 순서는 상관이 없다. 따라서 i개(i>0)를 순서없이 뽑았을 때 합이 s가 되면 답을 +1을 해주면 된다. CODE import sys input = sys.stdin.readline.. 2023. 1. 19.
[python] 백준 11723 집합 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제 해결 집합의 연산에 대해서 확인 할 수 있는 기본적 문제라 생략. CODE import sys input = sys.stdin.readline M = int(input()) S = set() for _ in range(M): command = input().split() if command[0] == 'add': S.add(int(command[1])) elif command[0] == 'remove': try: S.remov.. 2023. 1. 18.
[python] 백준 2529 부등호 https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 문제 해결 부등호를 k개 뽑기 때문에 숫자는 서로 다른 k+1개의 숫자를 뽑게 된다. (0~9) 따라서 [0,1,2,3,4,5,6,7,8,9] 에서 k+1개를 뽑는 순열을 쓴 다음 주어진 식을 만족하면 정답 리스트에 추가하는 식으로 문제를 해결했다. 마지막에 max, min 두번 찾는 것보다 sort()한번 한 다음 최댓값은 맨 뒤 원소를 꺼내고, 최솟값은 맨 앞 원소를 꺼내는 식으로 문제를 해결하였다. CO.. 2023. 1. 17.
[python] 백준 15661 링크와 스타트 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 문제 해결 팀을 정하는 것부터 하나 하나 다 해봐야 하기 때문에 상당히 시간복잡도가 클 것 같다.(팀원 수도 양수라는 것 외에 정해지지 않음) 결국 팀원 하나하나 정하는 것을 재귀를 통해서 정리하고 계산을 하여 최솟값을 구한다. 파이썬으로는 시간초과가 나와서 pyp3로 풀었다. CODE import sys input = sys.stdin.readline.. 2023. 1. 16.
728x90