Priceless

입력 받은 코인의 금액으로 코인 여러 개를 사용하여 목표 코인 금액을 맞출 수 있는 경우를 찾는 문제 물론 브루트 포스로도 풀 수 있겠지만 이 문제는 제한 시간이 0.5초로 다이나믹 프로그래밍으로 풀어야한다 dp[0]은 모든 코인이 0개가 사용되므로 dp[0] = 1로 설정한다 새로 갱신되는 dp 값은 새로운 코인 단위를 사용하기 전의 dp 값과 새로운 코인 단위의 dp 값을 합하면 새롭게 dp가 갱신된다 문제의 예시 경우를 살펴본다 1원, 2원, 5원을 사용하여 10원을 구성하는 예시이다 1원을 사용하는 경우 1원부터 10원까지 구성할 수 있는 경우는 모두 1가지 2원을 사용하는 경우 1원 1가지, 2원 2가지(1+1, 2), 3원의 경우 1원만 사용해서 3원을 구성하는 경우와 2원을 1원과 2원을 사..

이제는 dp를 푸는 대략적인 방법?을 알게 되었다 기본 배열, dp 배열, max or min 을 통해 구할 수 있다 물론 max 와 min 함수를 쓰기 위해서는 입력 값으로부터 어떻게 출력하는 과정까지 그 과정을 분석해야 함수를 쓸 수 있을 것이다 이 문제는 테스트 케이스 당 두 줄의 입력 값을 받는다 dp 배열의 초기 부분은 미리 초기화한다 배열의 길이가 1이더라도 동작한다 변이 이웃하지 않으니까 대각선이거나 두 칸 뒤의 값 중에서 최대 값을 고른다 이후 배열의 마지막에서 더 큰 값을 출력한다 // baekjoon 9465 #include #include using namespace std; // codes for fast I/O void init(){ cin.tie(0); cout.tie(0); i..

Computer Systems: A Programmer's Perspective 위 책의 내용을 정리하였습니다 Chapter 1: A Tour of Computer Systems 아래 코드를 기준으로 설명 // hello.c #include int main() { printf("hello, world\n"); } 1-1. Information Is Bits + Context 프로그램은 소스 프로그램(소스 파일)로 이루어져 있다 소스 프로그램은 bit(0과 1)의 연속이며, 8bit를 1byte로 정한다 ASCII code(아스키코드)를 사용하여 문자를 정수로 변한다 아래는 hello.c를 아스키코드로 변환한 결과이다 이러한 코드를 해석하기 위해서는 context가 필요하다 context를 통해 이 코드가..