본문 바로가기

코드잇17

알고리즘 패러다임 / Divide and Conquer [1/2] 알고리즘 패러다임 / Divide and Conquer Divide and Conquer (분할 정복) : 하나의 문제를 해결하기 위해 여러 가지 부분문제로 나누고 부분문제들을 정복한 뒤 부분문제들을 합쳐서 문제를 해결한다. (문제를 정복하다 : 문제에 대한 답을 알아내다) def consecutive_sum(start, end): if end == start: return start mid = (start + end) // 2 return consecutive_sum(start, mid) + consecutive_sum(mid + 1, end) # 테스트 print(consecutive_sum(1, 10)) print(consecutive_sum(1, 100)) print(consecutive_sum(.. 2021. 4. 1.
알고리즘 패러다임 / Brute Force 알고리즘 패러다임 / Brute Force 알고리즘 패러다임 : 자주 나타나는 알고리즘 접근법 Brute Force : 가장 순진한 알고리즘 접근법 (모든 경우의 수의 값을 다 구해서 정답을 도출) Brute Force 의 장점 : 직관적이고 명확하다. 답을 확실하게 찾을 수 있다. 인풋이 엄청 큰 경우에는 Brute Force 알고리즘을 쓰면 오래걸리겠지만, 효율적인 알고리즘의 항상 첫 시작은 Brute Force 이다. Brute Force 방법으로 알고리즘을 한번 생각해보고 거기서부터 발전을 시키는 것이다. 이것이 Brute Force 이해의 필요성이다. def max_product(left_cards, right_cards): new_cards = [] for i in left_cards: for.. 2021. 3. 31.
재귀 함수 / 재귀 함수 재귀 함수 / 재귀 함수 재귀 함수 (Recursive Function) 자기 자신을 호출하는 함수 def countdown(n): if n > 0: print(n) countdown(n - 1) countdown(4) # #4 #3 #2 #1 재귀 활용 예시 재귀적으로 문제를 푼다는 것 = 같은 형태의 더 작은 문제를 푸는 것 = 부분 문제의 답을 이용해서 기존 문제를 푸는 것 팩토리얼(!) 예제 5! = 1 x 2 x 3 x 4 x 5 = 120 4! = 1 x 2 x 3 x 4 = 24 0! = 1 n! 에서 n = 0 인 경우, n! = 1 (base case) n! 에서 n > 0 인 경우, n! = (n-1)! x n (recursive case) def factorial(n): if n ==.. 2021. 3. 30.
좋은 알고리즘이란? / 알고리즘 평가법 좋은 알고리즘이란? / 알고리즘 평가법 좋은 코드 기준 시간 공간 (컴퓨터의 저장공간) 시간 복잡도 (Time Complexity) 데이터가 많아질수록 걸리는 시간이 얼마나 급격히 증가하는가 시간 복잡도를 계산하려면 알아야하는 약간의 수학 지식 거듭제곱과 로그 1부터 n까지의 합 점근 표기법(Big-O Notation) n 의 영향력이 더 큰 곳을 찾으면 된다. 핵심 : n 이 엄청 크다고 가정 n 이 별로 크지 않으면, 안 좋은 알고리즘을 써도 문제 없다. n 이 엄청 크다고 가정하므로 n 의 영향력이 큰쪽이 나중에 커질수밖에 없다. 절대적인 시간이 아닌 성장성이 가장 중요하다. n제곱이 n 이나 상수 같은 값에 비해 훨씬 더 큰 값이므로 나머지 값은 큰 영향을 주지 않는다고 생각하여 O(n제곱)만 표.. 2021. 3. 29.
좋은 알고리즘이란? / 하나의 문제, 여러 가지 알고리즘 좋은 알고리즘이란? / 하나의 문제, 여러 가지 알고리즘 하나의 문제에는 여러가지 해결 방법(알고리즘)이 존재한다. Ex) 알파벳 순으로 되있는 도서관에서 책 찾는 방법 탐색 선형 탐색 알고리즘 (linear search algorithm) 이진 탐색 알고리즘 (binary search algorithm) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53] 이라는 배열이 존재할 때 29 값 찾는 방법 선형 탐색 : 처음 값 '2' 부터 '3', '5'... 순서로 값을 확인 이진 탐색 : 중간 값 '19' 와 찾는 값 '29' 의 대소를 비교하면 중간 값이 더 작으므로 중간 값보다 작은 왼쪽 원소들은 모두 제외한 후 [23, 29, 31, 37, .. 2021. 3. 28.
좋은 알고리즘이란? / 알고리즘이란? 좋은 알고리즘이란? / 알고리즘이란? 알고리즘이란? 알고리즘은 어떤 문제를 해결하기 위한 자세한 방법이다. 목적은 같으나 방법이 조금씩 다를 수 있다. 같은 문제를 해결하기 위해서도 다양한 알고리즘이 존재한다. 좋은 알고리즘이란? 1. 문제를 해결하는 것. 2. 문제를 더 잘 해결하는 것. 컴퓨터 알고리즘이란? 컴퓨터가 어떤 문제를 해결하기 위해서 컴퓨터가 이해할 수 있는 방식으로 정리되어 있는 해결 방법이다. 예를 들어 뒤죽박죽 섞여 있는 배열 숫자 원소들을 순서대로 배치하는 문제가 있다면, 우리는 정확하고 효율적으로 숫자들을 정렬하는 알고리즘을 찾아내야 한다. 네비게이션 어플 두 회사에서 각각 네비게이션 어플을 출시했다고 가정해보자. 둘 다 디자인이 훌륭하고, 사용성도 나쁘지 않다. 그러면 어떤 어플.. 2021. 3. 27.

티스토리툴바