반응형 조합3 [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. [class3]백준 1759번(암호 만들기) - 코테공부 24일차(2025.02.15) 문제유형조합 알고리즘풀이 방법 도출 과정1. 조합을 물어보는 문제로 조합 알고리즘을 사용하면된다.2. 하지만 모음 조합 1개, 자음 조합 2개를 사용해서 새로운 것을 만드는 것이기에 모음, 자음을 분리하는 것이 필요하다.3. 또한 모음 자음을 분리했으면 이를 서로 조합해야한다.4. 이를 토대로 코드를 작성해보도록 하겠다.시간 복잡도가장 최악을 구하자면 조합의 수는 O(15 choose 14)이고, 각 조합에 대해 O(14)만큼 처리하는 것이므로 O(15 choose 14 * 14)이다. 이것은 시간 복잡도가 시간에 비해 충분하다는 것을 보여준다.코드 및 간단설명combinations 함수를 사용하여 문제를 풀었다. from itertools import combinations# 모음 리스트vowels .. 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 다음 반응형
