이번 역은 서현역🚇

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다. 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 # ..

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

코드잇 강의를 듣고 정리한 알고리즘 내용 입니다. 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 ..

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다. 선형 탐색 알고리즘 : 리스트의 처음부터 끝까지 순서대로 처음부터 하나씩 탐색하여 값을 찾는 것 이진 탐색 알고리즘 : 정렬된 리스트를 반씩 나누어 검색하여 값을 찾는 것 1 . 선형 탐색(Linear Serch)알고리즘 구현해보기 조건 -함수명 : linear_search -매개변수명 : 탐색할 값(element), 받을 리스트(some_list) -반환값 : element가 있을 경우 some_list의 인데스 반환, 없으면 None 반환 -for문 사용, element in some_list 사용 금지 풀이 # 시간 복잡도 : O(n) def linear_search(element, some_list): for i in range(len(some_..

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다. 컴퓨터 알고리즘 : 컴퓨터가 어떤 문제를 해결하기 위해서 컴퓨터가 이해할 수 있는 방식으로 정리되어 있는 해결 방법 1. 팔린드롬 체크 함수 구현 - "토마토" 나 "기러기"처럼 거꾸로 읽어도 똑같은 단어를 팔린드롬이라고할 때, 문자열 word가 팔린드롬인지 확인하는 함수를 만들어 해결해보기 조건 -함수명 : is_palindrome -매개변수명 : word -반환값 : 팔린드롬일 시 True , 아닐 시 False 풀이1 -내장함수(join,reversed)사용 def is_palindrome(word): reverse_word = "".join(reversed(word)) if reverse_word != word: return False retur..