728x90 ⓒⓞⓓⓘⓝⓖⓣⓔⓢⓣ/ⓟⓨⓣⓗⓞⓝ19 [python] 단계별로 풀어보기 - 16단계 백준 16단계 그리디 알고리즘 https://www.acmicpc.net/step/33 그리디 알고리즘 단계 동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제 www.acmicpc.net 그리디 알고리즘 최적의 해를 구하는 데에 사용되는 근사적인 방법. 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 즉, 다음 것을 생각하지 않고 지금 당장에서 가장 최고의 답을 구하는 것! 따라서 가장 좋은 결과를 얻는 것이 보장되는 것은 아님. 16-1) 백준 11047번: 동전 0 N, K = map(int, input().split()) coin = [] count = 0 for i in range(N).. 2021. 8. 14. [python] 백준 1822번 차집합 사실 굉장히 쉬운 문제였는데 배운 점이 많다고 느낀 문제 잊지 않고 기억하려고 포스팅한다 코드 N = map(int, input().split()) A =set(map(int, input().split())) B = set(map(int, input().split())) res = [] for n in A: if n not in B: res.append(n) res.sort() print(len(res)) if len(res) !=0: print(*(res)) 1. 일단 if A not in B 라는 코드를 이론은 배웠는데 한번도 써보지 못했다 그런데 이번 기회에 써보게 되서 뜻깊었다! 그리고 종종 파이썬에 if A in B 등등의 쉬운 조건문을 사용할 수 있다는 점을 잊게되서 아쉬웠는데 다시 한번 학습.. 2021. 8. 9. [python] 단계별로 풀어보기 - 12단계 계수 정렬 / 카운팅 정렬 시간 복잡도 : O(n+k) (k는 데이터의 최댓값) => 속도가 엄청 빠름. 퀵 정렬, 힙 정렬, 합병 정렬의 평균 시간 복잡도 => O(nlogn) 정렬 방법: 데이터가 몇번 나왔는지 count -> 받은 수가 몇 번 들어왔는지 빈도 계산 -> 등장 횟수를 누적 합으로 바꾸기 -> 입력받았던 정렬할 배열을 뒤에서 앞으로 순회하면서 정렬된 배열에 넣기. (넣어준 뒤에는 누적합 -1 해주기) 정리: 시간 복잡도는 훨씬 유리하지만, 엄청난 메모리 낭비를 야기할 수 있음. (배열에 포함된 최댓값 만큼 메모리가 필요함) 따라서, k가 엄청 크다면 차라리 퀵정렬, 힙 정렬, 합병 정렬을 쓰는 것이 나음. 또한, 데이터 값이 정수라는 전제가 있어야한다. 순서대로 정렬을 해 주는데.. 2021. 5. 10. [python] 단계별로 풀어보기 - 11단계 브루트 포스 알고리즘(완전 탐색 알고리즘): 가장 간단한 알고리즘. 모든 경우의 수를 검사 하나하나 다 검사하다보니 시간적인 측면에서는 비효율적이지만 정확도가 100%임. 암호학에서는 가장 확실한 방법으로 통용 (ex) 숫자로만 구성된 4자리수 비밀번호를 풀 때, 0000 ~9999까지 모두 입력해보는 것) + 만들기 쉬운 알고리즘 + 문제의 복잡도에 매우 민감 11-1) 백준 2798번: 블랙잭 arr =[] a, b = map(int, input().split()) arr = list(map(int, input().split())) result = 0 for i in range(a): for j in range(i+1, a): for k in range(j+1, a): if arr[i] + a.. 2021. 5. 6. [python] 단계별로 풀어보기 - 10단계 전반적으로 풀이과정이 거의 유사하다 재귀함수에 대한 문제인데, 재귀함수는 정의 단계에서 자신을 재참조하는 함수이다. 그래서 식에 맞게 함수만 잘 선언해주면 바로 해결할 수 있는 단계! 10-1) 백준 10872번: 팩토리얼 def factorial(num): if num == 0: return 1 return num*factorial(num-1) n = int(input()) print(factorial(n)) n! = n*(n-1)*(n-2)*(n-3) ... 10-2) 백준 10870번: 피보나치 수5 def fibonacci(num): if num == 0: return 0 elif num == 1: return 1 return fibonacci(num-1)+fibonacci(num-2) n = .. 2021. 5. 1. 이전 1 2 3 4 다음 728x90