Algorithm/Algorithm_Theory
-
큐(Queue)Algorithm/Algorithm_Theory 2022. 11. 13. 23:57
선인섭출(First In First Out, FIFO) 구조 => 먼저 들어온 데이터가 먼저 나간다 큐 연산 - 데이터간 순서 관계를 유지해야 한다 - 맨 뒤 데이터 추가 - 맨 앞 데이터 삭제 - 맨 앞 데이터 접근 큐 동작 과정 보기 큐 구현은 2가지로 가능하다 1. 동적배열 2. 링크드 리스트 코드로 큐 구현해보기 # deque는 python collections 모듈에서 가지고 온다 from collections import deque queue = deque() # 큐의 맨 끝에 데이터 삽입 queue.append("연아1") queue.append("연아2") queue.append("연아3") print(queue) # deque(['연아1', '연아2', '연아3']) # 큐의 가장 앞 데..
-
그리디알고리즘(Greedy Algorithm)Algorithm/Algorithm_Theory 2022. 10. 22. 00:03
그리디 알고리즘이란?! 미래를 내다보지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 방식 A greedy algorithm is an approach for solving a problem by selecting the best option available at the moment. It doesn't worry whether the current best result will bring the overall optimal result. 장점 & 단점 장점: 간단하고 빠르다 단점: 최적의 답이 보장되지 않는다 When to use?! 다른 알고리즘 방법들이 너무 느릴 때 최적의 답이 필요 없을 때 feat.최적의 답을 구해주는 경우도 있다?! 1. 탐욕적 선택 속성(Greedy Choice Prop..
-
브루트포스(BruteForce)Algorithm/Algorithm_Theory 2022. 10. 10. 11:36
가능한 모든 경우의 수를 구해보는 것(it is just like iterating every possibility available to solve that problem) 예를 들어, 4자리 비밀번호를 알아내려고 할 때(비밀번호는 0-9까지) 0001,0002,....9999까지 모든 경우의 수를 구하는 것을 말한다. 실습) # left_cards에서 하나, right_cards에서 하나를 뽑아 두 카드의 곱이 가장 클 때를 구하기 def max_product(left_cards, right_cards): # 코드를 작성하세요. max_number = 0 for i in range(len(left_cards)): for j in range(len(right_cards)): if left_cards[i..
-
동적계획법(Dynamic Programming)Algorithm/Algorithm_Theory 2022. 9. 12. 11:49
Dynamic Programming이란?! 특정 값을 얻기 위해 매번 같은 결과를 반환하는 연산을 굳이 반복해서 수행한다면 문제를 효율적으로 해결할 수 없다.(재귀함수). 한 번 계산한 결과를 재활용하는 방식 Dynamic Programming 조건 1) 최적 부문 구조 (Optimal Substructure) - 부문 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것 ex) 피보나치 5번째의 수, fib(5)..(1,1,2,3,5..) 를 구한다고 했을 때 fib(3)과 fib(4) 2) 중복되는 부분 문제(Overlapping Subproblems) - fib(7)을 알아내기 위해, fib(5)를 2번씩이나..fib(4)를 3번씩이나..구하는것 재귀함수(Recursive Fu..