수리 공작소

동적 계획법(Dynamic Programming, DP)이란? 동적 계획(Dynamic Programming, DP)이란 주어진 문제를 작은 부분으로 쪼개어 해결해나가는 방법이다. 이러한 부분에서 분할정복(Divide and Conquer, DC) 비슷하지만 두 가지 대표적인 차이점이 있다. 1. 문제 접근 방식의 차이 DC는 top-down approach이고, DP는 bottom-up approach라는 차이점이 있다. (물론 DP도 top-down으로 사용될 수 있지만 대체적으로 그렇다고 한다.) 2. DP의 추가적인 메모리 저장 DP는 DC와는 다르게 이전에 계산한 값을 배열(혹은 다른)에 저장을 하여 재활용한다. 이와 같은 방법을 Memoization이라고 한다. 덕분에 이후에 중복 계산을 피하..

JAVA의 역사 [개발] 선마이크로칩스의 James Gosling이 이끄는 팀 [개요] 당시 미국 대선에 출마한 Al Gore의 공약 중, information highway라는 공약이 있었다. 이에 영감을 얻어 제임스 고슬링의 초기 아이디어로는 가전 제품 부착용 프로그래밍 언어를 만들어보자는 시도를 했음. (왜 기존의 언어를 사용하지 않고? -> 가전 제품과 컴퓨터는 사용 대상 자체가 다르므로 다른 특성을 가져야한다고 생각.) 그래서 제임스 고슬링의 design goal은 다음과 같았다. 컴퓨터용 언어인 C언어보다 쉽고, 안전하고, 객체 지향인 언어를 만드는 것이었다. 하지만 Al Gore가 낙선을 하게 되고 원래 목표하던 가전 제품 대상의 언어로 사용하기 어려워졌다. 하지만 그때 "웹"의 급부상(19..

문제 요약 : 전체 버스 N개가 있고, 그 중 창영이가 이용할 버스가 M개 입력으로 주어진다. 이 버스를 순서대로 탈 때, 들어가는 총 환승 비용으로 계산하는 문제이다. (전체 버스 간의 환승비용은 이차원 배열로 입력받는다.) #include using namespace std; int main() { int allBus = 0, useBus = 0, fee = 0;; // 모든 버스의 수, 창영이가 사용할 버스의 수, 총 환승 요금 cin >> allBus >> useBus; if (allBus 100 || useBus > allBus || useBus < 1) return 0; //조건 필터링 int* listUseBus = new int[useBus]; // 창영이가 사..

영어로 된 문제를 처음 풀어본다...! 영어로 쓰여져 있으면 괜히 더 어려워보인다. 사실은 복잡하지 않은 문제였다! 어쨋든 시작, 문제를 요약하자면 다음과 같이 벽돌은 몇개의 스택으로 나누어 쌓는다고 가정한다. 스택의 길이를 일정하게 유지하지 않고 쌓은 뒤, 최소한의 움직임으로 전체 스택의 길이를 맞추어주는 문제이다. 이때 개인적으로 생각했을 때 잊어버리지 말아야할 조건은 1. 위와 같은 형태를 한 세트라고 두었을 때, 입력은 여러 세트가 가능하다. 2. 0이 입력되었을 때 입력이 끝났음을 알 수 있다. (0에 대해선 계산을 돌지 않는다.) 3. 벽돌의 전체 수는 스택의 개수로 나누어 떨어진다. 즉, 남는 벽돌이 없다는 뜻이다. 다음은 코드이다. 먼저 각 세트의 최소 이동 벽돌 수를 구해주는 함수를 작성..