반응형 2017/06/096 [기술의역사] 파이썬(Python) 파이썬(Python) "인생은 너무짧다. 그래서 파이썬이 필요하다."파이썬은 짧은 코드에서 나오는 효율성 뿐만아니라 들여쓰기로 만들어지는 자동 정렬,어떤 분야든 가리지 않고 닥치는대로 사용할 수있는 범용성 등 많은 무기를 가지고 있다.이 때문인지는 몰라도 2017년 6월 기준 프로그래밍 점유율 수준은 당당하게 4위를 차지하고 있다. (파이썬의 창시자 - 귀도 반 로썸) 파이썬이 최근에 주목받고 있다고 생각할지 모르겠지만 발표시기는 1991년,웹 서비스가 일반인들에게 널리 상용화되기 전에 나온 언어이다.언어를 만든이는 귀도 반 로썸(Guido van Rossom)으로 1989년 크리스마스 주에 연구실이 닫혀있어 심심한 김에 만들었다고 한다.리누스나 귀도 둘다 심심한 김에 걸작을 만들었다는데 있어서, 위대한.. 2017. 6. 9. [알고리즘] 동적 계획법(Dynamic Programming) - 5 동적 계획법(Dynamic Programming) - 5 이번 시간에는 Longest Common Subsequence를 알아보자Longest Common Subsequence는 줄여서 LCS라고 부르는데, 약어로 부르는것은 그만큼 유명하다는 뜻이다.입력으로 2개의 문자열이 주어지며, bcdb는 문자열 의 subsequence이다.또한 는 문자열 와 의 common subsequence(공통 부분 문자열)이다. 우리가 고려해야할 부분은 LCS인데, 입력으로 2개의 문자열이 주어졌을때, common subsequence중에서 가장 긴것을 찾으면 된다.예를 들어, 는 와 의 LCS가 되는 것이다. 그렇다면 위의 그림에서 x라는 문자열과 y라는 문자열이 입력으로 주어진 문자열이며,z가 우리가 원하는 최적해라고.. 2017. 6. 9. [알고리즘] 동적 계획법(Dynamic Programming) - 4 동적 계획법(Dynamic Programming) - 4 이번에는 동적 계획법 알고리즘에서 가장 유명한 알고리즘인 Matrix chain multiple을 알아보자이것은 말그대로 두 행렬을 곱하는 알고리즘이다.위의 코드는 pxq인 A 행렬과 qxr인 B 행렬의 곱하기 이다.3개의 반복문으로 돌아가며 곱셈 연산의 횟수는 pqr번이고 결과값은 C에 저장된다. 그러나 우리가 지금 하려는 것은 Matrix chain이다. ABCD의 행렬을 차례로 곱해야 하는 것이다.행렬은 결합 법칙이 성립하므로 계산 순서에 따라서 곱셉 연산의 횟수가 달라진다.그럼 n개의 행렬을 곱할 때 최적의 순서는 무엇일까 이 문제를 동적 계획법으로 접근할때 어떻게 풀어야 하는지를 생각해보면,subproblem으로 나눠서 optimal su.. 2017. 6. 9. [알고리즘] 동적 계획법(Dynamic Programming) - 3 동적 계획법(Dynamic Programming) - 3 동적 계획법이라는 것은 순환식과 뗄레야 뗄수 없는 관계이다. 다시 말해 순환식을 효과적으로 푸는 테크닉이라고 할 수 있다.따라서 동적 계획법은 다음과 같은 특징을 가지고 있다. 1. 일반적으로 최적화문제 혹은 카운팅 문제에 적용된다.2. 주어진 문제에 대한 순환식을 정의한다.3. 순환식으로 Memoization 또는 Bottom up 으로 푼다. 동적계획법은 subproblem을 풀어서 원래 문제를 푸는 방식이다. 그런 의미에서 분할 정복법과 공통점이 있다.분할 정복법에서는 분할된 문제들이 서로 disjoint하지만 동적계획법에서는 그렇지 않다.즉 서로 overlapping하는 subproblem들을 해결함으로써 원래의 문제를 해결하는 것이다. 분.. 2017. 6. 9. 이전 1 2 다음 반응형
