해나의 컴공생존기

알고리즘시간에 배운 동적프로그래밍 문제를 하나 가져와봤다. 의사코드를 한번 보면 재귀호출은 들어온 숫자(n)이 1이나 2가 아니라면 n-1과 n-2를 인자로 재귀호출하여 더해준다. 만약 6이 들어온다면 f(6) → f(5) + f(4) → ( f(4)+f(3) ) + ( f(3)+f(2) ) → ( ( f(3)+f(2) ) + ( f(2)+f(1) ) ) + ( ( f(2)+f(1) )+1 ) → ( ( ( f(2)+f(1) )+1 ) + ( 1+1 ) ) + ( (1+1 )+1 ) → ( ( ( 1+1 )+1 ) + 2 ) + 3 → 8 동적프로그래밍 의사코드를 보면 인자로 들어온 n만큼 배열을 만들어서 인덱스 1,2, 에는 1을 넣어주고 나머지 인덱스에는 앞에 두자리를 더한 값을 넣어준다. 하지만 '..

1. Quick Sort Quick Sort의 알고리즘을 한번 보겠다. 1. 배열에서 하나를 pivot으로 설정한다. 2. 배열의 가장 앞을 가르키는 i와 가장 뒤를 가르키는 j로 설정한다. 3. i와 j가 만날때까지 아래의 과정을 반복한다. 3-1. i가 가르키는 값과 pivot이 가르키는 값을 비교해서 i가 더 작다면 pivot보다 더 큰 숫자를 만날때까지 i를 증가시킨다. 3-2. j가 가르키는 값과 pivot이 가르키는 값을 비교해서 j가 더 크다면 pivot보다 더 작은 숫자를 만날때까지 j를 증가시킨다. 3-3. 둘다 적절한 값을 찾는다면 i가 가르키는 값과 j가 가르키는 값을 바꾼다. 4. 반복문을 나왔다면 pivot값과 j가 가르키는 값을 교환한다. 5. 처음부터 j까지, j 다음부터 끝까..

수학적 귀납법 ( 명제 : P(n)이 있을때 ) 기본형 : p(1)이 참이고, p(n-1) -> p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다. 강한 형태 : p(1)이 참이고, p(1)^p(2) ^ ....^p(n-1) -> p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다. 수학적 귀납법은 크게 Base 와 Step 부분으로 나뉜다. base: p(1) 이 참이다. step : p(n-1) -> p(n) 가 참이라고 보이면, p (n) 은 모든 자연수 n에 대해 참이라고 증명이 가능하다. base 와 step은 서로 독립적이고, 보통 base는 참인것을 금방 알수 있으며, 포인트가 되는 것은 step 부분이 참인 것을 알아내는 것이다. 그런데 step 에서 p(n-1) -..