-
분할정복법(divide and conquer)data struture & algorithm 2019. 6. 21. 23:38
Introduction 분할정복법의 문제해결 과정 : 큰 문제를 같은 형태의 겹치지 않은 작은 문제들로 쪼갠다. 작은 문제들은 큰 문제의 형태와 다르지 않아야 하고 서로 겹치면 안된다. 작은 문제를 각각 해결한다. 작은 문제들을 해결한 결과를 합친다. 분할정복법의 예 1) : 이진탐색(binary search) 이진탐색을 하려면 숫자들은 오름차순으로 정렬되어 있어야 한다. 위와 같이 숫자들이 정렬된 배열이 있다고 하자. low는 배열의 첫번째 인덱스에 해당하는 0이고, high는 가장 마지막 인덱스에 해당하는 11이다. mid 는 low 와 high 를 더한 값을 반으로 나눈 결과를 반올림한 6이 된다. (반올림을 하던, 내림을 하던 상관없다. 어차피 mid를 기준으로 하는 상호배타적인 작은 문제로 분할..
-
탐욕법(greedy algorithms)data struture & algorithm 2019. 6. 15. 21:56
1. Car Fueling 어떤 자동차가 A지점부터 B지점까지 이동해야한다고 가정하자. 자동차에는 연료가 만땅으로 채워져있고 연료가 만땅일 때 최대 400km 까지 달릴 수 있다. A지점과 B지점 사이의 거리는 950km이며 사이에 여러 개의 주유소가 있다. 운전자의 목표는 주유소를 경유하는 횟수를 최소한으로 하는 것이다. 여기서 운전자는 아래 세 가지 방법 중에 무엇을 택하면 되는가? 1. 자동차 위치 기준으로 제일 가까운 주유소에 들린다. 2. 자동차 위치 기준으로 남은 연료로 갈 수 있는 거리에 한해서 가장 멀리 있는 주유소에 들린다. 3. 연료가 다 떨어질 때까지 일단 달리고 본다. 당연히 2번일 것이다. 예를 들어, A지점에서 연료가 만땅인 상태로 출발했을 때 A지점 기준으로 각각 350km와 ..
-
generatorfluent python 2019. 6. 15. 15:21
어떤 자료를 순회하기 위해 이터레이블(iterable) 클래스를 직접 정의할 수도 있지만 대신에 제너레이터(generator) 함수를 사용할 수도 있다. __iter__() 메서드를 구현했으므로 abc.Iterable 클래스의 하위 클래스인 것으로 간주한다. 이전의 iterable, iterable 포스팅에서 Sentence의 __iter__() 는 SentenceIterator() 생성자를 호출해서 반복자를 생성하고 리턴했다. 그러나 위 Sentence의 반복자는 제너레이터 객체로서, __iter__() 메서드를 호출할 때 자동으로 생성된다. __iter__() 메서드는 제너레이터 함수기 때문이다. 1. 제너레이터 함수의 작동방식 함수 본체 안에 yield 키워드를 가진 함수는 모두 제너레이터 함수다...
-
iterable and iteratorfluent python 2019. 6. 9. 20:45
1. 시퀸스가 반복가능한 이유 : __iter__(), __getitem__() 파이썬의 반복자(iterator)패턴은 메모리에 다 들어가지 않을 정도로 큰 데이터집합을 한꺼번에 가져오는 것이 아니라 한 번에 하나씩 가져온다. 파이썬의 컬렉션은 모두 반복형(iterable type)이며, 다음과 같은 연산을 지원하기 위해 내부적으로 반복자(iterator)를 사용한다. for 루프 컬렉션의 생성과 확장 텍스트 파일을 한 번에 한 줄씩 반복 지능형 리스트, 딕셔너리, 집합 튜플 언패킹 함수 호출시 * 를 이용해서 위치 인자로 들어오는 값들을 언패킹 먼저 Sentence 라는 클래스를 구현하여 반복형(iterable type)을 알아보자. 이 클래스의 생성자는 텍스트로 구성된 문자열을 받은 후 단어별로 순회..
-
함수의 매개변수fluent python 2019. 5. 11. 19:42
위치 인자 & 키워드 인자파이썬의 위치 매개변수와 키워드 매개변수는 함수에 인자를 전달하는 데 다양한 방법을 제공한다. 아래의 tag()함수는 HTML 태그를 생성한다. x ------------------------hello------------------------helloworld------------------------hello------------------------helloworld------------------------------------------------hellopython------------------------hellopython------------------------21: 위치 인자를 1개만 사용해서 호출하면 이름을 가진 빈 태그를 생성한다. 22 ~ 23: 첫번째 ..
-
일급함수, 고위함수, 콜러블fluent python 2019. 5. 6. 21:33
일급함수파이썬에서 함수는 일급객체다. 어떤 프로그램 개체가 일급객체가 되기 위해서는 아래의 조건을 만족해야 한다. * 런타임에 생성할 수 있다. * 데이터 구조체의 변수나 요소에 할당할 수 있다. * 함수의 파라미터로 전달할 수 있다. * 함수의 리턴값으로 할당할 수 있다. 아래의 코드는 파이썬의 함수가 객체임을 보여준다. xxxxxxxxxx>>> def factorial(n):... '''this is factorial'''... return n * factorial(n-1) if n > 1 else n... >>> factorial>>> factorial(10)3628800>>> factorial.__doc__'this is factorial'>>> type(factorial)factorial함수는..
-
default parameter, named parameterjavascript 2019. 5. 6. 02:56
JS 함수의 default & named parameter 파이썬에는 함수 파라미터를 keword argument로 전달할 수 있다.xxxxxxxxxxdef print_cheese(kind, weight=1.0, region): print(f'{region}에서 온 {kind}치즈 무게는 {weight}kg이다.') print_cheese('모짜렐라', 3.4, '임실') # 파라미터 순서를 지켜야 함print_cheese(region='임실', kind='모짜렐라', weight=3.4) # 키워드로 파라미터를 전달하므로 순서를 지키지 않아도 됨.키워드 혹은 변수이름으로 파라미터를 전달하면 순서를 알 필요가 없으므로 함수 파라미터 갯수가 많을 때 유용하다. 최근에 JS로 파라미터 갯수가 5개 정도되는 ..