알고리즘/TIL39 [코테스터디 day6] Dp ✏️ 추가 문제 : 설탕 배달 📌 풀이N = int(input())n = N//5m = N%5res = 0while (n>=0): if m%3 == 0: res = n+(m//3) break else: n -= 1 m += 5if(m>N): print(-1)else: print(res) 메모이제이션, dp 배열을 사용하진 않음N을 5,3으로 나누어 최소한의 횟수로 가져가는 방법을 찾기N//5 한 값에 대해서도, m//3 한 값에 대해서도 최적 부분 구조가 유지되기에부분 구조의 최적해를 합해서 전체 구조 최적해를 도출 2024. 11. 5. [코테스터디 day5] 그리디 ✏️ 그리디 알고리즘선택의 순간마다 눈앞의 최적의 상황을 쫓아 최종 해답에 도달하는 방법.항상 최적해를 보장하지 않고, 검증을 거쳐야 하지만 탐욕적으로 접근했을때 해결 보장이 있다면 효과적동전 거스름돈 문제, 다익스트라 알고리즘, 스케쥴링, Knapsack 문제등에 주로 이용된다. Greedy를 적용하는 조건탐욕적 선택 속성(Greedy Choice Property)앞의 선택이 이후의 선택에 영향을 주지 않는다.최적 부분 구조(Optimal Substructure)문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다.하지만, 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능하다. 대부분 속도가 빠르기에.. 2024. 11. 4. [코테스터디 day4] 완전탐색 ✏️ 오늘의 문제 : 소수 찾기 📌 주안점itertools.permutation을 이용한 순열 생성 (모든 경우의 수는 중복 가정했을때, 7! -> 충분히 작음)int로 변환해서 leading zero 제거. 001, 01, 1 등을 1로set 자료구조를 사용해서 중복을 제거에라토스테네스의 체 알고리즘을 사용해서 최대값의 루트값까지만 조사, 최대값 9999999에라토스테네스 체 시간복잡도 : O(n * log(log n)) N : 9999999 -> 충분 📌 풀이# 1. 7! # 2. int로 leading zero 제거# 3. set으로 중복 제거import itertoolsdef solution(numbers): numbers = list(numbers) ss = set() .. 2024. 11. 1. [코테스터디 day3] 정렬 ✏️ 정렬in pythonlist1.sort()시간 복잡도 O(nlogn)에 근접 -> 최적화 잘되어있다고 함 (quicksort -> O(nlogn)) sort 옵션sort(key=len) -> 정렬 기준을 지정하는 함수나 함수를 반환하는 식을 제공 (len 함수 등)sort(reverse = True) -> 내림차순 정렬 (기본값 : 오름차순)list1 = sorted(list2) Lambda식기본 형식lambda 인자: 반환값lambda x:x[1] -> x 인자에서 index 1의 원소를 반환lambda와 sort의 조합sort(key=lambda x:x[0]) ✏️ 오늘의 문제 : 가장 큰 수 📌 주안점정렬의 기준을 잡는 문제 -> python의 key=lambda, java의 Co.. 2024. 10. 31. 이전 1 2 3 4 ··· 10 다음
