분류 전체보기16 [Alogorithm - Python(파이썬)] 백준 1806 - 부분합 (투 포인터, 구간 합) https://www.acmicpc.net/problem/1806 이 문제의 제한 시간은 0.5초, N의 최대 수는 100,000이기 때문에 O(N)의 시간복잡도로 문제를 풀어야 한다. 때문에 이번 문제도 이전 포스팅에서 다룬 문제와 같이 투 포인터와 구간 합을 사용해서 문제를 풀었다. [Alogorithm - Python(파이썬)] 백준 2003 - 수들의 합 2 (투 포인터, 구간 합)https://www.acmicpc.net/problem/2003 이번 문제는 푸는 데 여러 시행착오가 있었다. (정답 코드는 맨 마지막 코드) 1. 백트래킹(시간 초과)import sysinput = sys.stdin.readlinedef dfs(idx): global cnt, tot, start if tot == .. 2024. 8. 18. [Alogorithm - Python(파이썬)] 백준 2003 - 수들의 합 2 (투 포인터, 구간 합) https://www.acmicpc.net/problem/2003 이번 문제는 푸는 데 여러 시행착오가 있었다. (정답 코드는 맨 마지막 코드) 1. 백트래킹(시간 초과)import sysinput = sys.stdin.readlinedef dfs(idx): global cnt, tot, start if tot == M: # 부분 합이 M을 만족하면 cnt += 1 # 정답 카운트 + 1 하고 return # 바로 return(모든 수는 자연수이므로 여기서 더 더한다고 해서 M이 또 나올 수가 없기 떄문) for i in range(idx, N): tot += A[i] # 현재 인덱스의 수 더하기 .. 2024. 8. 16. [Alogorithm - Python(파이썬)] 백준 1182 - 부분수열의 합 (itertools, 브루트포스) https://www.acmicpc.net/problem/1182 1. itertools(combinations)조합을 사용하는 문제라서 조합 라이브러리를 사용하여 풀어봤다.from itertools import combinationsimport sysinput = sys.stdin.readlineN, S = map(int, input().split())list = list(map(int, input().split()))cnt = list.count(S) # 수열 내에 존재하는 S들의 개수로 초기화for i in range(2, N + 1): # 2개부터 N개까지 반복 for li in combinations(list, i): # i개를 뽑는 조합 if sum(li) == S: # 구.. 2024. 8. 14. [Alogorithm - Python(파이썬)] 백준 6603 - 로또 (itertools, 백트래킹) https://www.acmicpc.net/problem/6603 1. itertools(combinations)처음에는 조합 문제라고 생각하여 itertools 라이브러리를 생각했다. 문제의 조건을 보고 시간복잡도를 계산해보니 제한 시간(1초) 내에 풀 수 있겠다고 판단하여 라이브러리를 사용했다.from itertools import combinationsimport sysinput = sys.stdin.readlinewhile True: li = list(map(int, input().split())) if li[0] == 0: # k가 0이면 프로그램 종료 break k = li[0] s = li[1:] for li in list(com.. 2024. 8. 9. 이전 1 2 3 다음