반응형 순열3 [실버2]백준 1182번(부분수열의 합) - 코테공부 26일차(2025.02.17) 문제유형조합 알고리즘풀이 방법 도출 과정1. 부분수열은 주어진 원소 중 일부를 선택하는 조합과 동일한 개념 이기에 조합을 사용해보도록 하겠다. 2. 조합을 사용하여 모든 수를 만들고 그 다음에 값들을 더한다음 첫째 줄에 합이 S가 되는 수를 찾는다.시간 복잡도최악의 경우 N이 20이기 떄문에 20 X 2^20= 2천만 정도 된다. O(N 2^N)코드 및 간단설명조합을 사용하여 풀었더니 시간초과가 나지 않았다. from itertools import combinationsN, S = map(int, input().split())lst = list(map(int, input().split()))ans = 0for i in range(1, N + 1): for num in combinations(lst, i.. 2025. 2. 17. [class2]백준 10974번(모든 순열) - 코테공부 24일차(2025.02.15) 문제유형순열 알고리즘풀이 방법 도출 과정1. 순열 알고리즘을 구현하는 것이 목표시간 복잡도최악의 순간을 생각하면 8!이기 때문에 이정도면 1억 번은 넘기지 않는 수이다. 코드 및 간단설명순열 알고리즘을 구현해보았다.N = int(input())lst = []for i in range(1, N + 1): lst.append(i)choose = []check = [False] * Ndef permutation(level): if level == N: print(*choose) return for i in range(0, N): if check[i] == True: continue choose.appen.. 2025. 2. 15. [class2]백준 6603번(로또) - 코테공부 24일차(2025.02.15) 문제유형조합풀이 방법 도출 과정1. 조합 알고리즘을 구현하는 것이 목표2. 이 방법대로 구현해보도록 하겠다.시간 복잡도시간 복잡도는 최악의 경우 k가 13이므로 13C6의 결과는 O(1)이다.코드 및 간단설명재귀함수를 사용하여 문제를 풀었다. 이건 간단히 조합을 구현하면 되는 문제였다. first_case = True # 첫 번째 테스트 케이스 여부 체크while True: lst = list(map(int, input().split())) N = lst.pop(0) # 첫 번째 값을 N으로 설정 if N == 0: # 종료 조건 break if not first_case: print() # 테스트 케이스 구분을 위해 빈 줄 출력 firs.. 2025. 2. 15. 이전 1 다음 반응형
