DP란? 동적 계획법(dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 부분 문제 반복 부분 문제 반복이란 어떤 문제가 여러개의 부분 문제로 쪼개질 수 있는 경우를 말한다. 계속해서 같은 부분 문제가 여러번 재사용 되거나 재귀 알고리즘을 통해 해결되는 문제이다. ex) 피보나치 수열에서 fib(n)문제는 fib(n-1)구하기와 fib(n-2)구하기의 부분문제로 쪼개질 수 있다. 최적 부분 구조 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다. ex) 피보나치 수열에서 fib(n)문제의..
Computer science/Algorithm
재귀 어떠한 것을 정의할 때 자기 자신을 참조하는 것. (자기 자신을 계속 호출하는 알고리즘) 재귀를 사용하는 이유 재귀는 일반적으로 반복문보다 느리다. (모든 재귀문은 반복문으로 나타낼 수 있다) 그러나 코드가 깔끔해진다. (다른사람이 보고 수정, 보수하기 쉽다) 코딩 하는법 1. 문제의 정의를 정확히 표기한다. 2. 종료 조건을 표기한다. 3. 컬스택 호출의 흐름을 알아야 한다. 선언적 프로그래밍 (Declarative programming) 명령형 프로그래밍 = 알고리즘 명시O, 목표는 명시X 선언형 프로그래밍 = 알고리즘 명시X, 목표는 명시O 선언적 프로그래밍에서는 코드의 목적만 선언해주면 중간 과정을 컴퓨터가 알아서 한다 [Reference] 하노이탑 (How to solve?) 하노이탑을 옮..
부동 소수점이란? 뜰 부(浮) 움직일 동(動) 소수점. 실수를 컴퓨터상에서 근사하여 표현할 때 소수점의 위치를 고정하지 않고 그 위치를 나타내는 수를 따로 적는 것. 부동소수점 문제를 본인과 같이 사전 지식이 부족한 사람들을 위해 최대한 이해하기 쉽게 정리해보았다. 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는 ..
