이번 역은 서현역🚇

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다. Greedy Algorithm - 당장 눈 앞에 보이는 최적의 선택을 하는 방식 - 최적의 답이 필요 없거나, 다른 알고리즘이 너무 느릴때 사용 - 최적 부분 구조가 있고, 탐욕적 선택 속성이 있다면 그리디 알고리즘이 최적의 솔루션을 보장함 장점 - 간단하고 빠르다 단점 - 최적의 답이 보장되지 않는다 1. 최소 동전으로 거슬러 주기 조건 - 함수명 : min_coin_count - 매개변수명 : value(거슬러 줘야하는 총약), coin_list(동전리스트) - 최소 동전 갯수 반환 풀이 def min_coin_count(value, coin_list): # 누적 동전 개수 count = 0 # coin_list의 값들을 큰 순서대로 본다 for c..

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다. Dynamic Programming - 한 번 계산한 결과를 재활용하는 방식 - 최적 부분 구조가 있고, 중복되는 부분 문제들이 있다면 이 방식으로 해결 방식 1. Memoization - 한 번 계산한 결과를 저장해 놓았다가 사용하는 방식 - 하향식 접근 - 재귀 사용 방식 2. Tabulation - 테이블(표)을 채워나가는 식으로 사용하는 방식 -상향식 접근 - 반복문 사용 1. 피보나치 (Memoization) 조건 - 함수명 : fib_memo - 매개변수명 : n(구하고 싶은 수), cache(저장 값) - n번째 피보나치 반환 풀이 def fib_memo(n, cache): # base case if n < 3: return 1 # 이미 n..

합병 정렬 : 두 개의 리스트를 하나의 정렬된 리스트로 합병하는 정렬 알고리즘 퀵 정렬 : 기준점보다 작은 것은 왼쪽에, 큰 것은 오른쪽에 정렬하는 정렬 알고리즘 1. 합병 정렬(Merge Sort) 구현 ''' # 시간복잡도 : O(NlogN) ''' def merge(list1, list2): i = 0 j = 0 # 정렬된 항목들을 담을 리스트 merged_list = [] # list1과 list2를 돌면서 merged_list에 항목 정렬 while i list2[j]: merged_list.append(list2[j]) j += 1 else: merged_list.append(list1[i]) i += 1 # ..

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다. 분할 정복(Divide and Conquer) : 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘 분할 정복 3단계 - 1. Divide(분할) - 2. Conquer(정복 == 풀기) - 3. Combine(합치기) 1 . 1부터 n까지의 합 구하기 조건 -함수명 : consecutive_sum -매개변수명 : start, end (end > start) - start부터 end까지의 합 리턴 풀이 def consecutive_sum(start, end): # base case if end == start: return start # 부분 문제를 반으로 나눠주기 위해서 문제의 정중앙을 정의한다 (Divide) mid = (..

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다. Brute Force : 무차별 대입으로 가능한 모든 경우에 대해 모두 탐색하여 조건에 충족되는 결과만 가져옴 장점 : 직관적이고 명확, 답을 확실하게 찾을 수 있음 단점 : 비효율적임 그럼에도 불구하고 알아야하는 이유 : 효율적인 알고리즘을 찾는 가장 기본적인 접근 방법이기 때문 1. 카드 뭉치 최대 조합 구하기 조건 -함수명 : max_product -매개변수명 : 카드 뭉치1(left_cards), 카드 뭉치2(right_cards) -카드 뭉치1과 카드 뭉치2에서 카드를 하나 뽑아서 곱했을 때 그 값이 최대가 되는 값을 반환 풀이 # 시간 복잡도 : O(mn) (m은 left_cards의 갯수, n은 right_cards의 갯수) def max_..

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다. 재귀 함수(Recursive Function) : 자기 자신을 호출하는 함수 재귀적으로 문제를 푼다는 것 : 부분 문제(같은 형태의 더 작은 문제)의 답을 이용해서 기존 문제를 푸는 것 1. 피보나치 수열 구현하기 조건 -함수명 : fib -매개변수명 : 받을 자연수(n) -10번째 항까지 출력하기 풀이 # 시간 복잡도 : O(2^n) def fib(n): # base case if n < 3: return 1 # recursive case return fib(n-1) + fib(n-2) # 테스트 for i in range(1, 11): print(fib(i)) 2. 숫자 합 구하기 조건 -함수명 : triangle_number -매개변수명 : 받을 ..

코드잇 강의를 듣고 정리한 알고리즘 내용 입니다. 1. 알고리즘 평가의 기준 1) 시간복잡도 : 얼마나 빠르게 실행되는지 2) 공간복잡도 : 얼마나 많은 공간이 필요한지 2. 복잡도 계산과 관련해서 알고 있으면 좋은 수학 개념 1) 거듭제곱 2) 로그 3) 1~n 까지의 합 3. 점근 표기법(Big-O Notation) 1) 점근 표기법 - 원 함수를 단순화시켜 최고차항의 차수만 고려하는 것 - ex) 원 함수 : 2(n^2) + 8n + 157 / 점근 표기법 : O(n^2) 2) 점근 표기법의 의미 - n의 차수가 클수록 시간이 많이 소요된다는 것을 알 수 있음 - 컴퓨터의 사양이 아무리 좋아도, 아무리 빠른 언어로 코딩을 해도 알고리즘이 별로면 한계가 있다는 것을 알려줌 4. 알고리즘 평가 주의 사..

선택 정렬 : 가장 작은 데이터를 선택하여 맨 앞 부터 순서대로 정렬해 나가는 알고리즘 거품 정렬 : 오른쪽부터 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식의 정렬 알고리즘 삽입 정렬 : 모든 요소를 앞에서 부터 정렬 범위를 확장시켜나가며 정렬을 진행하는 알고리즘 1. 선택 정렬(Selection Sort) 구현 ''' # 시간복잡도 (n^2) ''' def selection_sort(lst): for i in range(len(lst)-1): # 최저점 min_idx = i for j in range(i+1, len(lst)): if lst[min_idx] > lst[j]: min_idx = j lst[i], lst[min_idx] = lst[min_idx], lst[i] return lst ..