파이썬25 백준 1253: 좋다 (파이썬 풀이) https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 시간복잡도 -> 제한시간이 2초이고 N의 개수가 2000입니다. (제한시간 2초면 연산 4천만번 가정) 만약 좋은수 하나를 찾는 알고리즘의 시간복잡도가 N^2 이라면 반복문을 돌리는데 총 N^3의 시간복잡도가 되므로 N^2 알고리즘은 사용할 수 없습니다. 따라서 NlogN의 시간복잡도 알고리즘을 사용해야합니다. 정렬후에 (파이썬 퀵소트 : NlogN) 투 포인터를 이용하면 가능합니다. 수를 입력받아 리스트에 저장후 투 포인터.. 2022. 9. 12. 백준 11286: 절댓값 힙 (파이썬 풀이) https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 이 문제는 절댓값을 비교해서 가장 작은 값을 꺼내야 하므로, 우선순위 큐에 절댓값을 저장해야 합니다. 하지만 절댓값이 같은 수가 여러개 있을 경우 그중에 작은값(양수와 음수가 있다면 음수)을 골라야하므로 원래 원본 값도 같이 저장해야 합니다. 따라서 우선순위큐에 튜플을 이용하여 (절댓값, 원본값)을 우선순위큐에 넣어줍니다. 우선순위큐는 선형 자료구조일 경우 기본적으로 맨 앞의.. 2022. 8. 17. 22/08/08 백준하면서 간단한 기록 import sys input = sys.stdin.readline 파이썬의 입출력을 빠른 속도로 할 수 있다. from collections import defaultdict d = defaultdict(int) default_dict를 이용하여 딕셔너리를 만들면 위와 같이 int로 설정하면 지정하지 않은 키는 그 값이 0으로 지정된다. 인덱스 개수 셀 때 편리함 enumerate() 함수를 이용하면 인덱스와 원소를 동시에 접근하면서 루프를 돌릴 수 있다. 인덱스 개수 셀 때 편리함 파이썬 gcd, lcm def gcd(a, b): # 최대공약수 while b > 0: a, b = b, a % b return a def lcm(a, b): # 최소공배수 return a * b / gcd(a, b) 파이.. 2022. 8. 8. 동전 바꿔주기(DFS) 인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다. https://inf.run/P97f 파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의 파이썬을 이용한 코딩테스트 문제풀이를 합니다., - 강의 소개 | 인프런... www.inflearn.com 내 풀이 (정답 아님) #내 풀이 def DFS(L, sum): global cnt if sum > T: return if sum == T: cnt += 1 return if L == k: return else: for i in cn: for j in range(i+1): DFS(L+1, sum+cv[L]) DFS(L+1, sum) if __name__ == "__main__": cv = [] cn = [] T = int(inpu.. 2022. 4. 5. 휴가(DFS) 인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다. https://inf.run/7EX2 파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의 파이썬을 이용한 코딩테스트 문제풀이를 합니다., - 강의 소개 | 인프런... www.inflearn.com 강의 풀이 #강의 풀이 def DFS(L, sum): global res if L == n+1: if sum > res: res = sum else: if L+T[L] 2022. 4. 5. 최대점수 구하기(DFS) 인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다. https://inf.run/aaLB 파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의 파이썬을 이용한 코딩테스트 문제풀이를 합니다., - 강의 소개 | 인프런... www.inflearn.com 내 풀이 (정답 아님) #내 풀이 def DFS(L, sum, time): global res if total-sum < res-sum: return if L == n: if time res: res = sum else: for i in range(n): DFS(L+1, sum+s[i], time+t[i]) DFS(L+1, sum, time) if __name__ == "__main__": s = [] t = [] n, m = m.. 2022. 4. 4. 이전 1 2 3 4 5 다음
