![]()
License License: Creative Commons BY-NC-SA Divide & Conquer Divide & Conquer의 순서 1. 문제를 같은 유형의 문제로 쪼갠다. 2. 각각의 작은 문제들을 독립적으로 해결한다. 3. 그 해결들을 합친다. 병합정렬 각각의 가장 작은 숫자들부터 비교해서 리스트를 합치는 알고리즘. big-O는 n이다. 분할정복의 예시 def merge(left,right): """Assumes left and right are sorted lists. Returns a new sorted list containing the same elements as (left + right) would contain.""" result = [] i,j = 0, 0 while i <..
License License: Creative Commons BY-NC-SA 9회차 [MIT OpenCourseWare 6.00 9회차] 이진 탐색 정렬된 리스트가 있다고 생각하고 리스트의 범위를 잡은 뒤 midpoint를 구해 절반씩 버려가며 이진 탐색을 시행한다. 이후 마지막으로 남은 2개를 검사한다. 이진탐색은 강력하지만 반드시 선형탐색보다 빠른 것은 아니다. Binary def bsearch(s,e,first,last,calls): print(first, last, calls) if (last - first) < 2: return s[first] ==e or s[last] == e mid = first + int((last - first)/2) if s[mid] == e: return True i..
![]()
재귀 어떠한 것을 정의할 때 자기 자신을 참조하는 것. (자기 자신을 계속 호출하는 알고리즘) 재귀를 사용하는 이유 재귀는 일반적으로 반복문보다 느리다. (모든 재귀문은 반복문으로 나타낼 수 있다) 그러나 코드가 깔끔해진다. (다른사람이 보고 수정, 보수하기 쉽다) 코딩 하는법 1. 문제의 정의를 정확히 표기한다. 2. 종료 조건을 표기한다. 3. 컬스택 호출의 흐름을 알아야 한다. 선언적 프로그래밍 (Declarative programming) 명령형 프로그래밍 = 알고리즘 명시O, 목표는 명시X 선언형 프로그래밍 = 알고리즘 명시X, 목표는 명시O 선언적 프로그래밍에서는 코드의 목적만 선언해주면 중간 과정을 컴퓨터가 알아서 한다 [Reference] 하노이탑 (How to solve?) 하노이탑을 옮..
License License: Creative Commons BY-NC-SA 1. Contents 선형 알고리즘 def exp(a,b): ans = 1 while (b>0) : ans *= a b -= 1 return ans 위와 같은 식이 있을 때 이 함수의 값을 구하기 위해서- (ans = 1)과 (return ans)의 두가지 연산에 더해서 1. \> 연산 2. *= 연산 3. -= 연산 n회의 3가지의 단계를 거친다. 따라서 3n + 2의 단계가 필요하다. 점진적으로 숫자가 증가함에 따라 첨가된 +2의값은 중요하지 않고, 곱해진 3 또한 중요하지 않아진다. 여기서 중요한 것은 문제의 크기가 커질 때 증가의 비율이다. 알고리즘의 문제의 크기가 한계만큼 점점 더 커지는것에 대하여 증가비율을 특정하기 ..
License License: Creative Commons BY-NC-SA 7회차 [MIT OpenCourseWare 6.00 7회차] 1. Contents 리스트와 딕셔너리 자료형 리스트는 자료형을 연결한 것이다. Java와 다르게 형태가 다른 것도 같은 리스트에 들어갈 수 있고, 쉽게 변형과 추가, 제거가 가능하다. [점프투 파이썬 : 리스트] 딕셔너리는 Key와 Value를 한 쌍으로 갖는 자료형이다. Hash 기술을 사용해서 빠른 검색이 가능하다. [점프투 파이썬 : 딕셔너리] 의사코드 (pseudocode) 의사코드란 실행하고자 하는 단계의 설명을 쓰는 것. ex) 1. 밑변의 값을 float형으로 입력한다. 2. 높이의 값을 float형으로 입력한다. 3. 제곱근을 구하고 float형으로 h..
![]()
License License: Creative Commons BY-NC-SA 6회차 [MIT OpenCourseWare 6.00 6회차] 1. Contents Newton-Raphson method 탄젠트(기울기)는 근사값을 구할때 매우 유용하다. def squareRootBi(x, epsilon): assert x>= 0, 'x must be non-negative, not' + str(x) assert epsilon > 0, 'epsilon must be postive, not' + str(epsilon) low = 0 high = x guess = (low + high) / 2.0 ctr = 1 while abs(guess**2 -x) > epsilon and ctr 0, 'epsilon must ..
![]()
부동 소수점이란? 뜰 부(浮) 움직일 동(動) 소수점. 실수를 컴퓨터상에서 근사하여 표현할 때 소수점의 위치를 고정하지 않고 그 위치를 나타내는 수를 따로 적는 것. 부동소수점 문제를 본인과 같이 사전 지식이 부족한 사람들을 위해 최대한 이해하기 쉽게 정리해보았다. 1. 2진법 변환 2진법 변환을 쉽게 이해하기 위해 1부터 나누어 본다. 1을 2로 나누어 보았다. 1은 2로 나누어지지 않고 나머지값이 1이 남는다. {(2^0 x 1)} 2를 2로 나누어 보았다. 2는 2로 한번 나누어지고 나머지 값은 없다. {(2^1 x 1) + (2^0 x 0)} 3을 2로 나누어 보았다. 3은 2로 한번 나누어지고 나머지 값이 1이 남는다. {(2^1 x 1) + (2^0 x 1)} 4를 2로 나누어 보았다. 2는 ..
![]()
License License: Creative Commons BY-NC-SA 5회차 [MIT OpenCourseWare 6.00 5회차] 1. Contents Floating number 부동소수점에 관한 소개가 나왔다. import math from re import A a = math.sqrt(2) b = a*a print(a) print(b) print(b==2) print(b==a) 위와 같은 코드를 실행하면 1.4142135623730951 2.0000000000000004 False False 위와 같은 답이 나온다. 저장된 값이 제곱근의 근사치이기 때문이다. 부동소수점에 대해서는 이전에 정리를 해두어서 다시 적지는 않는다. [부동소수점] 위와 같은 상황은 두가지 근본적 문제를 내포한다. 우리..
License License: Creative Commons BY-NC-SA 4회차 [MIT OpenCourseWare 6.00 4회차] 1. Contents Decomposition (분해) 코드에 구조를 두는 것, 코드를 모듈로 나누는 방법. 모듈은 이해하고 쉽고, 다시 사용할 수 있다. 프로세스의 성분들을 분리한다. Return 1. 계산을 멈추고 함수로 부터 제어를 돌려준다. 2. 명령문의 값을 가지고 와서 전체 계산의 값으로 돌려준다. Local variable (지역변수) 맴버변수(Member variable) : Class 내부 영역에 정의한 변수(클래스 내부로 한정) 지역변수(Local variable) : Method 안에 있는 변수 매개변수(Parameter) : 함수로 값을 전달하는 ..
License License: Creative Commons BY-NC-SA 3회차 [MIT OpenCourseWare 6.00 3회차] 1. Contents 반복적 문제들을 해결하는 단계 중요한 변수를 선택한다. 그것을 루프 밖에서 초기화 한다. 옳은 마지막 테스트(얻고자 하는 값)를 만들어야 한다. 코드의 블록을 만든다. (코드의 블록은 명령문들의 세트) 끝나면 print 등으로 확인한다. Flowchart 논리를 시각화 하는 유용한 도구이다. ☆ 목표 : 귀찮더라도 로직을 작성하기 전에 플로우 차트를 손으로 그려본다. 플로우차트에 충분히 익숙해지면 머릿속으로 그린다. [Link : free UML] [Link : How to draw Flow chart?] Simulate the code to de..
